// Compile with: gcc -o gmp_optimised_lucas_ver2 gmp_optimised_lucas_ver2.c -lm -lgmp #include #include #include #include int main(int argc, char* argv[]) { char str[1000000], *string=str; int i, r, log_2_of_n; mpz_t a; mpz_t n; mpz_t fermat_n; mpz_t temp; mpz_t discriminant; mpz_t s; mpz_t t; mpz_t n_plus_1; if ( argc != 1 ) { printf( "Usage: echo n | ./gmp_optimised_lucas_ver2\n" ); printf( "Or like: echo \"print(n)\" | gp -q | ./gmp_optimised_lucas_ver2\n" ); printf( "Or like: ./pfgw64 -k -f0 -od -q\"n\" | ./gmp_optimised_lucasver2\n" ); exit ( -1 ); } gets ( str ); if ( ( string = strchr( str, ':' ) ) && string[1] == ' ' ) string += 2; else string = str; mpz_init_set_str ( n, str, 10 ); // return ( mpz_probab_prime_p (n,1) ); // Deal with Fermat numbers for ( i = 0; i < 5; i++ ) { if ( mpz_cmp_ui ( n, (1<<(1<= 0; i-- ) { if ( mpz_tstbit ( n, i ) ) { mpz_mul ( s, s, t ); mpz_sub ( s, s, a ); mpz_mul ( t, t, t ); mpz_sub_ui ( t, t, 2 ); } else { mpz_mul ( t, s, t ); mpz_sub ( t, t, a ); mpz_mul ( s, s, s ); mpz_sub_ui ( s, s, 2 ); } mpz_mod ( s, s, n ); mpz_mod ( t, t, n ); } if ( ( mpz_cmp ( s, a ) == 0 && mpz_cmp_ui ( t, 2 ) == 0 ) ) { printf ( "Is PrP!\n"); mpz_clear ( a ); mpz_clear ( s ); mpz_clear ( t ); return ( 0 ); } else { printf ( "Is composite.\n" ); mpz_clear ( a ); mpz_clear ( s ); mpz_clear ( t ); return ( 1 ); } }