大きな桁数を因数分解するプログラムについて

[理動]

初投稿です。自力ではどうしても解決できなかったので質問させていただきました。
よろしくお願いします。

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);
  }
}

[sleep]

intだと9桁(正確には2^31-1)までしか表現できません。
そこで大きな桁数をどう扱ったらいいのかを教えていただきたいです。

一応、現在だと c も c++ も
long long int
という、8byte(64bit)の型が用意されているはずです。

コード:

printf("long long int: %d\n", sizeof(long long int));

ご使用の環境で 使用可能かどうか確認してみてください。

[box]

仮にお使いの処理系でlong long intが使えるとしても、

50桁程度の大きな桁数を因数分解するプログラムを作ろうとしています。

これはむずかしいような気がします。
long long intの範囲よりも大きな整数を扱うことのできる環境を
自前で用意する必要がありそうです。

[理動]

返信ありがとうございます。

long long int の存在を初めて知りました。
しかしこれを使っても20桁程度なのでまだまだ足りないのです。

やはりc言語で50桁程度の因数分解は厳しいのでしょうか・・・

[sleep]

boxさん、ありがとうございます。
ほんとですね。long long intでも桁数足りないのですね。

確かにboxさんがおっしゃるようにあとは自作するしかないですね。

[みけCAT]

GMPというライブラリがあります。
このライブラリ(version6)のライセンスは、GNU LGPL v3またはGNU GPL v2です。

[理動]

sleepさん,boxさん,みけCATさん,返信ありがとうございました。
GMPを利用して進めてみようと思います。
何かありましたらまた質問させていただきます。

ありがとうございました。またよろしくお願いします。