Re: bug in isprime()

["John Cremona" <john.cremona@gmail.com>]

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