Karim Belabas on Sat, 08 Sep 2007 20:35:18 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: bug in isprime()


* Phil Carmody [2007-09-08 15:55]:
> --- Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> wrote:
> What I find odd is the following:
> 
> ? isprime(p)
> IFAC: cracking composite
>         507526619771207
>   *** isprime: Warning: IFAC: untested integer declared prime.
> IFAC: prime 507526619771207
>         appears with exponent = 1
> IFAC: found 1 large prime (power) factor.
> 1
> 
> 
> ? isprime(p,1)
> 
> [2 3 1]
> 
> [3 2 1]
> 
> [32839 2 1]
> 
> [507526619771207 2 1]
> 
> 
> ? isprime(p,2)
> Choosing t = 120
> 
> Jacobi sums and tables computed
> Step4: q-values (# = 8, largest = 61): 3 5 7 11 13 31 41 61 
> Step5: testing conditions lp
> Step6: testing potential divisors
> Individual Fermat powerings:
>   2  :   6
>   3  :   4
>   4  :   5
>   5  :   4
>   8  :   1
> Number of Fermat powerings = 21
> Maximal number of nondeterministic steps = 4
> 1
> 
> 
> So both of the individual proof techniques can proceed without a diagnostic,
> yet if the technique isn't specified, one is produced. I guess that's at the
> stage where it's trying to decide which of the two techniques to use.

Right. In this initial phase we remove "small" prime divisors
[ producing the diagnostic ]; if the (unfactored) cofactor happens to be
a strong pseudoprime, we go Pocklington-Lehmer (using the known prime
divisors). Otherwise APRCL.

    K.B.

P.S: For some reason, the current APRCL doesn't take into account the result
of N-1 tests [ the N+1 tests are only partially implemented, and not
taken into account either ]
--
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]
`