Re: bug in isprime()

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* 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]
`