Infinite loop in mpz_probab_prime_p

[Torbjorn Granlund]

"Darin Ohashi" <darin242 at hotmail.com> writes:

  Yeah, I did some more experimentation overnight and found that eventually it
  did complete. As long as it is expected to take that long then it is not a
  bug.

It takes time O(n^2*log(n)), where n is the number of digits in the
number.  This means that doubling the number of digits more than
quadruples the run time.

I'd estimate that your number needs 2 to 3 hours (depending on CPU
clock) on an Athlon64 or Opteron in 64-bit mode.  Current Pentiums or
current 32-bit AMD processors will take perhaps 2-3 times longer.

  Did you add a check for the potential overflow from ln2 = ln2*ln2 ?
  For very very large integers this could be a problem.

That code is gone.  Note however that overflow in that expression
isn't going to cause any miscomputation; it will only affect
performance.

It is an interesting problem to look for small divisors; what
algorithm and and what limits to use.

--
Torbjörn