Pollard's p -1 method
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 .
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 :
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:
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
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.
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
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 .
In total, three cases can arise in the end:
- 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.
- 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 .
- 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.
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.
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 .
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.
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
- (more precisely: the rest of this number modulo )
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.
Let the difference between the -th and the -th prime number in . Again you replace the numbers in each step with their remainder modulo .
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 .
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.
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
Let it be the greatest prime divisor of . Then:
Solving this equation for yields:
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.
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
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 :
As in the description of the 1st phase (see above) one obtains from this for an even number :
The number here is the same as that calculated in the 1st phase.
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 .
In practice, one sets a value for and, conversely, concludes for which values of this limit is sufficient. The following applies here:
If you give yourself the limit , you can use it to treat all who are less than or equal to.
Complexity of the procedure
The estimation results in a complexity of the procedure of:
The effort increases exponentially with the length of the input.
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 .
- G. Tenenbaum: Introduction to Analytic and Probabilistic Number Theory . P. 41, Th. 6.