大きな桁数を因数分解するプログラムについて
Posted: 2014年9月16日(火) 20:14
初投稿です。自力ではどうしても解決できなかったので質問させていただきました。
よろしくお願いします。
50桁程度の大きな桁数を因数分解するプログラムを作ろうとしています。
採用したアルゴリズムはポラードのρ法です。以下にアルゴリズムを示します。
nはユーザが入力する大きな桁数の整数です。
1[乱数種の選択]
ランダムにa∈[1,n-3]を選ぶ;
ランダムにs∈[0,n-1]を選ぶ;
U=V=s;
F(x)=(x * x + a) mod nと定める;
2[因子の探索]
U=F(U);
V=F(V);
V=F(V); //2回適用するのは意図的
g=gcd(U-V,n); //最大公約数を求める
if(g==1) goto [因子の探索];
3[乱数種が悪かった場合]
if(g==n) goto [乱数種の選択];
4[成功]
return g; //非自明な因子が見つかった
変数a,s,nに大きな桁数の整数をいれたいのですが、
intだと9桁(正確には2^31-1)までしか表現できません。
そこで大きな桁数をどう扱ったらいいのかを教えていただきたいです。
環境
OS:Linux
コンパイラ:gcc
以下ソースコードを載せます。
よろしくお願いします。
50桁程度の大きな桁数を因数分解するプログラムを作ろうとしています。
採用したアルゴリズムはポラードのρ法です。以下にアルゴリズムを示します。
nはユーザが入力する大きな桁数の整数です。
1[乱数種の選択]
ランダムにa∈[1,n-3]を選ぶ;
ランダムにs∈[0,n-1]を選ぶ;
U=V=s;
F(x)=(x * x + a) mod nと定める;
2[因子の探索]
U=F(U);
V=F(V);
V=F(V); //2回適用するのは意図的
g=gcd(U-V,n); //最大公約数を求める
if(g==1) goto [因子の探索];
3[乱数種が悪かった場合]
if(g==n) goto [乱数種の選択];
4[成功]
return g; //非自明な因子が見つかった
変数a,s,nに大きな桁数の整数をいれたいのですが、
intだと9桁(正確には2^31-1)までしか表現できません。
そこで大きな桁数をどう扱ったらいいのかを教えていただきたいです。
環境
OS:Linux
コンパイラ:gcc
以下ソースコードを載せます。
#include <stdio.h>
#include <stdlib.h>
int function(int s,int a,int n);
int gcd(int x,int y);
int main()
{
int a;
int s;
int g;
int n;
int U;
int V;
printf("input number:\n");
scanf("%d",&n);
while(1){//3乱数種が悪かった場合のループ
a = rand() % (n-3) + 1;
s = rand() % n;
U=s;
V=s;
while(1){//2因子の探索ループ
U=function(U,a,n);
V=function(V,a,n);
V=function(V,a,n);
g = gcd(U-V,n);
printf("1");
if(g!=1){
break;
}
}//2
printf("2");
if(g!=n){
break;
}
}//3
printf("%d\n",g);
return 0;
}
int function(int s, int a, int n)
{
int f;
f = (s*s*a) % n;
return f;
}
int gcd(int x, int y)
{
if(y==0){
return x;
}
else{
return gcd(y,x%y);
}
}