Pollard's p  -1 method

The Pollard- p  - 1 method is a method for factorization of composite numbers . It was described by John M. Pollard in 1974 .

Mathematical basics

The -Faktorisierungsmethode Pollard is based on the small Fermat's theorem . Let be a prime number and a number that is not divided by then holds ${\displaystyle p-1}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$.

The same then applies to all multiples of . That means that is a multiple of . If a number to be factored has an (unknown) prime divisor , it divides the , since it divides both numbers from which the gcd was formed. Usually this GCD is a real factor of . The following paragraph describes one method of finding a suitable number . ${\displaystyle a^{m}\equiv 1{\pmod {p}}}$ ${\displaystyle m}$ ${\displaystyle p-1}$ ${\displaystyle a^{m}-1}$ ${\displaystyle p}$ ${\displaystyle N}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \operatorname {ggT} (a^{m}-1,N)}$ ${\displaystyle N}$ ${\displaystyle m}$

The 1st phase of the procedure

Now be given a natural number to be factored . In particular, let it be a composite number. One chooses a number that is relatively prime too . Using a heuristic , one determines another number , of which one assumes that for every prime divisor of the number - is power smooth . That is, for every prime divisor of : ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle B}$ ${\displaystyle p}$ ${\displaystyle N}$ ${\displaystyle p-1}$ ${\displaystyle B}$ ${\displaystyle q}$ ${\displaystyle p-1}$

${\displaystyle q^{e_{q}\left(p-1\right)}\leq B}$

The number denotes the exponent of . It indicates how often the number appears in the prime factorization of . If the number in the inequality is replaced by any number with an even-power factor , the inequality remains true. Forming according to the exponent yields: ${\displaystyle e_{q}(p-1)}$ ${\displaystyle q}$ ${\displaystyle p-1}$ ${\displaystyle q}$ ${\displaystyle p-1}$ ${\displaystyle p-1}$ ${\displaystyle B}$ ${\displaystyle m}$ ${\displaystyle q}$

${\displaystyle e_{q}\left(m\right)\leq {\frac {\log B}{\log q}}}$

If and are selected, this formula gives a sharp upper limit for the exponent. If this is greater than the right-hand side of the inequality, then it is no longer -potential smooth. You bet now ${\displaystyle B}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle m}$ ${\displaystyle B}$

${\displaystyle f_{q}=\left\lfloor {\frac {\log B}{\log q}}\right\rfloor }$

This is the largest exponent that an even number can have. Next, you create a list in which the prime number occurs exactly times. The prime numbers in the list are numbered with, the number of list elements being from . The product of all numbers in is denoted by. According to the construction is -potential smooth. In fact , it's the largest even number. ${\displaystyle q}$ ${\displaystyle B}$ ${\displaystyle m}$ ${\displaystyle F}$ ${\displaystyle q}$ ${\displaystyle f_{q}}$ ${\displaystyle q_{1},q_{2},q_{3},\ldots ,q_{R}}$ ${\displaystyle R}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle B}$ ${\displaystyle B}$

If has at least one prime divisor with -power even, then is a multiple of this number . It is therefore (see previous paragraph) a real divisor of , or equal to . Usually a power of less than -th is enough to get a factor. The practical procedure is therefore as follows: Calculate iteratively ${\displaystyle N}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle B}$ ${\displaystyle M}$ ${\displaystyle p-1}$ ${\displaystyle \operatorname {ggT} (N,a^{M}-1)}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle M}$

${\displaystyle a_{1}=a}$

${\displaystyle a_{i+1}=a_{i}^{q_{i}}}$ For ${\displaystyle i=1,...,R}$

In each step, the potencies that occur are replaced by their remainder modulo . After a certain number of steps, e.g. B. the 20th, you check whether you have already found a divisor. That is, you look at . If this GCF is greater than 1, a divisor has been determined and the process is terminated; if the gcd is 1, you continue in steps of 20 until you have found or reached a factor . ${\displaystyle N}$ ${\displaystyle \operatorname {ggT} (a_{20}-1,N)}$ ${\displaystyle a_{R}=a^{M}}$

In total, three cases can arise in the end:

