Skip to content

Integer Factorization

Introduction

Given a positive integer \(N \in \mathbf{N}_{+}\), find one of its nontrivial factors quickly.

Start with the naive algorithm. Divisors come in pairs, so the divisors of \(N\) fall into two blocks, \([2, \sqrt N]\) and \([\sqrt N+1,N)\). It is enough to iterate over the numbers in \([2, \sqrt N]\); division then yields at least two divisors. This method runs in \(O(\sqrt N)\).

For \(N\ge10^{18}\) this running time is unacceptable, and we want a better algorithm. One idea is to guess at random whether a number is a divisor of \(N\). With luck this finds the answer in \(O(1)\) time, but for \(N\ge10^{18}\) a guess succeeds with probability \(\frac{1}{10^{18}}\), and the expected number of guesses is \(10^{18}\). Guessing within \([2,\sqrt N]\) raises the success rate somewhat. We want a way to make the guessing smarter.

Naive algorithm

The simplest algorithm iterates over \([2, \sqrt N]\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
vector<int> breakdown(int N) {
  vector<int> result;
  for (int i = 2; i * i <= N; i++) {
    if (N % i == 0) {  // If i divides N, then i is a prime factor of N.
      while (N % i == 0) N /= i;
      result.push_back(i);
    }
  }
  if (N != 1) {  // After the steps above, what is left of N is a prime
    result.push_back(N);
  }
  return result;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def breakdown(N):
    result = []
    for i in range(2, int(sqrt(N)) + 1):
        if N % i == 0:  # If i divides N, then i is a prime factor of N.
            while N % i == 0:
                N //= i
            result.append(i)
    if N != 1:  # After the steps above, what is left of N is a prime
        result.append(N)
    return result

We can prove that the elements of result are exactly the prime factors of N.

Proof that the elements of result are exactly the prime factors of \(N\)

First look at how N changes. When the iteration for i ends, the part while(N % i == 0) N /= i has just finished, so i no longer divides N. Moreover, every time a factor is divided out, N still divides \(N\). Together these two facts guarantee that when the iteration for i begins, N is a divisor of \(N\) and is not divisible by any integer smaller than i.

Next we show that every element of result is a divisor of \(N\). In the iteration for i, the condition for storing i in result is N % i == 0, which says that i divides N; we have already shown that N is a divisor of \(N\), so i is a divisor of \(N\). When the loop over i ends, N is stored in result as well if it is not one. By the above, it too must be a divisor of \(N\).

Next we show that every element of result is prime. Suppose result contains a composite number \(K\). Then there is an i greater than one and at most \(\sqrt K\) that is a divisor of \(K\). Such a \(K\) cannot have been stored in result as some i of the loop, because the first paragraph showed that when the loop reaches \(K\), N is not divisible by any i smaller than \(K\). Nor can such a \(K\) have been added after the loop: the loop exits when i * i > N, so every i up to \(\sqrt K\) has been visited, and by the above none of these i can divide the current N, which is \(K\).

Finally we show that every prime factor of \(N\) appears in result. Suppose \(p\) is a prime factor of \(N\) that does not appear in result. By the discussion above, \(p\) cannot be an i that occurred in the loop. Let i be the last i before the loop exits; then i is strictly less than \(p\), and the N left after the loop is not divisible by any earlier i, so \(p\) divides N. Hence the final N is greater than one, and by the above it must be prime, so N equals \(p\) and is added to result at the end, contradicting the assumption.

If a table of primes has been precomputed beforehand, the running time drops from \(O(\sqrt N)\) to \(O(\frac {\sqrt{N}} {\ln N})\). See Sieves for more on precomputing a table.

Example: CF 1445C

Pollard's rho algorithm

Introduction

Brute force finds a nontrivial factor in \(O(p)=O(\sqrt N)\) time, where \(p\) is the smallest prime factor of \(N\). Pollard's rho algorithm, described below, is a randomized algorithm that finds a nontrivial factor in \(O(\sqrt p)=O(N^{1/4})\) expected time (note that a nontrivial factor is not necessarily a prime factor!).

Its core idea is this. Take a random self-map \(f: \mathbf Z_p \rightarrow \mathbf Z_p\), start from any point \(x_1\) and iterate \(x_n = f(x_{n-1})\): the sequence enters a cycle in \(O(\sqrt p)\) expected time. If we can find \(x_i \equiv x_j \pmod p\), then \(p\) divides \(\gcd(|x_i-x_j|, N)\), and this greatest common divisor is a nontrivial factor of \(N\).

The birthday paradox helps explain why the expected time to enter the cycle is \(O(\sqrt p)\).

Birthday paradox

Ignoring the year of birth (assume every year has 365 days), how many people must a room hold, at the least, for the probability that two of them share a birthday to reach \(50\%\)?

Solution: suppose a year has \(n\) days and the room holds \(k\) people, numbered with the integers \(1, 2,\dots, k\). Assume that each person's birthday is uniformly distributed over the \(n\) days and that the birthdays of any two people are independent.

Let \(A\) be the event that the \(k\) people have pairwise distinct birthdays. The probability of \(A\) is

\[ P(A)=\prod_{i=0}^{k-1}\frac{n-i}{n} \]

The probability that at least two people share a birthday is \(P(\overline A)=1-P(A)\). The question asks for \(P(\overline A)\ge\frac{1}{2}\), so

\[ P(A)=\prod_{i=0}^{k-1}\frac{n-i}{n} \le \frac{1}{2} \]

The inequality \(1+x\le \mathrm{e}^x\) gives

\[ P(A) \le \prod_{i=1}^{k-1}\exp\left({-\frac{i}{n}}\right)=\exp \left({-\frac{k(k-1)}{2n}}\right) \]

Therefore

\[ \exp\left({-\dfrac{k(k-1)}{2n}}\right) \le \frac{1}{2}\implies P(A) \le \frac{1}{2} \]

Substituting \(n=365\) and solving gives \(k\geq 23\). So a room needs at least \(23\) people for the probability that two of them share a birthday to reach \(50\%\). This mathematical fact is so counterintuitive that it is called a paradox.

For \(k>56\) and \(n=365\), the probability that two people share a birthday exceeds \(99\%\)1. And when a year has \(n\) days, a room with \(\frac{1}{2}(\sqrt{8n\ln 2+1}+1)\approx \sqrt{2n\ln 2}\) people has a probability of about \(50\%\) that at least two of them share a birthday.

A similar computation shows that when birthdays are drawn uniformly at random one after another, the expected number of people needed until a birthday first repeats is also \(O(\sqrt n)\). Let \(X\) be this number. Then

\[ E(X) = \sum_{x=0}^{n}P(X\ge x+1) = \sum_{x=0}^n\frac{n!}{(n-x)!n^x} = \sqrt{\frac{\pi n}{2}}+\frac23+o(1). \]

This suggests that if we can draw a sequence of numbers at random, the expected sample size needed before a number repeats is also \(O(\sqrt n)\).

Finding a divisor with the greatest common divisor

Actually building a random sequence modulo \(p\) is not feasible, because \(p\) is exactly what we are looking for. So we generate a pseudorandom sequence \(\{x_i\}\) with \(f(x)=(x^2+c)\bmod N\): pick \(x_1\) at random and set \(x_2=f(x_1),\ x_3=f(x_2),\ \dots,\ x_i=f(x_{i-1})\), where \(c\in[1,N)\) is a randomly chosen constant.

This function is easy to compute and tends to produce fairly random sequences. But it is not truly random. For example, with \(N=50,\ c=6,\ x_1=1\), \(f(x)\) generates

\[ 1, 7, 5, 31, 17, 45, 31, 17, 45, 31,\dots \]

From \(x_4\) on, the values cycle through \(31,17,45\). Arranged as in the figure below, the numbers form a picture that looks very much like a \(\rho\), which is how the algorithm got the name rho.

pollard-rho

More importantly, such a function really does give a self-map of \(\mathbf Z_p\). That is, it has the following property: if \(x\equiv y\pmod p\), then \(f(x)\equiv f(y)\pmod p\).

Proof

If \(x\equiv y\pmod p\), then \(x^2+c\equiv y^2+c\pmod p\). Now \(f(x)=x^2+c-k_xN\), where \(k_x\) is an integer that depends on \(x\), and \(p\mid N\), so \(f(x)\equiv x^2+c\pmod p\) and therefore \(f(x)\equiv f(y)\pmod p\).

The sequence \(\{x_n\bmod p\}\) comes from iterating a pseudorandom self-map of \(\mathbf Z_p\), so it repeats within \(O(\sqrt p)\) expected time. As soon as we observe such a repetition \(x_i\equiv x_j\pmod p\), we get a nontrivial factor of \(N\) from \(\gcd(|x_i-x_j|,N)\). Since \(p\) is unknown, we cannot detect the repetition directly; a simple test is precisely that \(\gcd(|x_i-x_j|,N)\) is strictly greater than one.

The algorithm does not always succeed, because \(\gcd(|x_i-x_j|,N)\) may equal \(N\), that is, \(x_i\equiv x_j\pmod N\). In that case \(\{x_n\}\) happens to repeat at the very moment \(\{x_n\bmod p\}\) first repeats, and we get no nontrivial factor. Once \(\{x_n\}\) has started to cycle there is also no point in iterating further, since from then on it only repeats the cycle. The algorithm should report that the factorization has failed, and we have to factor again with a different \(c\) in \(f(x)\).

By the analysis above, in theory any function \(f(x)\) that satisfies \(\forall x \equiv y \pmod p, f(x) \equiv f(y) \pmod p\) and is reasonably pseudorandom (certain polynomial functions, for example) can be used here. In practice \(f(x)=x^2+c\ (c\neq 0,-2)\) is the main choice.2

Implementation

The algorithm we implement has to decide quickly, during the iteration, whether \(\{x_n\bmod p\}\) has already repeated. If we view \(f\) as the edges of a directed graph whose vertices are the elements of \(\mathbf Z_p\), what we really have to implement is a cycle detection algorithm, except that the equality test becomes a test of whether \(\gcd(|x_i-x_j|,N)\) is greater than one.

Floyd's cycle detection

Suppose two people are racing, A fast and B slow. After some time A is sure to meet B, and when they meet, the total distance A has run minus the total distance B has run is a multiple of the cycle length.

Let \(a=f(0),b=f(f(0))\) and update \(a=f(a),b=f(f(b))\) at every step. It suffices to check during the updates whether \(a\) and \(b\) are equal: once they are, a cycle has appeared.

At every step we set \(d=\gcd(|x_i-x_j|,N)\) and check whether \(d\) satisfies \(1< d< N\); if it does, we return \(d\) right away. If \(d=N\), then \(\{x_i\}\) has already formed a cycle, and once it has there is no point in going on: return \(N\) itself, then change the random constant \(c\) and factor again.

Pollard's rho algorithm with Floyd's cycle detection
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
ll Pollard_Rho(ll N) {
  if (N == 4) return 2;  // two steps are taken at the start, so 4 is handled as a special case
  ll c = rand() % (N - 1) + 1;
  ll t = f(0, c, N);
  ll r = f(f(0, c, N), c, N);
  while (t != r) {
    ll d = gcd(abs(t - r), N);
    if (d > 1) return d;
    t = f(t, c, N);
    r = f(f(r, c, N), c, N);
  }
  return N;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import random


def Pollard_Rho(N):
    if N == 4:
        return 2  # two steps are taken at the start, so 4 is handled as a special case
    c = random.randint(1, N - 1)
    t = f(0, c, N)
    r = f(f(0, c, N), c, N)
    while t != r:
        d = gcd(abs(t - r), N)
        if d > 1:
            return d
        t = f(t, c, N)
        r = f(f(r, c, N), c, N)
    return N

Brent's cycle detection

Floyd's cycle detection can in fact be improved by a constant factor. Brent's cycle detection increases \(k\) starting from \(k=1\). In round \(k\), A waits in place while B moves forward \(2^k\) steps. If B meets A along the way, a cycle has been found; otherwise A teleports to B's position and the next round begins.

It can be proved3 that the number of calls to \(f\) needed before the cycle is found this way is never larger than with Floyd's cycle detection. The tests in the original paper show that Brent's cycle detection takes \(24\%\) less time on average than Floyd's.

Doubling optimization

With either Floyd's or Brent's cycle detection, the number of iterations is \(O(\sqrt p)\). But computing a \(\gcd\) in every iteration to test for a cycle slows the algorithm down. Accumulating a product reduces the number of \(\gcd\) computations.

In short, if \(\gcd(a,N)>1\), then \(\gcd(ab\bmod N,N)=\gcd(ab,N)>1\) holds for every \(b\in\mathbf N_+\). In other words, if we find that \(\gcd(\prod |x_i-x_j| \bmod N,N)>1\), then some pair \((x_i,x_j)\) among them must satisfy \(\gcd(|x_i-x_j|,N)>1\). If the product becomes zero at some point, the factorization has failed: quit and return \(N\) itself.

If a \(\gcd\) is computed once every \(k\) pairs, the complexity drops to \(O(\sqrt p+k^{-1}\sqrt p\log N)\), where \(\log N\) is the cost of a single \(\gcd\) computation. When \(k\) and \(\log N\) are of roughly the same order of magnitude, this gives an expected complexity of \(O(\sqrt p)\). Most implementations choose \(k=127\).

Here is an implementation of Pollard's rho algorithm with Brent's cycle detection and the doubling optimization.

Implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
ll Pollard_Rho(ll x) {
  ll t = 0;
  ll c = rand() % (x - 1) + 1;
  ll s = t;
  int step = 0, goal = 1;
  ll val = 1;
  for (goal = 1;; goal <<= 1, s = t, val = 1) {
    for (step = 1; step <= goal; ++step) {
      t = f(t, c, x);
      val = val * abs(t - s) % x;
      // if val is 0, quit and factor again
      if (!val) return x;
      if (step % 127 == 0) {
        ll d = gcd(val, x);
        if (d > 1) return d;
      }
    }
    ll d = gcd(val, x);
    if (d > 1) return d;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from random import randint
from math import gcd


def Pollard_Rho(x):
    c = randint(1, x - 1)
    s = t = f(0, c, x)
    goal = val = 1
    while True:
        for step in range(1, goal + 1):
            t = f(t, c, x)
            val = val * abs(t - s) % x
            if val == 0:
                return x  # if val is 0, quit and factor again
            if step % 127 == 0:
                d = gcd(val, x)
                if d > 1:
                    return d
        d = gcd(val, x)
        if d > 1:
            return d
        s = t
        goal <<= 1
        val = 1

Complexity

The expected number of iterations of Pollard's rho algorithm is \(O(\sqrt p)\), where \(p\) is the smallest prime factor of \(N\). Whether an implementation uses Floyd's or Brent's cycle detection, its expected complexity without the doubling optimization is \(O(\sqrt p\log N)\); with the doubling optimization it is approximately \(O(\sqrt p)\).

Note that the analysis above assumes a truly random self-map, whereas Pollard's rho algorithm actually uses a pseudorandom function. The algorithm therefore has no rigorous complexity analysis; in practice it usually runs fast.

Example: finding the largest prime factor of a number

Example: P4718 [Template] Pollard-Rho Algorithm

For a number \(n\), use the Miller–Rabin algorithm to test whether it is prime. If it is, return right away. Otherwise use Pollard's rho algorithm to find a factor \(p\) and divide \(p\) out of \(n\). Then factor \(n\) and \(p\) recursively, using Miller–Rabin to tell when a prime factor has been reached and updating max_factor with it; this yields the largest prime factor. The data in this problem is far too large for Floyd's cycle detection to be enough, so the doubling optimization is used here.

Implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;
using ll = long long;
using ull = unsigned long long;

int t;
ll max_factor, n;

ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

ll bmul(ll a, ll b, ll m) {  // fast modular multiplication
  ull c = (ull)a * (ull)b - (ull)((long double)a / m * b + 0.5L) * (ull)m;
  if (c < (ull)m) return c;
  return c + m;
}

ll qpow(ll x, ll p, ll mod) {  // binary exponentiation
  ll ans = 1;
  while (p) {
    if (p & 1) ans = bmul(ans, x, mod);
    x = bmul(x, x, mod);
    p >>= 1;
  }
  return ans;
}

bool Miller_Rabin(ll p) {  // primality test
  if (p < 2) return false;
  if (p == 2) return true;
  if (p == 3) return true;
  ll d = p - 1, r = 0;
  while (!(d & 1)) ++r, d >>= 1;  // make d odd
  for (ll k = 0; k < 10; ++k) {
    ll a = rand() % (p - 2) + 2;
    ll x = qpow(a, d, p);
    if (x == 1 || x == p - 1) continue;
    for (int i = 0; i < r - 1; ++i) {
      x = bmul(x, x, p);
      if (x == p - 1) break;
    }
    if (x != p - 1) return false;
  }
  return true;
}

ll Pollard_Rho(ll x) {
  ll s = 0, t = 0;
  ll c = (ll)rand() % (x - 1) + 1;
  int step = 0, goal = 1;
  ll val = 1;
  for (goal = 1;; goal *= 2, s = t, val = 1) {  // doubling optimization
    for (step = 1; step <= goal; ++step) {
      t = (bmul(t, t, x) + c) % x;
      val = bmul(val, abs(t - s), x);
      if ((step % 127) == 0) {
        ll d = gcd(val, x);
        if (d > 1) return d;
      }
    }
    ll d = gcd(val, x);
    if (d > 1) return d;
  }
}

void fac(ll x) {
  if (x <= max_factor || x < 2) return;
  if (Miller_Rabin(x)) {              // if x is prime
    max_factor = max(max_factor, x);  // update the answer
    return;
  }
  ll p = x;
  while (p >= x) p = Pollard_Rho(x);  // run the algorithm
  while ((x % p) == 0) x /= p;
  fac(x), fac(p);  // keep factoring x and p
}

int main() {
  cin >> t;
  while (t--) {
    srand((unsigned)time(NULL));
    max_factor = 0;
    cin >> n;
    fac(n);
    if (max_factor == n)  // the largest prime factor is n itself
      cout << "Prime\n";
    else
      cout << max_factor << '\n';
  }
  return 0;
}

  1. https://en.wikipedia.org/wiki/Birthday_problem#Reverse_problem ↩

  2. Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (2001). Handbook of Applied Cryptography. Section 3.11 and 3.12. ↩

  3. Brent, R. P. (1980), An improved Monte Carlo factorization algorithm, BIT Numerical Mathematics, 20(2): 176–184, doi:10.1007/BF01933190 ↩