# Re: Question about the efficiency of integer factorization algorithms

*From*: Bryan <bryanjugglercryptographer@xxxxxxxxx>*Date*: Sat, 22 Jan 2011 05:40:35 -0800 (PST)

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()

.

**References**:

- Prev by Date:
**Chaocipher Exhibit 4 Challenge solved.** - Next by Date:
**Re: mp_montgomery_reduce Bug?** - Previous by thread:
**Re: Question about the efficiency of integer factorization algorithms** - Next by thread:
**P == NP** - Index(es):