John Cremona on Fri, 07 Sep 2007 23:30:23 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: bug in isprime() |
Thanks for the clear explanation (I do know about Pocklington-L and so on). IN fact Bill Hart had already proposed this as the explanation to sage-dev. As you may have guessed, sage-dev are getting concerned about having all its results provably valid (possibly after turning on some "proof=trye switch). One such place is in class number computations (which Bill has been looking into in detail), the other is in prime factorizations. I would still like to have a "proof=true" flag in factorint() though. While I am here, can you tell me whether or not factor(n) and factorint(n) are the same for integers n? John On 9/7/07, Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> wrote: > * 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] > ` > -- John Cremona