Hart’s One-Line Factoring Algorithm

January 28, 2014

William Hart wrote, in one line of PARI, a function that factors integers. His method, which he gives in the form of a program, is a variant of Fermat’s method:

ONELINEFACTOR(n,iter)
1    for i ← 1 … iter do
2        s ← ⌈√ni⌉
3        m ← s2 (mod n)
4        if ISSQUARE(m) then
5            t ← √m
6            return GCD(n, s − t)
7        endif
8    endfor

Hart’s paper, which you should read, gives several optimizations. The algorithm works best when the two factors are near each other, so you should first perform trial division to n1/3, thus ensuring that there is a factor between n1/3 and n1/2, unless n is prime. The algorithm works well for semi-primes up to 1016 or 1018, and Hart claims it is faster than SQUFOF in that range.

Your task is to write a function that factors integers by Hart’s method. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
1 Comment »

One Response to “Hart’s One-Line Factoring Algorithm”

  1. Mike said
    January 28, 2014 at 11:16 PM

    Here’s a python version without the optimization:

    from math import ceil, sqrt
from utils import is_square, gcd     # my library of utilities

def OLF(n):
	for ni in range(n, n*n, n):
		cs = ceil(sqrt(ni))
		pcs = pow(cs, 2, n)
		if is_square(pcs):
			return gcd(n, floor(cs - sqrt(pcs)))

    or as a one-liner:

    
OLF = lambda x: next(gcd(x, floor(ceil(sqrt(ix)) - sqrt(ceil(sqrt(ix))**2 % x))) for ix in range(x, x*x, x) if is_square(ceil(sqrt(ix))**2 % x))

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: