These numbers can be factored in O(log n) time by iterating over their multiplicative Sylow psubgroups.
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 2subgroup.
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 2subgroup. 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.
