/*
C で書いた rho 法
gmp パッケージが必要である。
(gmp の最新版は gmp-3.1.1 であり、
GNU ソフトをおいてあるFTPサイトからとってくることができる。
インストール法や使用法はgmp パッケージ付属のREADME をよむこと。)
このファイルをコンパイルするには 
cc rho_ho.c -o rho_ho -lgmp
とすればよい。
*/
#include<stdio.h>
#include<gmp.h>
int advance(mpz_t x, mpz_t n){
mpz_mul(x,x,x);
mpz_add_ui(x,x,1);
mpz_mod(x,x,n);
return(0);
}


int main(){
mpz_t a,b,x,n;
mpz_init(a);
mpz_init(b);
mpz_init(x);
mpz_init(n);
mpz_set_str(n,"607143768775207",10);
mpz_set_ui(a,1);
mpz_set_ui(b,1);
while(1){
advance(a,n);
advance(b,n);
advance(b,n);
mpz_sub(x,a,b);
mpz_gcd(x,x,n);
if (mpz_cmp_ui(x,1)!=0)
{
mpz_out_str(stdout,10,x);
puts("\n");
break;
}
}
mpz_clear(a);
mpz_clear(b);
mpz_clear(x);
mpz_clear(n);
return(0);
}