CODEWITHSUNDEEP
prime-factoringfactorization
noman pouigt
noman pouigt

Reputation: 976

Pollard’s p−1 algorithm: understanding of Berkeley paper

This paper explains about Pollard's p-1 factorization algorithm. I am having trouble understanding the case when factor found is equal to the input we go back and change 'a' (basically page 2 point 2 in the aforementioned paper).

  1. Why we go back and increment 'a'?
  2. Why we not go ahead and keep incrementing the factorial? It it because we keep going into the same cycle we have already seen?

  3. Can I get all the factors using this same algorithm? Such as 49000 = 2^3 * 5^3 * 7^2. Currently I only get 7 and 7000. Perhaps I can use this get_factor() function recursively but I am wondering about the base cases.

    def gcd(a, b):
if not b:
    return a
return gcd(b, a%b)

def get_factor(input):
    a = 2
    for factorial in range(2, input-1):
     '''we are not calculating factorial as anyway we need to find
        out the gcd with n so we do mod n and we also use previously
        calculate factorial'''
        a = a**factorial % input
        factor = gcd(a - 1, input)
        if factor == 1:
            continue
        elif factor == input:
            a += 1
        elif factor > 1:
            return factor

n = 10001077
p = get_factor(n)
q = n/p
print("factors of", n, "are", p, "and", q)

Upvotes: 2

Views: 1191

Answers (1)

user448810
user448810

Reputation: 17866

The linked paper is not a particularly good description of Pollard's p − 1 algorithm; most descriptions discuss smoothness bounds that make the algorithm much more practical. You might like to read this page at Prime Wiki. To answer your specific questions:

  1. Why increment a? Because the original a doesn't work. In practice, most implementations don't bother; instead, a different factoring method, such as the elliptic curve method, is tried instead.

  2. Why not increment the factorial? This is where the smoothness bound comes into play. Read the page at Mersenne Wiki for more details.

  3. Can I get all factors? This question doesn't apply to the paper you linked, which assumes that the number being factored is a semi-prime with exactly two factors. The more general answer is "maybe." This is what happens at Step 3a of the linked paper, and choosing a new a may work (or may not). Or you may want to move to a different factoring algorithm.

Here is my simple version of the p − 1 algorithm, using x instead of a. The while loop computes the magical L of the linked paper (it's the least common multiple of the integers less than the smoothness bound b), which is the same calculation as the factorial of the linked paper, but done in a different way.

def pminus1(n, b, x=2):
    q = 0; pgen = primegen(); p = next(pgen)
    while p < b:
        x = pow(x, p**ilog(p,b), n)
        q, p = p, next(pgen)
    g = gcd(x-1, n)
    if 1 < g < n: return g
    return False

You can see it in action at http://ideone.com/eMPHtQ, where it factors 10001 as in the linked paper as well as finding a rather spectacular 36-digit factor of fibonacci(522). Once you master that algorithm, you might like to move on to the two-stage version of the algorithm.

Upvotes: 2

Related Questions