I believe Pari uses Buchmann's algorithm, which is apparently not asymptotically slower as I stated. The paper I refer to is basically a version of this algorithm based on the quadratic sieve and should be much faster than Pari if implemented very well (in C).
Pari apparently implements algorithms of Hafner-McCurley, Buchmann and Cohen-Diaz-Olivier. One should also see the paper: http://www.math.u-bordeaux.fr/~belabas/pub/OnBach.pdf for an algorithm with a much lower bound than the original Bach bound used by the Buchmann algorithm. I have no idea whether this algorithm can be combined with the sieving algorithm which I linked in the previous post. However, all things being equal my bet is that the algorithm based on the quadratic sieve will be faster if the two cannot be combined. I shall now do some Magma and Pari timings, LiDIA essentially being uncooperative. 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/ -~----------~----~----~----~------~----~------~--~---
