View Single Post
Old 2011-05-24, 16:57   #30
May 2011

2418 Posts
Default 2^32 primes

Why are you not using an array with all the primes smaller tahnn2^32?
You have only 200 000 000 of primes so using a simple RLE the file
is 200 000 000 of byte

Two hours to compute the llst (i can give the file) and you can factorized
20 digits number in less than one minute.

For the classic m^k mod you can use a fast algo

function E_M(m, K, N: int64): int64;
var b, a: int64;
 b := 1;
 a := m;
 if odd(k) then
  b := A;
 k := k shr 1;
  A := (A * A) mod N;
  if odd(k) then
   b := (A * b) mod N;
  k := k shr 1;
 until k = 0;
 result := b;
It's also good for RSA encryption


Last fiddled with by JohnFullspeed on 2011-05-24 at 17:00
JohnFullspeed is offline   Reply With Quote