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

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

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

John

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