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.
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. Is the GMP mpz_nextprime function or are any of the NTL primality testing functions used in SAGE? 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. Are there tables of number fields in SAGE? Were they computed assuming GRH? John Jones' tables were computed using Pari were they not? 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. I'm sure these examples can be multiplied ad inifinitum. So is the policy going to be that las vegas algorithms are allowed in SAGE but not monte carlo algorithms for default functionality? If so, I feel we have a lot of work to do. Bill. 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. --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
