I have written a code in C that basically makes a list of all the prime factors of a huge number, which is stored using the gmp
library. Here it is :
int is_div(mpz_t number, mpz_t i) {
return mpz_divisible_p(number,i)!=0;
}
mpz_t * prime_divs(mpz_t number){
mpz_t * prime_dividers = NULL;
mpz_t i, i_squared,TWO, comp;
mpz_inits(i, i_squared, TWO, comp, NULL);
mpz_set_ui(i,2);
mpz_mul(i_squared, i ,TWO);
while(mpz_cmp(i_squared,number)<=0){
if(is_div(number,i)){
mpz_fdiv_q(comp, number, i);
if(is_prime(i)) append(&prime_dividers,i);
if(is_prime(comp)) append(&prime_dividers,comp);
}
mpz_add_ui(i,i,1);
mpz_mul(i_squared, i ,i);
}
mpz_clears(i, i_squared, TWO, comp, NULL);
return prime_dividers;
}
Note that the function int is_prime(mpz_t n)
is not defined here because it is quite long. Just know that it is an implementation of a deterministic variant (up to 3,317,044,064,679,887,385,961,981) of Miller-Rabin's primality test. Same goes for the function void append(mpz_t** arr, mpz_t i)
, it is just a function that appends it to a list.
So my prime_divs
function searches for all integers i
in the range [2,sqrt(number)]
which divide number
. If it is the case, it then calculates it's complementary divisor (i.e. number/i
) and determines if any of them are primes. Would these integers be prime, then they would be appended to a list using append
.
Is there any way to makeprime_divs
faster?
[2, sqrt(number)]
probably negates whatever efficiency you're gaining by using M-R. You should at least restrict the loop to only odd numbers, since the only even prime is2
.factorize.c
, in the demos directory, that implements Pollard's rho algorithm. This isn't the fastest known algorithm for factoring large integers, but it's a lot easier to understand than the newer ones.