Karim Belabas on Fri, 07 Sep 2007 22:52:06 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: bug in isprime() |
* John Cremona [2007-09-07 21:57]: [...] > the manual claims that while the out of factor() contains "primes" > which are not proved primes, the function isprime() provides a proof > of primality. In which case what is going on here: > > ? default(debug,2) > %5 = 2 > ? p=nextprime(10^20) > %6 = 100000000000000000039 > ? isprime(p) > *** isprime: Warning: IFAC: untested integer declared prime. > 507526619771207 > %7 = 1 > > It seems that part of the "proof" involves a factorization whose > results are not proved. Your guess is correct. You may remove the quotes around "proof", though. The traditional Pocklington-Lehmer primality proof [ or Brillhart-Lehmer-Selfridge, or Pomerance- Konyagin, or lattice reduction-based generalizations (the latter two not implemented) ... ] all start by factoring p - 1 = F U, where -- F(actored) is fully factored with proven prime divisors [ a few simple congruences are checked at this point ] -- U(nfactored) is arbitrary but not much biger than F Here, -- F = 2 * 3 * 32839 [ all 3 easily proven primes ] -- U = 507526619771207 is in fact prime, but we don't know that at the time the diagnostic is output. -- Unfortunately U is slightly too big to apply a direct Brillhart-Lehmer-Selfridge [ it would be OK for the more advanced ones, not implemented, as I said ]. -- So we attempt a primality proof of U, which fortunately succeeds. Now, we have -- F = 2 * 3 * 32839 * 507526619771207 -- U = 1, suitably small. And we are done. > Unless I am misunderstanding what the manual claims, this means that > it is _not_ doing what is claimed. You understood the manual, but misunderstood the diagnostics output at \g2. This will go into the FAQ when I get some spare time... Cheers, K.B. P.S: Feel free to suggest explicit improvements to the documentation or the FAQ. I'll be more than happy to include submitted paragraphs to the above documents. -- Karim Belabas Tel: (+33) (0)5 40 00 26 17 Universite Bordeaux 1 Fax: (+33) (0)5 40 00 69 50 351, cours de la Liberation http://www.math.u-bordeaux.fr/~belabas/ F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP] `