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.

**References**

*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.
673-715, 1990.

Mon Feb 23 16:26:48 EST 1998