Williams's p + 1 algorithm

<h2 id="algorithm">Algorithm</h2>
Choose some integer A greater than 2 which characterizes the <a href="/facts/Lucas_sequence/kceqhe6X">Lucas sequence</a>:

V
          
            0
          
        
        =
        2
        ,
        
          V
          
            1
          
        
        =
        A
        ,
        
          V
          
            j
          
        
        =
        A
        
          V
          
            j
            −
            1
          
        
        −
        
          V
          
            j
            −
            2
          
        
      
    
    {\displaystyle V_{0}=2,V_{1}=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
 )
 
 
 {\displaystyle \gcd(N,V_{M}-2)}
 
 whenever M is a multiple of 
 
 
 
 p
 −
 (
 D
 
 /
 
 p
 )
 
 
 {\displaystyle p-(D/p)}
 
, where

D
        =
        
          A
          
            2
          
        
        −
        4
      
    
    {\displaystyle D=A^{2}-4}
  
 and

(
 D
 
 /
 
 p
 )
 
 
 {\displaystyle (D/p)}
 
 is the <a href="/facts/Jacobi_symbol/lHlojG0o">Jacobi symbol</a>.
We require that 
 
 
 
 (
 D
 
 /
 
 p
 )
 =
 −
 1
 
 
 {\displaystyle (D/p)=-1}
 
, that is, D should be a <a href="/facts/Quadratic_non-residue/rHD2uQdQ">quadratic non-residue</a> 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
 
 
 {\displaystyle (D/p)=+1}
 
, this algorithm degenerates into a slow version of <a href="/facts/Pollard%2527s_p_-_1_algorithm/dITySRp5">Pollard's p − 1 algorithm</a>.
So, for different values of M we calculate 
 
 
 
 gcd
 (
 N
 ,
 
 V
 
 M
 
 
 −
 2
 )
 
 
 {\displaystyle \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
 
 
 
 
 {\displaystyle V_{M}}
 
 is the M-th value of the sequence characterized by 
 
 
 
 
 V
 
 M
 −
 1
 
 
 
 
 {\displaystyle 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 do
 if the bit is 1 then
 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

<h2 id="example">Example</h2>
With N=112729 and A=5, successive values of 
 
 
 
 
 V
 
 M
 
 
 
 
 {\displaystyle V_{M}}
 
 are:

V1 of seq(5) = V1! of seq(5) = 5
V2 of seq(5) = V2! of seq(5) = 23
V3 of seq(23) = V3! of seq(5) = 12098
V4 of seq(12098) = V4! of seq(5) = 87680
V5 of seq(87680) = V5! of seq(5) = 53242
V6 of seq(53242) = V6! of seq(5) = 27666
V7 of seq(27666) = V7! 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 = 22 × 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:

V1 of seq(9) = V1! of seq(9) = 9
V2 of seq(9) = V2! of seq(9) = 79
V3 of seq(79) = V3! of seq(9) = 41886
V4 of seq(41886) = V4! of seq(9) = 79378
V5 of seq(79378) = V5! of seq(9) = 1934
V6 of seq(1934) = V6! of seq(9) = 10582
V7 of seq(10582) = V7! of seq(9) = 84241
V8 of seq(84241) = V8! of seq(9) = 93973
V9 of seq(93973) = V9! 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 × 34. 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 do not know in advance whether the prime that will be found has a smooth p+1 or p−1.

<h2 id="generalization">Generalization</h2>
Based on <a href="/facts/Pollard%2527s_p_%25E2%2588%2592_1_algorithm/dITySRp5">Pollard's p − 1</a> and Williams's p+1 factoring algorithms, Eric Bach and Jeffrey Shallit developed techniques to factor n efficiently provided that it has a prime factor p such that any kth <a href="/facts/Cyclotomic_polynomial/TsWXDHIp">cyclotomic polynomial</a> Φk(p) is <a href="/facts/Smooth_number/pC6DVLJW">smooth</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
The first few cyclotomic polynomials are given by the sequence Φ1(p) = p−1, Φ2(p) = p+1, Φ3(p) = p2+p+1, and Φ4(p) = p2+1.

<ul><li>Williams, H. C. (1982), "A p+1 method of factoring", Mathematics of Computation, 39 (159): 225–234, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2007633">10.2307/2007633</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2007633">2007633</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0658227">0658227</a></li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://rieselprime.de/ziki/P%2B1_factorization_method">P + 1 factorization method</a> at Prime Wiki</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Bach, Eric; Shallit, Jeffrey (1989). "Factoring with Cyclotomic Polynomials" (PDF). Mathematics of Computation. 52 (185). American Mathematical Society: 201–219. doi:10.1090/S0025-5718-1989-0947467-1. JSTOR 2008664. <a href="http://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989-0947467-1/S0025-5718-1989-0947467-1.pdf" target="_blank">http://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989-0947467-1/S0025-5718-1989-0947467-1.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Williams's p + 1 algorithm open-in-new

Williams's p + 1 algorithm