Factoring of integers

Given a number $X$ we want to find its prime factors. The ``trial division'' method tests all integers up to $\sqrt{X}$, requiring $\approx 2^{n/2}$ trials where $n$ is the bit-length of $X$. Several factoring algorithms are known which run in time $2^{c\sqrt{n\log n}}$. While this is still very far from polynomial time, it is significantly better than trial division. We shall see the idea.

Remark 0.1   The best factoring algorithm known, called the number field sieve, runs in time $2^{c\sqrt[3]{n\log^2n}}$ [Lenstra, Lenstra, Manasse and Pollard (1990)]. This statement is based on some plausible but unproven number theoretic assumptions (``heuristic analysis''). Given the significance of factoring integers, efficient factoring algorithms are of great interest even if we cannot rigorously prove their efficiency. Dixon's remains the only factoring algorithm with a fully proven $2^{c\sqrt{n\log n}}$ upper bound on its running time.