Factoring integers
The difficulty of factoring is presumably related to the irregularity of the pattern of divisors shown on page 909. One approach to factoring a number n is just to try dividing it by each of the numbers up to √n. A sequence of much faster methods have however been developed over the past few decades, one simple example that works for most n being the so-called rho method of John Pollard (compare the quadratic residue sequences discussed below):
Module[{f = Mod[#2 + 1, n] &, a = 2, b = 5, c}, While[(c = GCD[n, a - b]) 1, {a, b} = {f[a], f[f[b]]}]; c]
Most existing methods depend on facts in number theory that are fairly easy to state, though implementing them for maximum efficiency tends to lead to complex programs. Typical running times for FactorInteger[n] in Mathematica 4 are shown below for the first 1000 numbers with each of 15 through 30 digits. Different current methods asymptotically require slightly different numbers of steps—but all typically at least Exp[Sqrt[Log[n]]]. Nevertheless, to test whether a number is prime (PrimeQ) it is known that only a few more than Log[n] steps suffice.