Williams' p + 1 algorithm

From Wikipedia, the free encyclopedia

In computational number theory, Williams' p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic-group factorisation algorithms. It was invented by H. C. Williams in 1982.

It works well if the number N to be factored contains one or more prime factors p such that

p + 1

is smooth, i.e. p + 1 contains only small factors. It uses Lucas sequences to perform exponentiation in a quadratic field.

It is analogous to Pollard's p − 1 algorithm.

Contents 1 Algorithm 2 Example 3 References 4 External links

[edit] Algorithm

Choose some integer A greater than 2 which characterizes the sequence:

V₀ = 2,V₁ = A,V_j = AV_{j − 1} − V_{j − 2}

where all operations are performed modulo N.

Then any odd prime p divides gcd(N,V_M − 2) whenever M is a multiple of p − (D / p), where D = A² − 4 and (D / p) is the Jacobi symbol.

We require that (D / p) = − 1, that is, D should be a quadratic non-residue modulo p. But as we don't know p beforehand, more than one value of A may be required before finding a solution. If (D / p) = + 1, this algorithm degenerates into a slow version of Pollard's p − 1 algorithm.

So, for different values of M we calculate gcd(N,V_M − 2), and when the result is not equal to 1 or to N, we have found a non-trivial factor of N.

The values of M used are successive factorials, and V_M is the M-th value of the sequence characterized by V_{M − 1}.

To find the M-th element V of the sequence characterized by B, we proceed in a manner similar to left-to-right exponentiation:

 x=B           
 y=(B^2-2) mod N     
 for each bit of M to the right of the most significant bit
   if the bit is 1
     x=(x*y-B) mod N 
     y=(y^2-2) mod N 
   else
     y=(x*y-B) mod N 
     x=(x^2-2) mod N 
 V=x

[edit] Example

With N=112729 and A=5, successive values of V_M are:

V₁ of seq(5) = V_1! of seq(5) = 5

V₂ of seq(5) = V_2! of seq(5) = 23

V₃ of seq(23) = V_3! of seq(5) = 12098

V₄ of seq(12098) = V_4! of seq(5) = 87680

V₅ of seq(87680) = V_5! of seq(5) = 53242

V₆ of seq(53242) = V_6! of seq(5) = 27666

V₇ of seq(27666) = V_7! of seq(5) = 110229

At this point, gcd(110229-2,112729) = 139, so 139 is a non-trivial factor of 112729. Notice that p+1 = 140 = 2 × 5 × 7. The number 7! is the lowest factorial which is multiple of 140, so the proper factor 139 is found in this step.

Using another initial value, say A = 9, we get:

V₁ of seq(9) = V_1! of seq(9) = 9

V₂ of seq(9) = V_2! of seq(9) = 79

V₃ of seq(79) = V_3! of seq(9) = 41886

V₄ of seq(41886) = V_4! of seq(9) = 79378

V₅ of seq(79378) = V_5! of seq(9) = 1934

V₆ of seq(1934) = V_6! of seq(9) = 10582

V₇ of seq(10582) = V_7! of seq(9) = 84241

V₈ of seq(84241) = V_8! of seq(9) = 93973

V₉ of seq(93973) = V_9! of seq(9) = 91645

At this point gcd(91645-2,112729) = 811, so 811 is a non-trivial factor of 112729. Notice that p-1 = 810 = 2 × 5 × 3⁴. The number 9! is the lowest factorial which is multiple of 810, so the proper factor 811 is found in this step. The factor 139 is not found this time because p-1 = 138 = 2 × 3 × 23 which is not a divisor of 9!

As can be seen in these examples we don't know in advance whether the prime that will be found has a smooth p+1 or p-1.

[edit] References

H.C. Williams, A p+1 method of factoring, Math. Comp., 39, 225-234 (1982)

[edit] External links

• http://www.mersennewiki.org/index.php/P_Plus_1 MersenneWiki article about p+1 factorization method.

v • d • e Number-theoretic algorithms Primality tests AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division Sieving algorithms Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm Other algorithms Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.