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        ms2 (mod n)
4        if ISSQUARE(m) then
5            t ← √m
6            return GCD(n, st)
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.

About these ads

Pages: 1 2

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

  1. Mike said

    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:

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: