Programming Praxis

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₀ = 2, V₁ = 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² − 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_kn and 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₁-smooth except for a single prime factor in the range B₁ to B₂. 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_n for each k divisible by 6 between B₁ and B₂, 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.

Pages: 1 2