Thread: Fast isPrime() for n < 2^32 View Single Post
 2011-05-24, 16:57 #30 JohnFullspeed   May 2011 France 2418 Posts 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