These numbers can be factored in O(log n) time by iterating over their multiplicative Sylow p-subgroups.
Let n be an odd integer. Its maximal multiplicative order is n - 1; the largest power of 2 dividing n - 1 is o, the maximal order of its multiplicative Sylow 2-subgroup.
Let t = (n - 1) / o.
Pick random integers x and y such that the Jacobi symbols (x/n) and (y/n) are -1; that is, x and y are quadratic nonresidues modulo n. Exponentiate both by t to produce generators of the Sylow 2-subgroup. Retain the value of y as r.
Repeatedly multiply x by y and y by r, modulo n, giving a parabolic sequence of x values. A factor may be obtained from gcd(x - 1, n), gcd(y - 1, n), gcd(x - y, n), or gcd(x + y, n). If a factor is not found quickly, choose new values of x and y.
It is often the case that one iteration is sufficient, instead of log n iterations.
|