Next: Primality Testing
Up: Prime Numbers
Previous: Largest Fermat number with
There are several known algorithms that have subexponential estimated
running time, to mention just a few:
- Continued fraction algorithm.
- Quadratic sieve algorithm.
- Class Group method.
- Elliptic curve algorithm.
- Number field sieve.
- Dixon's random squares algorithm.
- Valle's two-thirds algorithm.
- Seysen's class group algorithm.
A.K. Lenstra, H.W. Lenstra Jr. Algorithms in Number Theory. J. van Leeuwen (ed.), Handbook of Theoretical Computer
Science, Volume A: Algorithms and Complexity Elsevier, pp.
Mon Feb 23 16:26:48 EST 1998