On 9/6/07, Bill Hart <[EMAIL PROTECTED]> wrote:
> While we are at it we should determine the default algorithm which
> SAGE uses for primality checking. If GMP is used for this then it is
> not guaranteed to only pass primes. It simply does a Fermat test and
> then a certain number of rounds of Miller-Rabin. Usually to make this
> practical GRH is assumed.
SAGE uses PARI. PARI claims to prove primality under no hypothesis
"using a combination of algorithms" including Pocklington-Lehmer
and APRCL.
> The NTL primality tests are also not guaranteed to pass only primes.
>
> Magma primality proving is said to be slow. Perhaps this is why.
>
> Pari is based on GMP. We better check all algorithms in both NTL and
> Pari which are used in SAGE which rely on primality to return correct
> results.
PARI implements their own primality test. I think they only use GMP
here for arithmetic, not for their primaility test. SAGE doesn't use
NTL's primality test at all -- at least not in the is_prime function.
> Is the GMP mpz_nextprime function or are any of the NTL primality
> testing functions used in SAGE?
SAGE uses a "proof=True" next_prime function based on pari.
There was a lot of discussion about this on sage-devel about 2
months ago, when we learned that pari's default "nextprime" function
is proof=False.
> Are there other algorithms available in SAGE from Pari that rely on
> conjectures? This would include the stuff for totally real fields that
> relies on the Stark conjectures.
None of this is directly exposed in the SAGE number fields interface.
Stuff that you get via gp('..') or pari('..'), i.e., directly calling out
to other programs -- for that -- all bets are off, and that's the way
it should be.
> Are there tables of number fields in SAGE?
Yes.
> Were they computed assuming
> GRH?
No clue. Probably.
> John Jones' tables were computed using Pari were they not?
The only tables in SAGE of number fields now are John Jones's.
I don't know how they were computed.
> My quadratic sieve, as does Pari's relies on numbers being fed to it
> not being prime. Thus a test is performed to assume they are not. This
> test is not guaranteed to pass only primes. This means my quadratic
> sieve is not reliable. The same goes for the one in Pari. I wonder if
> the Magma quadratic sieve has the same problem.
Is that really a problem? I mean, you know for a fact the input is
an integer that is composite. If your sieve splits it we're happy.
If it doesn't, we try again.
> I'm sure these examples can be multiplied ad inifinitum.
I'm really glad you're thinking about such things in the context of
SAGE. It's sort of analogous to high Michael Abshoff is auditing memory
leaks in SAGE right now.
> So is the policy going to be that las vegas algorithms are allowed in
> SAGE but not monte carlo algorithms for default functionality?
Yes. That's only the *default*, and that's only for top level exposed
functionality. Also, I think there should be a global proof=False
flag
in all SAGE that changes these assumptions.
> If so, I feel we have a lot of work to do.
We have a lot of work to do no matter what. Let's do it! :-)
William
>
> On 7 Sep, 01:08, Bill Hart <[EMAIL PROTECTED]> wrote:
> > The question is, which algorithm does SAGE currently use? Does it
> > really provide a proven result? Is it proven to terminate? Can it
> > provide a certificate that I can check in less time than doing the
> > computation again? How can I be sure the result is valid?
> >
> > Anyhow, whatever algorithm or level of rigour is used, it is clear we
> > need to make it *much* faster. That's the problem I'm most interested
> > in of course.
> >
> > Bill.
>
>
> >
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://www.williamstein.org
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
