Re: Question about the efficiency of integer factorization algorithms

Scott Contini wrote:
These numbers can be
factored very quickly with Fermat's factoring method!
I'd have to search around for a good source but in
the mean time read first paragraph of section 2 of:
 http://arxiv.org/ftp/math/papers/0702/0702227.pdf

Below is code in current Python. It is eye-blink fast for n of two-
hundred digits, provided, of course, that |p - q| is in small. The
constraint in the opening post:

|p - q| < (p*q)**0.25

is so strong that Fermat's algorithm always finds a factor on the
first trial. We don't really need an algorithm, just a formula. Let

w = ceil(sqrt(n))

Now two factors are:

w - sqrt(w*w - n)

and

w + sqrt(w*w - n)


-Bryan Olson
-------------------------------------------------------


from __future__ import print_function


def ceiling_sqrt(n):
""" Return the least integer not less than the square root of n.
Newton's method, with lame initial estimate.
"""
assert n >= 0
est = 1
nest = (est + n // est) // 2
while abs(nest - est) >= 2:
est = nest
nest = (est + n // est) // 2
est = min(est, nest)
while est * est < n:
est += 1
return est


def is_square(n):
fs = ceiling_sqrt(n)
return fs * fs == n


def ffact(n):
""" Return a factor of positive odd integer n.
Fermat's method.
"""
assert n > 0 and n % 2 == 1
u = ceiling_sqrt(n)
v = u * u - n
while not is_square(v):
u += 1
v = u * u - n
return u - ceiling_sqrt(v)


def demo():
from random import SystemRandom
randrange = SystemRandom().randrange
p = randrange(10**100) * 2 + 1
q = (p + randrange(ceiling_sqrt(p))) | 1
n = p * q
print('p: %d\nq: %d\nn: %d\nFactoring...' % (p, q, n))
pp = ffact(n)
print('...Got factor:', pp)
assert n % pp == 0
print('Looks good.\n')

for _ in range(20):
demo()

.