 Williams' p + 1 algorithm

In computational number theory, Williams' p + 1 algorithm is an integer factorization algorithm, one of the family of algebraicgroup factorisation algorithms. It was invented by Hugh 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
Algorithm
Choose some integer A greater than 2 which characterizes the Lucas sequence:
 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) whenever M is a multiple of p − (D / p), where D = A^{2} − 4 and (D / p) is the Jacobi symbol.
We require that (D / p) = − 1, that is, D should be a quadratic nonresidue 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 nontrivial factor of N.
The values of M used are successive factorials, and V_{M} is the Mth value of the sequence characterized by V_{M − 1}.
To find the Mth element V of the sequence characterized by B, we proceed in a manner similar to lefttoright exponentiation:
x=B y=(B^22) mod N for each bit of M to the right of the most significant bit if the bit is 1 x=(x*yB) mod N y=(y^22) mod N else y=(x*yB) mod N x=(x^22) mod N V=x
Example
With N=112729 and A=5, successive values of V_{M} are:
 V_{1} of seq(5) = V_{1!} of seq(5) = 5
 V_{2} of seq(5) = V_{2!} of seq(5) = 23
 V_{3} of seq(23) = V_{3!} of seq(5) = 12098
 V_{4} of seq(12098) = V_{4!} of seq(5) = 87680
 V_{5} of seq(87680) = V_{5!} of seq(5) = 53242
 V_{6} of seq(53242) = V_{6!} of seq(5) = 27666
 V_{7} of seq(27666) = V_{7!} of seq(5) = 110229.
At this point, gcd(1102292,112729) = 139, so 139 is a nontrivial factor of 112729. Notice that p+1 = 140 = 2^{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_{1} of seq(9) = V_{1!} of seq(9) = 9
 V_{2} of seq(9) = V_{2!} of seq(9) = 79
 V_{3} of seq(79) = V_{3!} of seq(9) = 41886
 V_{4} of seq(41886) = V_{4!} of seq(9) = 79378
 V_{5} of seq(79378) = V_{5!} of seq(9) = 1934
 V_{6} of seq(1934) = V_{6!} of seq(9) = 10582
 V_{7} of seq(10582) = V_{7!} of seq(9) = 84241
 V_{8} of seq(84241) = V_{8!} of seq(9) = 93973
 V_{9} of seq(93973) = V_{9!} of seq(9) = 91645.
At this point gcd(916452,112729) = 811, so 811 is a nontrivial factor of 112729. Notice that p1 = 810 = 2 × 5 × 3^{4}. 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 p1 = 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 p1.
Generalization
Based on Pollard's p1 and Williams' p+1 factoring algorithms, Eric Bach and Jeffrey Shallit developed techniques to factor n efficiently provided that is has a prime factor p such that any k^{th} cyclotomic polynomial Φ_{k}(p) is smooth.^{[1]} The first few cyclotomic polynomials are given by the sequence Φ_{1}(p) = p1, Φ_{2}(p) = p+1, Φ_{3}(p) = p^{2}+p+1, and Φ_{4}(p) = p^{2}+1.
References
 ^ Bach, Eric; Shallit, Jeffrey (1989). "Factoring with Cyclotomic Polynomials". Mathematics of Computation (American Mathematical Society) 52 (185): 201–219. JSTOR 2008664.
 Williams, H. C. (1982), "A p+1 method of factoring", Mathematics of Computation 39 (159): 225–234, doi:10.2307/2007633, MR0658227
External links
 P Plus 1 Factorization Method, MersenneWiki.
Primality tests AKS · APR · Baillie–PSW · ECPP · Elliptic curve · Pocklington · Fermat · Lucas · Lucas–Lehmer · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay–Strassen · Miller–Rabin · Trial divisionSieving algorithms 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'sMultiplication algorithms Ancient Egyptian multiplication · Karatsuba algorithm · Toom–Cook multiplication · Schönhage–Strassen algorithm · Fürer's algorithmDiscrete logarithm algorithms Babystep giantstep · Pollard rho · Pollard kangaroo · Pohlig–Hellman · Index calculus · Function field sieveGCD algorithms Modular square root algorithms Cipolla · Pocklington's · Tonelli–ShanksOther algorithms Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests (current article is always in bold).Categories: Integer factorization algorithms
Wikimedia Foundation. 2010.
Look at other dictionaries:
Nearestneighbor chain algorithm — In the theory of cluster analysis, the nearest neighbor chain algorithm is a method that can be used to perform several types of agglomerative hierarchical clustering, using an amount of memory that is linear in the number of points to be… … Wikipedia
Ross Williams — infobox person name=Ross Williams birth place = Melbourne, Victoria, Australia nationality = AustralianRoss Neil Williams is an Australian computer scientist and entrepreneur who has made significant contributions to data compression and… … Wikipedia
Integer factorization — In number theory, integer factorization is the way of breaking down a composite number into smaller non trivial divisors, which when multiplied together equal the original integer.When the numbers are very large, no efficient integer… … Wikipedia
Semiprime — In mathematics, a semiprime (also called biprime or 2 almost prime, or pq number) is a natural number that is the product of two (not necessarily distinct) prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ...… … Wikipedia
List of mathematics articles (W) — NOTOC Wad Wadge hierarchy Wagstaff prime Wald test Wald Wolfowitz runs test Wald s equation Waldhausen category Wall Sun Sun prime Wallenius noncentral hypergeometric distribution Wallis product Wallman compactification Wallpaper group Walrasian… … Wikipedia
Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… … Wikipedia
Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… … Wikipedia
Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… … Wikipedia
Digg — Digg, Inc. Type Private Founded San Francisco, California, United States[1] … Wikipedia
Algorithme de Grover — En informatique quantique, l´algorithme de Grover est un algorithme de recherche, permettant de rechercher un ou plusieurs éléments qui répondent à un critère donné parmi N éléments non classés en temps proportionnel à et avec un espace de… … Wikipédia en Français