## Williams’ *P*+1 Factorization Algorithm

### June 4, 2010

Hugh Williams invented the *p*+1 integer factorization method in 1982 based on John Pollard’s *p*-1 integer factorization method; the *p*+1 method finds a factor *p* when *p* is smooth with respect to a bound *B*. We noted in a previous exercise the similar structure of Pollard’s *p*-1 method and Lenstra’s elliptic curve method, and Williams’ *p*+1 method shares the same two-stage structure; Pollard’s *p*-1 method performs multiplications modulo *p*, Lenstra’s elliptic curve method performs multiplications over an elliptic curve, and Williams’ *p*+1 method performs multiplications over a quadratic field using Lucas sequences (similar to the Lucas chain in the Baillie-Wagstaff primality-testing exercise). A good description of Williams’ *p*+1 method is given at http://www.mersennewiki.org/index.php/P_Plus_1_Factorization_Method.

Williams’ *p*+1 method uses the Lucas sequence *V*_{0} = 2, *V*_{1} = *A*, *V _{j}* =

*A*·

*V*

_{j−1}−

*V*

_{j−2}, with all operations modulo

*N*, where

*A*is an integer greater than 2. Multiplication by successive prime powers is done as in Pollard’s

*p*-1 algorithm; when all the products to the bound

*B*are accumulated, the greatest common divisor of

*N*and the result

*V*

_{B}− 2 may be a divisor of

*N*if all the factors of

*p*+1 are less than

*B*. However, if

*A*

^{2}− 4 is a quadratic non-residue of

*p*, the calculation will fail, so several attempts must be made with different values of

*A*before concluding that

*p*+1 is not

*B*-smooth.

Given the addition formula *V*_{m+n} = *V _{m}*

*V*−

_{n}*V*

_{m−n}and the doubling formula

*V*

_{2m}=

*V*

_{m}×

*V*

_{m}− 2, multiplication is done by means of a Lucas sequence that computes two values at a time. Starting with the pair

*V*and

_{kn}*V*

_{(k+1)n}, and looking at the bits in the binary representation of the multiplier

*M*, excluding the most significant bit (which is always 1) and working from most significant to least significant, calculate the pair

*V*,

_{2kn}*V*

_{(2k+1)n}when the bit is zero and the pair

*V*

_{(2k+1)n},

*V*

_{2(k+1)n}when the bit is one.

The second stage finds factors that are *B*_{1}-smooth except for a single prime factor in the range *B*_{1} to *B*_{2}. It can be done in a similar manner to the second stage of Pollard’s *p*-1 method, but a little bit of algebra gives us a better second stage. Assuming that *V _{n}* is the point that survives the first stage, multiply the products

*V*−

_{k}*V*for each

_{n}*k*divisible by 6 between

*B*

_{1}and

*B*

_{2}, then take the greatest common divisor of the product with

*n*to reveal the factor.

Your task is to write a program that factors integers using Williams’ *p*+1 algorithm. 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.

Hello, what is the ilog function?

@Ruslan: The integer logarithm (ilog) of

nto the basebis the largest integeresuch thatb≤^{e}n. You can see an implementation by clicking to run the code.