mpz_probab_prime_p(n, reps) : how long?

[Torbjorn Granlund]

"jojo 29" <jojo29118 at hotmail.com> writes:

  Someone wrote me that my mpz_probab_prime_p() function (33 million digits
  number, 10 iterations) needs few months only, with a Pentium 4. So... I
  don't know who is right...

That someone probably has a very powerful processor, if he can
run mpz_probab_prime_p a thousand times faster than the rest of
us.

  What calculations did you make to determine that my mpz_probab_prime_p()
  function needs "100 years"?

I made some measurements of basic multiplication and division.
Then multiplied that by the number of bits in your number.  On my
2.2 GHz Athlon system that would mean close to 200 years.  A
highend 64-bit Athlon would need around 100 years.

I need to correct my previous claim about the complexity of GMP's
implementation.  The right formula is:

     2   2
  O(n log n)

The extra log factor comes from division.  Division is not is not
asymptotically optimal.  There are plans for better division in
GMP 5, but we have only began implementing it.  Once done, your
computation should become about 180 years faster, to leave only
about 20 years.  :-)

You cannot compare Miller Rabin with the Lucas test used for
Mersenne prime testing.  The latter is several times faster.  And
GIMPS is several times faster than GMP for huge number
arithmetic.

--
Torbjörn