| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Brent-Suyama extension
The Brent-Suyama extension to the P-1 factorization method allows the possibility of finding factors outside the normal range expected from the P-1 bounds.
Recall that stage 1 computes S=3E where E is the product of prime powers less than B1. Then by Fermat's Little Theorem, a prime number p | S-1 if p-1 | E.
A naive stage 2 would then compute T=Sq = 3E*q for successive prime q in the range (B1,B2]. Then p | T-1 if p-1 | q*E.
Slicker would be to note that all primes > 3 are of form 6k+/-1. Suppose instead that we compute T=S(6k)2-1 = 3E*(6k-1)*(6k+1) whenever one of 6k+1 or 6k-1 is prime. If both are prime, then we get to include two for the price of one. Even if only one is prime, the other may be a multiple of some other prime > B1, so with a bit of planning, we may be able to skip that prime on the way up, and thus again get two for the price of one. This is called "prime pairing".
Brent-Suyama instead computes T=S(6k)e-1, where e is a small even number >2. (6k)e-1 = (6k-1)*(6k+1)*(a higher order polynomial in k). The algorithm will then find a factor p if the largest prime factor of p-1 is 6k-1, 6k+1, or if it is a factor of the higher order polynomial evaluated at some k between B1/6 and B2/6 - and all other factors of p-1 are below B1. It is this latter case, whether the relevant prime factor of the higher order polynomial happens to be > B2, that the additional factors are found.
Note that there is nothing special about the number 6, other than that it is a primorial. A larger primorial increases the proportion of primes that pair up, at the cost of having to consider a larger number of congruence classes "relatively prime" to it, and consequently a larger memory requirement. Prime95 uses 30, 210, or 2310 (depending upon the available memory).
E in the output equates to e in the above explanation: the Brent-Suyama exponent. The small primorial is d in the source code, but isn't directly indicated in the output. You can see its effect, though:
- [math]\displaystyle{ \phi(30) = 8 }[/math]
- [math]\displaystyle{ \phi(210)=48 }[/math]
- [math]\displaystyle{ \phi(2310)=480 }[/math]
Where [math]\displaystyle{ \phi(x) }[/math] is Euler's totient function - the number of congruences (mod x) which are relatively prime to x.
