On 7 Sep, 02:21, "William Stein" <[EMAIL PROTECTED]> wrote:
> SAGE uses PARI. PARI claims to prove primality under no hypothesis
> "using a combination of algorithms" including Pocklington-Lehmer
> and APRCL.
OK. I certainly didn't know of this. That invalidates what I say about
Pari below. But it doesn't remove the objections regarding NTL which
only has access to its own primality tests and presumably those in
GMP.
I now see FLINT must prove primality. It currently doesn't (except up
to 10^16 for which it implements a very fast primality test which is
proven).
With regard to the new quadratic sieve, it is currently a problem. If
a large composite is proven prime, the sieve will never even see it,
so this is a problem (but not for the current version in SAGE which
relies on SAGE to test primality, not my sieve code). This will
certainly need fixing. Fortunately primality testing is a minute part
of the runtime in the sieve, so it won't impact the times I've been
getting.
Technically it is also a problem for the factor base generation in the
old version of the sieve which is in SAGE. But in fact the primes are
small enough that GMP is known to not pass composites. The new version
of the sieve uses the FLINT primality testing functions which are
proven to pass only primes of this size.
I'm glad I found out about this now though. This discussion has been
very worthwhile.
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/
-~----------~----~----~----~------~----~------~--~---