1. One finds a real divisor of . In this case the procedure was successful and it has been broken down into two factors. If necessary, the procedure can be applied again to these two numbers until one obtains the prime factorization of , or one of the factors from case 3 occurs. ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$
2. One finds the divisor of . This is not particularly likely, but it can happen. In this case it is advisable to choose a different value for . ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle a}$
3. One finds the divisor 1 of . In this case, the assumption was that there is a divider of are, for the is -potenzglatt wrong. In this case you should start the 2nd phase of the method. ${\displaystyle N}$ ${\displaystyle p}$ ${\displaystyle N}$ ${\displaystyle p-1}$ ${\displaystyle B}$ ${\displaystyle p-1}$

The 2nd phase of the procedure

If the procedure fails in the 1st phase, the cause is often that for the prime factors of , that . Where is B-smooth or even B-power smooth, and a prime number that is greater than . In other words: is not B- (power-) smooth because of a single prime factor. ${\displaystyle p}$ ${\displaystyle N}$ ${\displaystyle p-1=u\cdot l}$ ${\displaystyle u}$ ${\displaystyle l}$ ${\displaystyle B}$ ${\displaystyle p-1}$

A second bound is therefore chosen to “capture” the factor . should be chosen much larger than , but not larger than . Often one chooses in the range of . ${\displaystyle B_{1}}$ ${\displaystyle l}$ ${\displaystyle B_{1}}$ ${\displaystyle B}$ ${\displaystyle B^{2}}$ ${\displaystyle B_{1}}$ ${\displaystyle B^{\frac {4}{3}}}$

As in the first phase, the list of prime numbers between and is created. You save the first of these numbers as and enter the differences between neighboring prime numbers in the list. The number of elements of be . Note: For each of these differences is less than or equal to 200. So there are only a few and only small differences. ${\displaystyle F_{1}}$ ${\displaystyle B}$ ${\displaystyle B_{1}}$ ${\displaystyle l_{1}}$ ${\displaystyle F_{1}}$ ${\displaystyle S}$ ${\displaystyle B_{1}<20.000.000}$

The number that was calculated at the end of the 1st phase serves as the starting value for the 2nd phase . As a further preparation, calculate for each difference in the number ${\displaystyle a_{R}}$ ${\displaystyle d}$ ${\displaystyle F_{1}}$

${\displaystyle j_{d}=a_{R}^{d}}$(more precisely: the rest of this number modulo ) ${\displaystyle N}$

On the one hand only a few have to be calculated here, on the other hand only a small power is required. As in phase 1, you now start an iteration again. You can replace the time-consuming exponentiation with multiplications. ${\displaystyle j_{d}}$

${\displaystyle a_{R+1}=a_{R}^{l_{1}}}$

${\displaystyle a_{R+i}=a_{R+i-1}\cdot {j_{d}}_{i}=a_{R}^{l_{i-1}}\cdot a_{R}^{d_{i}}=a_{R}^{l_{i-1}+d_{i}}=a_{R}^{l_{i}}}$ For ${\displaystyle i=2,3,...,S}$

Let the difference between the -th and the -th prime number in . Again you replace the numbers in each step with their remainder modulo . ${\displaystyle d_{i}}$ ${\displaystyle (i-1)}$ ${\displaystyle i}$ ${\displaystyle F_{1}}$ ${\displaystyle N}$

Unlike in phase 1, it is not sufficient to form the after a fixed number of steps . Instead one has to accumulate the numbers ; H. one forms the product of all these numbers. This can be done in the course of the iteration above by using , and . By accumulating one achieves that prime factors of can also be found for which more than one prime factor of is greater than . ${\displaystyle \operatorname {ggT} (a_{R+i}-1,N)}$ ${\displaystyle a_{R+i}-1}$ ${\displaystyle z_{1}=a_{R+1}-1}$ ${\displaystyle z_{i}=z_{i-1}(a_{R+i}-1)}$ ${\displaystyle p}$ ${\displaystyle N}$ ${\displaystyle p-1}$ ${\displaystyle B}$

