🖊️
Crypto
  • Crypto
  • Fundamentals
    • Divisibility, Factors and Euclid's Algorithms
    • Modular Arithmetic
    • Rings, Fields and Euler's Totient Function
  • Further Maths
    • Continued Fractions
  • RSA
    • Overview
    • Public Exponent Attacks
      • e=1
      • Small e
      • Multi-party RSA with Small e
      • Wiener's Attack
    • Choice of Primes
      • N is prime
      • Mersenne Primes
      • P=Q
      • Fermat Factorisation
    • Factorisation Methods
      • Pollard's p-1
  • Diffie-Hellman Key Exchange
    • Overview
    • Solving the DLP
      • Baby Step, Giant Step
Powered by GitBook
On this page
  • Overview
  • Example
  • Applications
  • Sage Code

Was this helpful?

  1. RSA
  2. Factorisation Methods

Pollard's p-1

Factorising N when we know a factor is smooth

PreviousFactorisation MethodsNextOverview

Last updated 3 years ago

Was this helpful?

If we say that N=pqN=pqN=pq, where p,qp,qp,q are prime, then we can also say that for any a,ka,ka,k:

ak(p−1)≡1mod  pa^{k(p-1)} \equiv 1 \mod pak(p−1)≡1modp

Due to . This would mean ak(p−1)−1a^{k(p-1)} - 1ak(p−1)−1 is a factor of ppp and therefore NNN.

Overview

Let us say that L=k(p−1)L=k(p-1)L=k(p−1). If aL≡1mod  pa^L \equiv 1 \mod paL≡1modp, then p∣aL−1p \mid a^L-1p∣aL−1. Since p∣Np \mid Np∣N, we know that p∣gcd(aL−1,N)p \mid gcd(a^L-1, N)p∣gcd(aL−1,N).

This may seem all well and good, but how does this help us? We don't know ppp, nor do we have a way of calculating kkk.

What we actually do here is guess the value of LLL by (effectively) brute force. Essentially we put aaa to the power of integers with a huge number of prime factors, so it's all the more likely that the factors of p−1p-1p−1 are there. Once we put it to the powers, we can calculate the gcd(aL−1,N)gcd(a^L-1, N)gcd(aL−1,N) and if it is not equal to 000 then we have factorised NNN successfully.

The most common technique is to calculate ak!mod  Na^{k!} \mod Nak!modN and then calculate the GCD from there. We can make this into a more efficient approach by repeatedly putting it to the power of one greater than the previous iteration, e.g. calculate a,a2,(a2)3,((a2)3)4,...a,a^2,(a^2)^3,((a^2)^3)^4,...a,a2,(a2)3,((a2)3)4,... and calculate the GCD each time - this way, we will have a wealth of factors. A common choice of aaa is 222.

Example

Let's try and factorise 713713713 using Pollard's p−1p-1p−1:

21≡2mod  713,  gcd(1,713)==122≡4mod  713,  gcd(3,713)==143≡64mod  713,  gcd(63,713)==1644≡326mod  713,  gcd(325,713)==13265≡311mod  713,  gcd(310,713)==312 ^ 1 \equiv 2 \mod 713, \,\, gcd(1, 713) == 1 \\ 2 ^ 2 \equiv 4 \mod 713, \,\, gcd(3, 713) == 1 \\ 4 ^ 3 \equiv 64 \mod 713, \,\, gcd(63, 713) == 1 \\ 64 ^ 4 \equiv 326 \mod 713, \,\, gcd(325, 713) == 1 \\ 326 ^ 5 \equiv 311 \mod 713, \,\, gcd(310, 713) == 3121≡2mod713,gcd(1,713)==122≡4mod713,gcd(3,713)==143≡64mod713,gcd(63,713)==1644≡326mod713,gcd(325,713)==13265≡311mod713,gcd(310,713)==31

We get to 25!mod  7132^{5!} \mod 71325!mod713, and find that gcd(310,713)=31gcd(310, 713)=31gcd(310,713)=31​. We have successfully factorised NNN!

Applications

Sage Code

We can implement this algorithm really easily in Sage:

def pollards(n, iterations=50):
    R = IntegerModRing(n)
    cur = R(2)
    
    for i in range(2, iterations):
        print(f'{cur} ^ {i} = {cur**i}')
        
        cur **= i
        tst = gcd(cur-1, n)
        
        print(f'gcd({cur-1}, {n}) = {tst}')
        
        if tst != 1:
            return tst
    else:
        return None

You can remove the print() functions as they are completely unneccessary, but the logging may help visualise what it does.

This algorithm is useful when we know ppp is smooth, meaning it has lots of small prime factors. If this is the case, the iterative approach is more likely to include p−1p-1p−1 sooner rather than later. This leads to the concept of safe primes, primes in the form p=2q+1p=2q+1p=2q+1 where qqq is also a prime (called a ). In this case, p−1p-1p−1 is not smooth.

Sophie Germain prime
Fermat's Little Theorem