Algoritmo solovoy-strassen

/*
============================================================================
Name : solovay_strassen.c
Author : Moises Osorio
Description : Solovoy-Streaasen algorithm============================================================================
*/

#include
#include
#include

//#define TEST

#define BASE 16
#define REPETITIONS 50
#define MAX_PRIME 1000000long long primes[MAX_PRIME+1];
long long primes_count = 0;

long long getTime()
{
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec*1000000 + tv.tv_usec; // Microsecondprecision
}

void calculateSmallPrimes() // Sieve of Eratosthenes
{
int is_prime[MAX_PRIME+1];
long long i, j;
for (i = 0; i 0) {
k--;
mpz_urandomm(a, RAND, n1);
mpz_add_ui(a, a, 1);int j = jacobi(a, n);
if (j == -1) { // jac = n + jac(a,n)
mpz_sub_ui(jac, n, 1);
} else if (j == 1)
mpz_set_si(jac, j);

mpz_divexact_ui(exp, n1, 2); // exp = (n-1)/2mpz_powm(mod, a, exp, n); // mod = a^((n-1)/2) % n
if (mpz_cmp_ui(jac, 0) == 0 || mpz_cmp(mod, jac) != 0) { // Is it a liar?
mpz_clear(a);
mpz_clear(jac);
mpz_clear(mod);
mpz_clear(exp);mpz_clear(n1);

return 0;
}
}

mpz_clear(a);
mpz_clear(jac);
mpz_clear(mod);
mpz_clear(exp);
mpz_clear(n1);

return 1;
}

long long measureTime(mpz_t n, int repetitions)
{long long start = getTime();
solovay_strassen(n, repetitions);
long long end = getTime();

return end - start; // Time in microseconds
}

long long testPerformance(long long tests, intbit_count, int repetitions)
{
gmp_randstate_t RAND;
gmp_randinit_default(RAND);
gmp_randseed_ui(RAND, getTime());

mpz_t base;
mpz_init_set_ui(base, 1);
mpz_mul_2exp(base, base,bit_count-1); // base = 2^(bit_count-1)

mpz_t n;
mpz_init(n);
long long time = 0;
int test;
for (test = 0; test < tests; test++) {
mpz_urandomb(n, RAND, bit_count-1);
mpz_add(n, n, base); // n...