On 7 Sep, 08:55, "John Cremona" <[EMAIL PROTECTED]> wrote:
> The pari manual says (about factor(x)):
>
> If $x$ is of type integer or rational, the factors are \var{pseudoprimes}
> (see \kbd{ispseudoprime}), and in general not rigorously proven primes. In
> fact, any factor which is $\leq 10^{15}$ is a genuine prime number. Use
> \kbd{isprime} to prove primality of other factors,
>
> I would need to change the mwrank code to test "primes" > 10^15 for
> primality as recommended. A better solution would be to ask the pari
> developers to add an optional "proof=true" flag to factor() which does
> the isprime() calls automatically. I will do that.
I examined their quadratic sieve code and after splitting N it checks
the factors it has found to see if they are probable primes (17 rounds
of Miller-Rabin).
In other words it doesn't call the Pari isprime function, nor does it
try to factor these factors.
What you suggest would work, so long as they then attempt to factor
factors which fail the primality test. The quadratic sieve is
probabilistic and consecutive calls to it give additional chances to
factor the numbers being sent to it, so it's not possible to get an
infinite loop doing this. The same can be said of the elliptic curve
method I believe.
Actually the Pari quadratic sieve can eventually give up on factoring
a number, but probably it hasn't ever happened though. The probability
is probably less than 1 in 10^12 and if you are a being who has time
to factor 10^12 numbers using the quadratic sieve then you don't need
a computer to test primality for you (nor would you want it to, since
the failure rate of the machine itself would dominate your error
rate).
Bill.
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
