Here is a (probably not comprehensive list) of functions in NTL which allow or use probabilistic strategies with a probability of incorrect results:
GF2EX::ProbMinPolyMod GF2EXFactoring::ProbIrredTest lzz_pX::ProbMinPolyMod lzz_pXFactoring::ProbIrredTest lzz_pXFactoring::ProbComputeDegree lzz_pEX::ProbMinPolyMod lzz_pEXFactoring::ProbIrredTest mat_ZZ::determinant mat_ZZ::solve mat_ZZ::inv ZZ::GenPrime ZZ::GenPrime_ZZ ZZ::GenGermainPrime_ZZ ZZ::GenGermainPrime ZZ::RandomPrime ZZ::RandomPrime_ZZ ZZ::RandomPrime_long ZZ::NextPrime ZZ_pEX::ProbMinPolyMod ZZ_pEXFactoring::ProbIrredTest ZZ_pX::ProbMinPolyMod ZZ_pXFactoring::ProbIrredTest ZZ_pXFactoring::ProbComputeDegree ZZX::XGCD ZZX::resultant ZZX::NormMod ZZX::CharPolyMod ZZX::MinPolyMod More than likely SAGE doesn't use many of them and probably none directly. The ones that worry me the most are the primality tests since these are used elsewhere in NTL. Even polynomial multiplication makes use of primes in its multimodular methods. However I think this can't be a problem in practice because of the way that the modular inversion code operates. Pari uses GRH in quadclassunit and this function can't be certified. The function which computes the Hilbert class field of totally real fields is also dependent on the Stark conjectures. Of course bnrstark is too, but I don't think this last one is a problem. Surprisingly this looks like about it for Pari. Not too devastating it seems. I'm not familiar enough with any of the other packages SAGE uses to say anything about them. I think I shall now get back to timing number field computations. I intend to: 1) Finish timing Pari without certification and Magma with the "Pari" option set 2) Time Pari with certification and similarly Magma with full proof level of certification 3) Try to find a way to get Pari to compute a class group given an LLL reduced basis for the maximal order of a number field as Nils suggested be done with Magma. If I am able to, I will give comparative times for both programs. 4) Time computation of fundamental units, checking whether ideals are principal, factoring ideals and computing maximal orders. 5) Add LiDIA times for the above. 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/ -~----------~----~----~----~------~----~------~--~---