After a fixed number of steps, about every 20th, one forms . Again, the three cases that could occur at the end of phase 1 may end up. If the process fails, the barriers and can be increased and the process started again. However, it is better to use a different method in this case. ${\displaystyle \operatorname {ggT} (z_{i},N)}$ ${\displaystyle B}$ ${\displaystyle B_{1}}$

The heuristic of the greatest prime divisor

On average, a natural number has prime divisors. This statement can be precisely formulated and proven. One pretends to have the number of prime divisors of exactly this value, i. H. it is believed that ${\displaystyle m}$ ${\displaystyle \log \log m}$ ${\displaystyle m}$

${\displaystyle \omega \left(m\right)=\log \log m}$

Let it be the greatest prime divisor of . Then: ${\displaystyle q}$ ${\displaystyle m}$

${\displaystyle \omega \left({\frac {m}{q}}\right)=\omega (m)-1}$

Solving this equation for yields: ${\displaystyle q}$

${\displaystyle q=m^{1-{\frac {1}{e}}}}$

It is the Euler number . That is a heuristic reason that the greatest prime divisor of about is equal . This fact is used to determine a value for the search limit from the above method. ${\displaystyle e}$ ${\displaystyle m}$ ${\displaystyle m^{0{,}632}}$ ${\displaystyle B}$

Application to the procedure

Now be a composite natural number to which you want to apply the method. Since it is composite, it has a prime divisor . According to the heuristic, the greatest prime divisor of ${\displaystyle N}$ ${\displaystyle p-1}$ ${\displaystyle p\leq {\sqrt {N}}}$ ${\displaystyle q}$ ${\displaystyle p-1}$

${\displaystyle q\leq \left(p-1\right)^{1-{\frac {1}{e}}}\leq n^{{\frac {1}{2}}(1-{\frac {1}{e}})}\approx n^{0{,}316}}$

So if one chooses, one can expect that -smooth. The -potential smoothness can now be achieved as follows: Suppose it is -smooth. Then for all prime divisors of : ${\displaystyle B\geq N^{0{,}316}}$ ${\displaystyle p-1}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle p-1}$ ${\displaystyle B}$ ${\displaystyle q}$ ${\displaystyle p-1}$

${\displaystyle q^{e_{q}(p-1)}\leq n^{\frac {1}{2}}\leq B^{\frac {e}{e-1}}}$

As in the description of the 1st phase (see above) one obtains from this for an even number : ${\displaystyle B}$ ${\displaystyle m}$

${\displaystyle e_{q}(m)\leq \left\lfloor {\frac {e}{e-1}}{\frac {\log B}{\log q}}\right\rfloor \approx 1{,}6\cdot f_{q}}$

The number here is the same as that calculated in the 1st phase. ${\displaystyle f_{q}}$

That means: For this choice of you have to replace the values ​​of the with the slightly larger values ​​in order to achieve the smoothness of the potential . ${\displaystyle B}$ ${\displaystyle f_{q}}$ ${\displaystyle 1{,}6\cdot f_{q}}$ ${\displaystyle B}$ ${\displaystyle p-1}$

In practice, one sets a value for and, conversely, concludes for which values ​​of this limit is sufficient. The following applies here: ${\displaystyle B}$ ${\displaystyle N}$

${\displaystyle N\leq B^{2{\frac {e}{e-1}}}\approx B^{3{,}164}}$

If you give yourself the limit , you can use it to treat all who are less than or equal to. ${\displaystyle B=10.000}$ ${\displaystyle N}$ ${\displaystyle 4{,}5\cdot 10^{12}}$

Complexity of the procedure

The estimation results in a complexity of the procedure of: ${\displaystyle B\geq N^{0{,}316}}$

${\displaystyle O({\sqrt[{3}]{N}})}$

The effort increases exponentially with the length of the input.

Applications

The Pollard p  - 1 method is used by GIMPS (Great Internet Mersenne Prime Search), among others, to factor numbers of the shape and thus to reduce the number of time-consuming Lucas-Lehmer tests necessary to search for Mersenne prime numbers . ${\displaystyle 2^{p}-1}$

literature

• G. Tenenbaum: Introduction to Analytic and Probabilistic Number Theory . P. 41, Th. 6.