INTEGER FACTORISATION

ALGORITHMS AND THE RSA

PROBLEM

A dissertation submitted to Birkbeck, University of London

for the degree of MSc in Mathematics.

By
James Stearn
Supervisor: Dr. Maura Paterson
Department of Economics, Mathematics and Statistics
31st August 2021
Contents

Abstract 5

Declaration 6

1 Public-key cryptography 7
1.1 Fundamentals of public-key cryptography . . . . . . . . . . . . . . . . . . . . 7
1.2 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 The RSA Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 Attacks on RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.4 Security of RSA & parameter choices . . . . . . . . . . . . . . . . . . 10

2 Integer factorisation algorithms 12

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Special-purpose algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Trial division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Fermat’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 Euler’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.4 Pollard’s rho algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 General-purpose algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Legendre’s congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Dixon’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Continued Fraction method . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.4 The Quadratic Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.5 Optimisation and the Multiple Polynomial Quadratic Sieve . . . . . . 26

2
Contents 3

3 The General Number Field Sieve 28

3.1 Foundations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.2 Key ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Rings of algebraic integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 Ring homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.2 The ring Z[θ] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.3 Generating a congruence of squares . . . . . . . . . . . . . . . . . . . . 30
3.2.4 Choosing a suitable polynomial . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Factor bases in Z & Z[θ] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.1 The rational factor base . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.2 The algebraic factor base . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.3 Quadratic characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Sieving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.1 Technical implementation of the sieve . . . . . . . . . . . . . . . . . . 40
3.4.2 The Lanczos algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Calculating the square root . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4 Time complexity 44
4.1 Big O notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Exponential time algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.1 Trial division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.2 Fermat’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.3 Euler’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.4 Pollard’s rho algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 Subexponential time algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3.1 Dixon’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3.2 Continued Fraction method . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3.3 The Quadratic Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3.4 The General Number Field Sieve . . . . . . . . . . . . . . . . . . . . . 48

5 Summary 49

Contents
List of Tables

1.1 Integer factorisation records . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1 Values calculated using Fermat’s method . . . . . . . . . . . . . . . . . . . . . 14

2.2 Values required for Euler’s method . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Values calculated using Pollard’s rho algorithm . . . . . . . . . . . . . . . . . 17
2.4 Possible factors when x2 ≡ y 2 (mod n) . . . . . . . . . . . . . . . . . . . . . . 18
2.5 Relations found with smooth yi . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 Smooth values found using the CFRAC method . . . . . . . . . . . . . . . . . 22
2.7 Selected sieving results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.8 Sieving results using logarithms . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.9 Factorisation data using MPQS . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4
Abstract

BIRKBECK, UNIVERSITY OF LONDON

ABSTRACT OF DISSERTATION submitted by James Stearn and entitled Integer

Factorisation algorithms and the RSA problem.

Date of Submission: 31st August 2021

Factorisation of large integers is a problem of considerable theoretical and practical interest.

The difficulty of factorising large integers lies at the heart of the RSA cryptosystem, which
is widely used to encrypt communications data. In this paper, we outline a number of
factorisation algorithms, from simple methods such as trial division, to the current fastest
known algorithm, the General Number Field Sieve.

In §1, we introduce the number theoretic foundations of the RSA cryptosystem and dis-
cuss the RSA problem. We show that factorising represents the best general method for
attempting to break the RSA cryptosystem.

§2 discusses a variety of factorising algorithms. We first highlight the distinction between

special-purpose and general-purpose algorithms. The algorithms are presented roughly in
historical order, to show how ideas developed and improved over time. Example factorisa-
tions of small numbers are given for each algorithm in order to illustrate their workings. The
General Number Field Sieve is discussed in detail in §3, including proofs of some of the more
important results used in the algorithm.

§4 outlines the time complexities of each algorithm, introducing notation used in the analysis
of algorithms. This chapter gives a quantifiable comparison of the theoretical running times
of the algorithms introduced in §2 & §3. We conclude with some consideration of future
prospects for factorising in §5, given possible theoretical and technological developments.

5
Declaration

This dissertation is submitted under the regulations of Birk-

beck, University of London as part of the examination re-
quirements for the MSc degree in Mathematics. Any quo-
tation or excerpt from the published or unpublished work
of other persons is explicitly indicated and in each such in-
stance a full reference of the source of such work is given. I
have read and understood the Birkbeck College guidelines on
plagiarism and in accordance with those requirements submit
this work as my own.

6
Chapter 1

Public-key cryptography

1.1 Fundamentals of public-key cryptography

To send a message securely in a classical (symmetric) cryptosystem, two parties must first
exchange some shared secret (the key) to enable encryption and decryption of the message.
Key exchange represents a critical vulnerability of the classical cryptosystem: an adversary
may intercept the exchange or retrieve the key post facto, thereby rendering the system
insecure. Continually changing keys presents further practical issues of secure distribution
and storage.

Public-key (asymmetric) cryptography resolves these issues by obviating the need to dis-
tribute a shared secret amongst the cryptosystem’s users. In a symmetric cryptosystem, the
decryption rule dk is identical to (or easily derived from) the encryption rule ek . [41] In a
public-key cryptosystem, each user has both a public key ek , used for encryption and pub-
lished publicly, and a distinct private key dk , used for decryption and kept secret. This allows
a user of the cryptosystem to send and receive messages securely without the vulnerability
inherent in an initial key exchange.

In 1976, Diffie and Hellman [14] published a viable method of public key exchange that
allowed two users to generate a shared secret securely over a public channel. In contrast
to the wartime cryptographers, who utilised mechanical methods to increase the complexity
of their ciphers, Diffie-Hellman key exchange exploits mathematical structures, namely the
multiplicative group of integers modulo a prime. In 1977, Rivest, Shamir, and Adleman
published the RSA cryptosystem, [37] building on ideas in Diffie and Hellman’s work.

7
Chapter 1. Public-key cryptography 8

1.2 RSA

In this section, we outline the mechanics of the RSA cryptosystem. We discuss its security
and the tractability of attacking the cryptosystem via number theoretic and computational
approaches.

1.2.1 The RSA Cryptosystem

Suppose Alice wishes to send a secure message to Bob. Bob first generates two large primes
p and q using one of a number of primality testing algorithms.

Bob then generates a large semiprime n = pq and calculates ϕ(n). [37]

Definition 1.1. A semiprime n ∈ N is the product of exactly two (not necessarily unique)
primes.

Definition 1.2. ϕ(n) is Euler’s totient function: the number of positive integers up to
n coprime to n.

As n is a semiprime, ϕ(n) = (p−1)(q−1), as ϕ(p) = p−1 for p prime and ϕ is a multiplicative

function.

Definition 1.3. Let (a, b) represent the greatest common divisor of a, b ∈ Z.

Definition 1.4. An arithmetic function f (n) is multiplicative if f (ab) = f (a)f (b) for all
a, b with (a, b) = 1.

Bob then chooses an e ∈ N such that (e,ϕ(n)) = 1 and calculates its inverse d modulo ϕ(n)
using the Extended Euclidean algorithm.

Definition 1.5. The pair (n, e) is an RSA public key. The integer n is an RSA modulus.

Definition 1.6. A corresponding RSA private key d is calculated d ≡ e−1 (mod ϕ(n))

To encrypt a message, Alice looks up Bob’s public key pair and encrypts the plaintext using
a one-way trapdoor function: a function that is easy to compute in one direction but difficult
to invert without some additional information (the private key). [16]

1.2. RSA
Chapter 1. Public-key cryptography 9

Definition 1.7. RSA encryption

To generate a ciphertext C from a plaintext M, Alice computes:

C = M e (mod n)

Definition 1.8. RSA decryption

Bob may now decrypt C using his knowledge of the private key d :

M = C d (mod n).

Given a ciphertext, we require that the function is indeed invertible given knowledge of the
private key d, and hence that the plaintext may be retrieved by the recipient.

Proposition 1.9. RSA decryption of C using private key d returns the original plaintext M.

Proof.

C d (mod n) ≡ (M e )d (mod n)
≡ M ed (mod n)
≡ M kϕ(n)+1 (mod n) [as ed ≡ 1 (mod ϕ(n)]
≡ (M ϕ(n) )k × M (mod n)
≡ (1)k × M (mod n) [By Euler’s Theorem] [20]
≡ M (mod n)

Having demonstrated the correctness of the RSA algorithm, we now consider its security.

1.2.2 The RSA Problem

The difficulty of inverting the encryption function, i.e. the difficulty of finding eth roots
modulo n underlies the security of the cryptosystem.

Definition 1.10. The RSA problem is defined as: [16]

Given y ∈ (Z/nZ∗ ), compute x such that xe ≡ y (mod n) (1.1)

We now outline some different approaches to this problem.

1.2. RSA
Chapter 1. Public-key cryptography 10

1.2.3 Attacks on RSA

Although there is no publicly known general attack on RSA, da Costa Boucinha describes
a number of specific attacks requiring implementation errors during the encryption process.
[11] These include repeated usage of the same modulus n and various known plaintext attacks
which require some partial knowledge of the plaintext. Careful selection of primes when
generating the modulus n and the use of random padding schemes defend against these
types of attack. Thus, as [11] makes clear, the most promising general attack is to attempt
to factorise the modulus n. Throughout this paper, we use n to represent an RSA modulus
to be factored.

A successful factorisation of n allows an attacker to calculate ϕ(n) and thereby decrypt all
messages encrypted using the corresponding public key. As the original RSA paper outlines,
‘the security of the [RSA] system rests in part on the difficulty of factoring the published
divisor, n.’ [37] As the difficulty of factorising generally increases with the size of the input,
by choosing larger primes to generate n, the security of the system may be (indefinitely)
increased.

The computational complexity of factorising n is at least as hard as the RSA problem, as

recovering p and q allows us to compute x directly using the private key d. [37] argues ‘...that
all the obvious approaches for breaking [the] system are at least as difficult as factoring n’.
Factorisation of large integers is therefore a problem of significant theoretical, practical, and
commercial importance.

1.2.4 Security of RSA & parameter choices

In 1977, Rivest was quoted in Martin Gardner’s column Mathematical Games as estimating
that a 126-digit semiprime would take around ‘... 40 quadrillion years’ to factorise with the
technology and algorithms of the day. [17] Subsequent increases in computing power and
theoretical development of faster algorithms have increased the size of numbers that may be
factorised.

In 1991, RSA Laboratories issued the RSA Factoring Challenge - a list of large semiprimes
intended to stimulate research into the factorisation problem. These days, factorisation of
large numbers is distributed across a network with many researchers contributing optimisa-
tions and processing power to large-scale factorisation projects. Optimisation of algorithm
implementations is at the forefront of modern factorisation research. The problem of fac-

1.2. RSA
Chapter 1. Public-key cryptography 11

torising thus lies at the cutting-edge intersection of number theory and computer science.

Table 1.1 [36] shows some record factorisations to outline advances made in the field. Esti-
mates for the capabilities of factorising algorithms between 1970-90 are based on [35]. These
records are for general numbers; larger numbers with particular special forms have been
factorised but are not presented here.1

Number Decimal digits Date factorised

20 ∼1970
50 ∼1980
107 1989
RSA-120 120 1/6/1993
RSA-130 130 10/4/1996
RSA-155 155 22/8/1999
RSA-576 174 3/12/2003
RSA-768 232 12/12/2009
RSA-240 240 2/12/2019
RSA-250 250 28/2/2020

Table 1.1: Integer factorisation records

RSA-250 is a semiprime with 250 decimal digits (or 829 bits). In the original RSA paper,
the authors recommended ‘...using 100-digit prime numbers p and q, so that n has 200
[decimal] digits’ (∼512 bits). [37] The National Institute of Standards and Technology
(NIST) currently recommends the use of at least 2048-bit keys to ensure security for personal
use. [2] Developments in factorising technology have been fairly consistent since the early
nineties, enabling institutions to accurately assess when security standards require updating.

To summarise, provided that our chosen generating primes satisfy particular conditions (to
be detailed in later chapters), the size of the modulus n is the primary determinant of
the security of an RSA encryption. We now detail the development of a range of integer
factorisation algorithms, highlighting the improvements and optimisations of later algorithms
on earlier work.

1
RSA-576 & RSA-768 are labelled according to their number of binary, not decimal, digits

1.2. RSA
Chapter 2

Integer factorisation algorithms

2.1 Introduction

Definition 2.1. The Integer Factorisation Problem is defined as: [45]

Given n ∈ Z+ , find a non-trivial a such that a|n (2.1)

Note that a need not be prime, in which case there are a number of primality testing
algorithms that may be used in combination with a factorisation algorithm to determine the
unique prime factorisation of n. There are two main classes of factorisation algorithm:

Definition 2.2. A special-purpose algorithm has runtime depending on some special

√
property of n or the factor a (e.g. the size of a or its proximity to n).

Definition 2.3. A general-purpose algorithm has runtime depending on the size of n

and independent of the size of the factors.

Although general-purpose algorithms may appear more powerful, as we can input any number
and reasonably estimate the runtime based on its size, the special-purpose algorithms remain
useful. For example, a large number with a small prime factor may be factorised quickly
and efficiently by simply attempting division by small values for a. On the other hand, a
general-purpose algorithm will take as long to factor a 100-digit number with 1-digit and
99-digit prime factors as it would to factor one with two 50-digit factors. [45] It is therefore
instructive to review a range of approaches to factorising and utilise methods suitable for
the given situation.

In practice, many factorisation attempts will combine a combination of special-purpose and

12
Chapter 2. Integer factorisation algorithms 13

general-purpose algorithms. This is somewhat analogous to the brute-force use of lists of

common passwords when attempting to crack a password, before the application of more
sophisticated techniques.

We begin with a review of selected special-purpose algorithms in §2.2, then proceed to

general-purpose algorithms in §2.3.

2.2 Special-purpose algorithms

2.2.1 Trial division

√
A naive approach to factorising involves trial division of n by all primes up to n. As
division is a computationally intensive operation, this approach is obviously inefficient as
many unnecessary divisions will be performed. However, if n happens to have a small prime
factor, trial division will find it in a reasonable amount of time. ([45] suggests it should only
be used for n < 108 ). In practice, trial division is still employed as an element in even the
most sophisticated algorithms, such as the Number Field Sieve.

2.2.2 Fermat’s method

Fermat introduced a method of factorisation that has directly influenced the development of
modern methods. We thus review it here for historical context.

Henceforth, we may assume the integer to be factored is odd, as even integers have an obvious
prime factor. We begin with a theorem of elementary number theory.

Theorem 2.4. Every odd integer may be written as the difference of two squares.

Proof. Let n be an odd integer. Write n = 2k + 1 for n, k ∈ Z. Squaring consecutive integers

k, k + 1 and subtracting gives: (k + 1)2 − k 2 = 2k + 1.

Fermat’s method entails searching for x, y ∈ Z such that n = x2 − y 2 . Once such x & y are
found, we may write n = (x + y)(x − y) and a factorisation has been found. It is possible
that this gives a trivial factorisation, in which case a new x, y pair must be found.

To find x & y, we calculate values of x2 − n until a square is found. Then x2 − n = y 2 and

n may be factored as above.
√
We begin with x = b nc + 1, incrementing by 1 until the value of x2 − n is a square. [24]

2.2. Special-purpose algorithms

Chapter 2. Integer factorisation algorithms 14

Example 2.5. We shall factorise n = 1633 using Fermat’s method.

√
We initialise with x = b 1633c + 1 = 41 and increment by 1.

xi yi2 = x2i − n yi
41 48 6.928...
42 131 11.446...
43 216 14.697...
44 303 17.407...
45 392 19.799...
46 483 21.977...
47 576 24

Table 2.1: Values calculated using Fermat’s method

Having found a square, we may write n = 472 − 242 , then n = (47 + 24)(47 − 24).
Thus, 1633 = 71 × 23.

Note that if the two factors are ‘close’ together, Fermat’s method will find them quickly.
This needs to be taken into account when generating an RSA modulus. In the worst case
however, Fermat’s method is slower than trial division.

2.2.3 Euler’s method

Euler employed a similar method to Fermat to factor larger numbers. As the proof of
the method outlines the derivation of values used in a factorisation, we show it here for
completeness. [9]

Proposition 2.6. Let n be an odd integer, expressible as the sum of two squares in two
distinct ways: n = a2 + b2 = c2 + d2 for some a, b, c, d ∈ Z with b < d; a, c odd, and b, d even.

Let r = (a − c, d − b); u = (a + c, d + b); s = a − c/r; t = d − b/r

Then n is factorised by:

 r u 
n = ( )2 + ( )2 s2 + t2


(2.2)
2 2

Proof. Suppose n is expressible as the sum of two squares in two distinct ways.
Factorising gives: (a − c)(a + c) = (d − b)(d + b)
As r = (a − c, d − b), then: a − c = rs and d − b = rt for some s, t ∈ Z with (s, t) = 1.

2.2. Special-purpose algorithms

Chapter 2. Integer factorisation algorithms 15

This gives s(a + c) = t(d + b), so t|(a + c) and a + c = tu for some u ∈ Z.

Then d + b = su =⇒ (a + c, d + b) = u with u even.
Therefore:
 r u 
1
( )2 + ( )2 s2 + t2 = (rs)2 + (rt)2 + (su)2 + (tu)2


2 2 4
1
(a − c)2 + (d − b)2 + (d + b)2 + (a + c)2


=
4
1 2
a + b2 + c2 + d2


=
2
=n

Example 2.7. We shall factorise n = 4453 using Euler’s method.

By a similar process to Fermat’s method, we have found that we may write 4453 as
4453 = 632 +222 and 4453 = 332 +582 . We can calculate greatest common divisors efficiently
using the Extended Euclidean algorithm.

a = 63 a − c = 30 r = (30, 36) = 6
b = 22 a + c = 96 u = (96, 80) = 16
c = 33 d − b = 36 s = a − c/r = 5
d = 58 d + b = 80 t = d − b/r = 6

Table 2.2: Values required for Euler’s method

Taking the values from the last column and substituting into (2.2), gives:

n = ( 26 )2 + ( 16 2

2 2
2 ) (5 + 6 )

Thus, we obtain the factorisation 4453 = (32 + 82 )(52 + 62 ) = 73 × 61.

Euler’s method relies on being able to express n as the sum of two squares in more than one
way. Moreover, to be of any use, we must be able to find these sums in an efficient manner.
Unfortunately, its utility is severely limited by the following theorem:

Theorem 2.8. Sum of two squares theorem: For n ∈ Z, n is the sum of two squares if
and only if all primes p of the form p ≡ 3(mod 4) in the prime factorisation of n have even
powers .

Proof. A proof is given in Theorem 3.13 of [3].

2.2. Special-purpose algorithms

Chapter 2. Integer factorisation algorithms 16

2.2.4 Pollard’s rho algorithm

In 1975, John Pollard introduced a novel factorisation method in his paper ‘A Monte Carlo
Method for Factorization’. Pollard’s method utilises a pseudo-randomly generated sequence,
hence the paper’s title.

To factorise n, the method proceeds by generating a sequence with some polynomial f ∈ Z[x].
[33] Pollard originally used f (x) = x2 − 1.1 An initial value x0 ∈ N is chosen randomly such
that x < n. The sequence is now generated recursively: [45]

xi ≡ f (xi−1 ) (mod n)

As n is finite, there are a finite number of congruence classes modulo n, so the sequence
must eventually repeat and cycle.

Now consider some non-trivial factor d of n. Both the sequences xi (mod d) and xi (mod n)
must eventually cycle, but it is likely that xi (mod d) will cycle sooner, as d < n, so there are
fewer congruence classes modulo d. It is therefore likely there exists some pair xi , xj such
that:

xi ≡ xj (mod d)
(2.3)
xi 6≡ xj (mod n)

In this case, (xi − xj , n) is a non-trivial factor of n as d | (xi − xj ) but n - (xi − xj ). [45]

Of course, we don’t know d in advance, so to find it, we could check the gcd of each xi with
all previous xj values until a non-trivial factor is found (if (2.3) does not hold, (xi − xj , n)
will be a trivial factor). This becomes quite inefficient as the number of xi s grows, so Pollard
used Floyd’s cycle-finding algorithm to detect a cycle. This algorithm works by incrementally
checking xi and x2i for a repeated value in order to identify a cycle. [45]

Floyd’s cycle-finding algorithm greatly increases efficiency as it requires only that we check
(x2i − xi , n) for each i, until a non-trivial factor is found. When plotted as a graph, the even-
tual cycling of the xi (mod d) sequence resembles the Greek letter ρ, hence the algorithm’s
name.

Example 2.9. We shall factorise n = 6497 using Pollard’s rho algorithm.

We initialise the algorithm using x0 = 2 and f (x) = x2 − 1 (mod 6497).

We calculate the values of xi for i = 1, 2, 3..., and calculate (x2i − xi , 6497) until a non-trivial

1
[33] conjectures that all polynomials x2 ±a with a 6= 0, 2 work equally well.

2.2. Special-purpose algorithms

Chapter 2. Integer factorisation algorithms 17

factor is found. Intermediate calculations of the algorithm are shown in the table on the
next page.

One particular advantage of Pollard’s rho algorithm is that it does not require much storage,
as only a few xi values need to be stored at any one time.

i xi x2i − 1 (mod 6497) (x2i − xi , 6497)

0 2 3 N/A
1 3 8 1
2 8 63 1
3 63 3968 1
4 3968 2792 73
5 2792 5360 1
6 5360 6362 1
7 6362 5230 1
8 5230 529 73

Table 2.3: Values calculated using Pollard’s rho algorithm

So (x8 − x4 , 6497) = 73 and the algorithm has found a non-trivial factor of 6497 (we could
have stopped the calculations in the final column here).
We therefore find the factorisation 6497 = 73 × 89.

It is possible that the sequence modulo d and modulo n will repeat at the same xi value, in
which case the gcd will be n and the algorithm will fail to find a non-trivial factor. [45] In
this case, we initialise with a different x0 value or change our polynomial f (x).

The greatest success of Pollard’s rho algorithm was its use (in a slightly adapted form) in the
8
factorisation of the 8th Fermat number F8 = 22 + 1. [4] F8 has 78 decimal digits and was
factored in 1980 by Pollard and Brent, who would go on to factor larger Fermat numbers
such as F10 . [6] Brent’s optimisation consists of a cycle-finding algorithm ∼36% faster than
Floyd’s algorithm, leading to an overall speed up of ∼24% for the entire algorithm. [5]
Besides this optimisation, the overall approach is the same, so we do not describe the details
here.

To summarise, we have reviewed some historically important special-purpose factorisation

algorithms, and outlined the development of factorising capabilities. This review is by no
means exhaustive. In particular, we have not discussed Lenstra’s elliptic-curve method,
which is a fast special-purpose algorithm often used to factorise n known to have small prime

2.2. Special-purpose algorithms

Chapter 2. Integer factorisation algorithms 18

factors. For further details, see [29]. We now proceed to the general-purpose algorithms.

2.3 General-purpose algorithms

2.3.1 Legendre’s congruence

Most general-purpose algorithms exploit an idea based upon Fermat’s method, perhaps first
introduced by Maurice Kraitchik. [34] Recall from §2.2.2 that in order to factorise n, we
attempt to find some values x, y such that x2 − y 2 = n. The closely related congruence
x2 ≡ y 2 (mod n) is fundamental to the general-purpose algorithms. Kraitchik observed:

Proposition 2.10. If x and y are two integers less than n, such that x 6= y and x + y 6= n,
and x2 ≡ y 2 (mod n), then (x − y, n) and (x + y, n) are possibly non-trivial factors of n.

The congruence above is sometimes known as Legendre’s congruence. [45] To see why Propo-
sition 2.10 holds, we tabulate the possibilities for a semiprime n = pq with p, q prime, as
used in RSA: [8]

p|x+y? p|x-y? q|x+y? q|x-y? (x+y,n) (x-y,n) Non-trivial factor?

X X X X n n ×
× X X X q n X
X × X X n q X
X X × X p n X
X X X × n p X
X × X × n 1 ×
× X × X 1 n ×
X × × X p q X
× X X × q p X

Table 2.4: Possible factors when x2 ≡ y 2 (mod n)

Thus, if we are able to find x, y such that Legendre’s congruence holds, there is a probability
2
of 3 that we will find a non-trivial factor. Each algorithm varies in the manner in which the
congruence of squares is found.

We begin ahistorically with Dixon’s algorithm, which uses a number of concepts employed
in more complex algorithms. In §2.3.3 , we outline one of the earliest general-purpose al-
gorithms, the Continued Fraction (or CFRAC) method. We build upon these concepts in

2.3. General-purpose algorithms

Chapter 2. Integer factorisation algorithms 19

discussion of the Quadratic Sieve in §2.3.4, leading naturally into a review of the General
Number Field Sieve in §3.

2.3.2 Dixon’s algorithm

Rather than attempting to find x and y such that x2 ≡ y 2 (mod n), Dixon’s method requires
only that we find a number of relations:

x2 ≡ y (mod n) where y is B-smooth. (2.4)

Definition 2.11. A number is B-smooth if all of its prime factors pi satisfy pi ≤ B for
some B ∈ N. [45]

Example 2.12. 10780 is 11-smooth as 10780 = 22 × 5 × 72 × 11.

11466 is not 11-smooth as 11466 = 2 × 32 × 72 × 13.

Definition 2.13. A factor base PB is the set of primes pi ≤ B.

Dixon’s method is an improvement on Fermat’s, as there are more smooth numbers satisfying
(2.4) than the stricter requirement x2 ≡ y 2 (mod n). To see how we generate a congruence
of squares using these relations, consider the following example:

Example 2.14. We will factorise n = 1537 using the factor base PB = {2, 3, 5, 7, 11}

The required relations are of the form: [15]

Y
x2i ≡ yi (mod 1537) where the yi are 11-smooth (i.e. yi = pai i )
pi ∈PB

By calculating x2 (mod 1537) for random x values and searching for 11-smooth numbers, we
find the relations in Table 2.5.2

x x2 (mod 1537) Factorisation of yi Vector

47 672 25 × 3 × 7 (1 1 0 1 0)
49 864 25 × 33 (1 1 0 0 0)
57 175 52 × 7 (0 0 0 1 0)
62 770 2 × 5 × 7 × 11 (1 0 1 1 1)
69 150 2 × 3 × 52 (1 1 0 0 0)
80 252 22 × 32 × 7 (0 0 0 1 0)

Table 2.5: Relations found with smooth yi

2
There are more relations than this, those shown are examples only.

2.3. General-purpose algorithms

Chapter 2. Integer factorisation algorithms 20

The prime factorisations of each yi are also represented as vectors vi ∈ FB B

2 , with F2 the

B-dimensional vector space over the finite field Z/2Z. [8]

The vector entries thus show the parity of each prime’s exponent in the factorisation.

Example 2.15. 756 = 22 × 33 × 50 × 71 × 110 would be represented (0 1 0 1 0).

We may now generate a square using linear algebra. Provided we have B+1 or more vectors
vi ∈ FB
2 , there must be a non-trivial linear dependence between them. Gaussian elimination

or another algorithm for solving systems of linear equations may now be used to find a
combination of vectors which sum to the zero vector.

In this case, we see by inspection that adding the first 3 vectors v1 + v2 + v3 gives:

(1 1 0 1 0) + (1 1 0 0 0) + (0 0 0 1 0) = (0 0 0 0 0)

This is equivalent to multiplying x1 , x2 , x3 and ensures that all prime powers are even. This
gives the congruence of squares:

472 × 492 × 572 ≡ 210 × 34 × 52 × 72 (mod 1537)

or
(47 × 49 × 57)2 ≡ (25 × 32 × 5 × 7)2 (mod 1537)

Reducing modulo 1537 gives:

6262 ≡ 8582 (mod 1537)

We now calculate (858 + 626, 1537) = 53 and (828 − 626, 1537) = 29 to find the factorisation
1537 = 29 × 53.

It’s possible that this method gives a trivial factorisation of n, in which case we try again
with a different combination of relations or an expanded factor base. It is clear that the
speed of this method (and others based upon it) relies on finding enough relations efficiently.
In addition, we require some efficient way of determining smoothness. With a smaller factor
base, finding a linear dependency is faster but we risk not being able to find enough smooth
values to guarantee a dependency. [34] Thus, our choice of factor base is critical to the
algorithm’s runtime.

We now consider the Continued Fraction method, which uses continued fractions to find
relations of the form (2.4).

2.3. General-purpose algorithms

Chapter 2. Integer factorisation algorithms 21

2.3.3 Continued Fraction method

Lehmer and Powers introduced the Continued Fraction (CFRAC) method in a 1931 paper,
but it was not until the 1970’s that computers were powerful enough to fully exploit their
ideas.

Definition 2.16. A continued fraction is an expression of the form:

b0
a0 +
b1
a1 +
b2
a2 +
bn
··· +
an
ai , bi ∈ Z and all ai positive for i > 0.
If all bi = 1, the continued fraction is regular.

Earlier factorisation methods utilising continued fractions depended on finding squares in

the denominators of an expansion, which happens only rarely. As [25] observes, more often
we may find a square as the ‘...product of two more denominators.’
√
To generate relations, we consider the continued fraction expansion of kn. To see why,
consider the congruence x2 ≡ W (mod n) for some small W. If W is small enough, it has a
reasonable chance of being smooth. We can express this congruence as x2 = W + knd2 for
some k, d ∈ Z. Then ( xd )2 − kn = W/d2 and W/d2 is small. So x
d ∈ Q is an approximation
√
of kn. [45]

Ai
√
We first generate a sequence of convergents Bi to kn, and set Wi = A2i − Bi2 kn.

Definition 2.17. The convergents of a continued fraction are rational approximations to

a0
a real number. The first convergent is given by . The nth convergent is given by the
1
following recursive formula, with the ai from the continued fraction expansion: [21, §1.2]
hn an hn−1 + hn−2
=
dn an dn−1 + dn−2

√
For details on finding the continued fraction representation of n and generating convergents,
see §2.5 and §2.6 of [21].

2.3. General-purpose algorithms

Chapter 2. Integer factorisation algorithms 22

Example 2.18. We shall factorise n = 1711 using the Continued Fraction method.

We set k = 1 in this expansion and will use the factor base PB = {−1, 2, 3, 5}.

Note that we include -1 in the factor base. This allows us to consider negative congruences,
which may be of smaller absolute value, and thus more likely to be smooth. As we require
that the power of -1 in our final congruence be even, the linear algebra step is unchanged.
√
The continued fraction expansion of 1711 is:

√ 1
1711 = 41 +
1
2+
1
1+
1
2+
1
1+
13 + · · ·

We show the convergents in Table 2.6. Note that only convergents with Wi smooth are
shown for clarity.

Ai
Bi (mod 1711) Wi = A2i − 1711 × Bi2 (mod 1711) Factorisation of Wi Vector
41
1 -30 −1 × 2 × 3 × 5 (1 1 1 1)
83
2 45 32 × 5 (0 0 0 1)
455
11 -6 −1 × 2 × 3 (1 1 1 0)
1113
151 5 1×5 (0 0 0 1)
1129
1403 -54 −1 × 2 × 33 (1 1 1 0)

Table 2.6: Smooth values found using the CFRAC method

We observe that summing the third and fifth vectors generates the zero vector (0 0 0 0).
By the definition of Wi , we have Wi ≡ A2i (mod n), giving the congruence:

4552 × 11292 ≡ −12 × 22 × 34 (mod 1711)

Which simplifies and reduces to:

3952 ≡ 182 (mod 1711)

Finally, we calculate (395 + 18, 1711) = 59 and (395 − 18, 1711) = 29 and obtain the factori-
sation 1711 = 29 × 59.

2.3. General-purpose algorithms

Chapter 2. Integer factorisation algorithms 23

In 1970, Morrison and Brillhart developed a computer implementation of CFRAC and used
7
it to factorise the seventh Fermat number, 22 + 1, a number with 39 decimal digits. [31]
Although this represented a significant milestone in factorising technology, the CFRAC al-
gorithm was soon superseded by a forerunner to today’s methods, the Quadratic Sieve of
Carl Pomerance.

2.3.4 The Quadratic Sieve

A primary innovation of the Quadratic Sieve, attributed by Pomerance in [34] to unpublished

work by Richard Schroeppel in the late 1970’s, was the introduction of a sieving process to
drastically speed up the identification of smooth values. Although the primes in our factor
base may be small relative to the modulus, much time is wasted by trial division on non-
smooth values, which cannot be used to form a congruence.

The sieve inverts this process: rather than dividing every value by each prime in our factor
base to determine if they are smooth, we instead fix a prime pi ∈ PB and determine all values
which are divisible by pi . Pomerance’s choice of polynomial facilitates this step. Recall from
§2.3.2 that Dixon’s method seeks x2 ≡ y (mod n) where y is B-smooth.

Pomerance instead proposed finding smooth values of the polynomial:

f (xi ) = x2i − n (2.5)

Once B+1 xi with f (xi ) smooth are found, we use linear algebra to find a subset S with: [8]
Y Y q
f (xi ) = (pi i )2
xi ∈S pi ∈PB

(pqi i ), gives the required congruence of squares:

Y Y
Setting a = xi and b =
xi ∈S pi ∈PB

Y Y Y
a2 = (x2i ) ≡ (x2i − n) ≡ f (xi ) = b2 (mod n) (2.6)
xi ∈S xi ∈S xi ∈S

Proposition 2.19. If p|f (xi ) for p ∈ PB , then p|f (xi + kp) for k ∈ Z.

Proof. As p|f (xi ), f (xi ) ≡ 0 (mod p). So x2i − n ≡ 0 (mod p).

Now, f (xi + kp) = (xi + kp)2 − n = (x2i + 2xi kp + k 2 p2 ) − n) ≡ x2i − n ≡ 0 (mod p). [8]
So p|f (xi + kp).

2.3. General-purpose algorithms

Chapter 2. Integer factorisation algorithms 24

To sieve by pj , we first need to solve the congruence:

x2i − n ≡ 0 (mod pj ). (2.7)

The Tonelli-Shanks algorithm is an efficient method for doing this. [44] We sieve over an
interval [−u ≤ xi ≤ u] that is heuristically expected to generate enough smooth values of
f (xi ). To do this, a 2u × B array is initialised with the 2u values of f (xi ) in the first column.
For xi solving (2.7) we divide f (xi ) by pj and put the result in the jth column. We can then
divide all further values f (xi + kpj ) in the interval by pj by Proposition 2.19.

This process only works if n is a quadratic residue modulo p (otherwise (2.7) has no solutions),
so we must modify our factor base PB to contain only primes satisfying this condition. The
process is then repeated for each pj ∈ PB . Finally the array is scanned for values of ±1, which
indicate that the f (xi ) factors completely over the factor base. As Pomerance mentions, f (xi )
values divisible by paj for a > 2 will not equal 1 unless we sieve further by higher powers of
pj . For example, 60 would be reduced to 2 after sieving only by 21 , 31 , and 51 . [35]

Example 2.20. We will sieve the interval [0,60] for smooth values of f (xi ) = x2i − n and
use this to factorise n = 2291 with PB = {−1, 2, 3, 5, 7, 11}.

We first need to solve (2.7) modulo the pj ∈ PB . We find that 2291 is a quadratic non-residue
modulo 3, so we remove 3 from our factor base.

Besides p = 2, for any p for which n is a quadratic modulo, there will be 2 solutions. We
find x2i ≡ 2291 (mod 5) has solutions x ≡ 1 (mod 5) & x ≡ 4 (mod 5).

We thus go to the 1st and 4th rows in the column p = 5 and divide f (xi ) by 5. We continue
down the column, dividing by 5 in the (1 + 5k)th and (4 + 5k)th positions. To sieve by higher
powers, we next solve x2i ≡ 2291 (mod 52 ) and repeat this process.

Table 2.7 shows the results of sieving with PB = {−1, 2, 5, 7, 11} and some small values of
paj . We only tabulate a few selected values with small factors for clarity, including any xi
that are found to generate smooth f (xi ) values, shown in bold.

2.3. General-purpose algorithms

Chapter 2. Integer factorisation algorithms 25

xi x2i − 2291 2 5 52 53 7 72 73 11
1 -2290 -1145 -229 - - - - - -
4 -2275 - -455 -91 - -13 - - -
17 -2002 -1001 - - - -143 - - -13
24 -1715 - -343 - - -49 -7 -1 -
31 -1330 -665 -133 - - -19 - - -
39 -770 -385 -77 - - -11 - - -1
46 -175 - -35 -7 - -1 - - -
49 110 55 11 - - - - - 1
51 310 155 31 - - - - - -
60 1309 - - - - 187 - - 17

Table 2.7: Selected sieving results

After scanning the sieve, we find the following smooth values and use them to generate the
exponent matrix:

xi f (xi ) Factorisation  
1 0 1 1 0
24 -1715 −1 × 5 × 73  

→
 
 1 1 1 1 1 
39 -770 −1 × 2 × 5 × 7 × 11 



 1 0 0 1 0 
46 -175 −1 × 52 × 7  
0 1 1 0 1
49 110 2 × 5 × 11

Although we have only collected 4 smooth values and a dependency is not guaranteed, in
this case we are fortunate that v2 + v3 + v4 = (0 0 0 0 0).

We thus generate the congruence by (2.6):

(39 × 46 × 49)2 ≡ (2 × 52 × 7 × 11)2 (mod 2291)

or
879062 ≡ 15592 (mod 2291)

Calculating as usual (87906 + 1559, 2291) = 29 and (87906 − 1559, 2291) = 79 gives the
factorisation 2291 = 29 × 79.

As there are fewer primes allowed in our factor base due to the quadratic residue condition, we
may miss some f (xi ) values with only small prime factors, but we save time by only dividing
by a pj once we already know that pj |f (xi ). This represents a huge gain in efficiency over
naive trial division methods of finding smooth values.

2.3. General-purpose algorithms

Chapter 2. Integer factorisation algorithms 26

2.3.5 Optimisation and the Multiple Polynomial Quadratic Sieve

Pomerance introduced an optimisation in [34] that further speeds up the sieving process.
Rather than dividing by the pj ’s directly, we instead initialise the array with the values of
log f (xi ) and subtract log pj , which is equivalent to dividing by pj by the Second Log Law. As
the logarithms are computed only roughly, this is much quicker than division by (potentially)
large numbers. The array is then scanned for values close to 0, which correspond to values
likely to be smooth. Only at this point is time-consuming trial division performed, in order
to verify that the f (xi ) actually is smooth. In this way, we only perform trial division on
values highly likely to be smooth.

Depending on the initial accuracy of the logarithms, there will be some small percentage of
misidentified non-smooth values tested, but the prior time savings more than make up for
these unnecessary divisions.

Example 2.21. We show the sieving process using logarithms only for xi = 24, 31 as exam-
ples. Recall from Table 2.7 that xi = 24 gave a smooth f (xi ).

xi log10 |(x2i − 2291)| 2 5 52 53 7 72 73 11

24 3.234 - 2.535 - - 1.690 0.845 0 -
31 3.124 2.823 2.124 - - 1.279 - - -

Table 2.8: Sieving results using logarithms

A further improvement on the algorithm was developed by Peter Montgomery. [34] As the
values of f (xi ) grow larger, it becomes increasingly more unlikely that they will be smooth
over the factor base. Montgomery proposed employing multiple quadratic polynomials to
increase the number of smooth values found. These days, it is this form of the algorithm
that is generally used, and that has made the factorisation of 60-80 digit numbers feasible
on a home computer.

Montgomery’s optimisation also allows the distribution of computation across a network,

as each polynomial may be sieved in parallel, with the results then combined for the linear
algebra processing. For further details on the Multiple Polynomial Quadratic Sieve (MPQS)
see [38].

During the mid-90’s Lenstra and Manasse exploited the parallelisation of the sieve to dis-
tribute factorising projects over the internet. [35] Sample factorisation data from this project

2.3. General-purpose algorithms

Chapter 2. Integer factorisation algorithms 27

is shown below to give a more realistic example of the size of factor bases and primes required
for a successful factorisation with MPQS. [28] Table 2.9 also indicates the rapid growth in
computation time as the size of the modulus increases.3

Parameter 116-digit n 120-digit n 129-digit n

Size of factor base 120,000 245,810 524,339
Prime bound B 108 230 230
Data generated (GB) 0.25 1.1 2
Sieving time (MY) 400 825 5000
Matrix processing time (Hours) 0.5 4 45

Table 2.9: Factorisation data using MPQS

The Quadratic Sieve set many factoring records throughout the 1980’s, before it too, was
superseded by the current fastest-known algorithm, the General Number Field Sieve (GNFS).
For n with less than 120 digits or so, [19] MPQS remains the fastest algorithm due to the
complexity of setting up the GNFS. Above this threshold, the GNFS begins to be faster.

In this section, we have described some important general-purpose algorithms and laid the
mathematical foundations for an outline of the General Number Field Sieve in §3.

3
Sieving time is given in units of MIPS-years; at the time, 1 MY equalled 1 year of processing on a VAX
11/780. [28]

2.3. General-purpose algorithms

Chapter 3

The General Number Field Sieve

3.1 Foundations

3.1.1 History

The foundations of the General Number Field Sieve can be traced to ideas circulated in a
letter by John Pollard in 1988 for factorising a special class of numbers: those of the form
re +s with small positive r, s. In his letter, Pollard proposed F9 , with 155 decimal digits, as a
potential candidate for factorisation using what is now called the Special Number Field Sieve
(SNFS). This was successfully achieved in 1990, by A Lenstra, H Lenstra, and Manasse. [26]
The General Number Field Sieve employs similar ideas but removes the input conditions and
works with integers of any form, at the expense of some speed. We thus concentrate on the
GNFS for the remainder of this chapter. For further information on the SNFS, see [27] and
§4 & 5 of [26].

3.1.2 Key ideas

The key innovation of Pollard’s idea was to expand the search for smooth values beyond the
ring Z, using algebraic number fields. If we can find rings that generate more smooth values
than Z, we should in theory be able to find relations faster. Such an idea is not obvious
- smoothness is easily understood when dealing with integers, but how do we apply it to
elements not in Z? To answer this, we will need to extend our concept of smoothness.

A second, more intuitive, innovation is to use polynomials other than quadratics as our gen-
erating polynomial f (xi ). If some higher-power polynomials generate more smooth values
than quadratics, again, we may find relations faster. The expansion of our scope to other

28
Chapter 3. The General Number Field Sieve 29

rings requires some knowledge of algebraic number theory; we outline the necessary mathe-
matical background in §3.2. In §3.3, we present the theory required to extend our concept of
smoothness, and discuss sieving for the GNFS in §3.4. The final step of calculating a square
root in an algebraic number field is discussed in §3.5.

3.2 Rings of algebraic integers

3.2.1 Ring homomorphisms

Recall that the quadratic sieve maps squares in Z to squares in Z/nZ.

Definition 3.1. A ring homomorphism is a function from a ring R to a ring S,

φ : R → S such that: [40]

ˆ φ(1R ) = (1S )

ˆ φ(a + b) = φ(a) + φ(b) for all a, b ∈ R

ˆ φ(ab) = φ(a)φ(b) for all a, b ∈ R

To generate a congruence of squares using rings other than Z, we construct a ring homo-
morphism. We first choose a monic, irreducible polynomial f (x) of degree d with rational
coefficients. Typically for numbers in the 120-150 digit range, we set d = 5.

Then f (x) factorises: f (x) = (x − θ1 )(x − θ2 ) . . . (x − θd ) with θi ∈ C.

Each root θ may be used to form a ring:

Proposition 3.2. Let θ be the root of a monic, irreducible polynomial f (x) of degree d
with rational coefficients. The set of all polynomials in θ with rational coefficients is a ring,
denoted Q(θ).

By Theorem 2.2.2 of [8], Q(θ) is a field and the elements of Q(θ) may be represented as
Q-linear combinations of elements of the set R = {1, θ, θ2 , . . . , θd−1 }, i.e. R forms a basis for
Q(θ).

3.2.2 The ring Z[θ]

We now consider the ring of integers of the field Q(θ).

Definition 3.3. An α ∈ C is an algebraic integer if it is the root of some monic polynomial

with integer coefficients. [40]

3.2. Rings of algebraic integers

Chapter 3. The General Number Field Sieve 30

That is, for an equation of the form: f (x) = xn + · · · + a2 x2 + a1 x + a0 with ai ∈ Z, we have

f (α) = 0.

Definition 3.4. A number field K is an extension of the field Q that is a finite dimensional
vector space. We call the dimension of the vector space the degree of K.

The set of all algebraic integers in a field F ⊆ C is called the ring of integers.

Definition 3.5. The ring of integers OK of the number field K ⊆ C is defined: OK = K∩A
where A is the ring of algebraic integers.

As Q(θ) is a field, we now form a subring of OQ(θ) by Proposition 2.3.2 of [8], as follows:

Proposition 3.6. Given a root θ of a monic, irreducible polynomial f(x) such that:

f (x) = xn + · · · + a2 x2 + a1 x + a0 with ai ∈ Z,

the set of Z-linear combinations of the elements {1, θ, θ2 , . . . , θd−1 }, forms a subring of OQ(θ) ,
denoted Z[θ].

It is this ring Z[θ] which we will use to find smooth values. By using Z-linear combinations
of the elements, we can ignore denominators in our representations of the elements. This
simplification does have some important consequences; our ring is now possibly a proper
subring of OQ(θ) , which causes some complications, which we shall resolve once we have
found smooth values in Z[θ].

3.2.3 Generating a congruence of squares

How then do we use the ring Z[θ] and a ring homomorphism to generate a congruence of
squares? Consider the following mapping: [35]

Proposition 3.7. Given f (x) satisfying the conditions of Proposition 3.6, a root θ ∈ C, and
m ∈ Z/nZ such that f (m) ≡ 0 (mod n), the function φ : Z[θ] → Z/nZ defined by:

φ(1) = 1 (mod n)
φ(θ) = m (mod n)

is a ring homomorphism.

We will use this homomorphism to construct the required congruence using smooth values
in Z[θ] and Z.

3.2. Rings of algebraic integers

Chapter 3. The General Number Field Sieve 31

Suppose we have found a set S of pairs of coprime integers (a, b) such that:

Y Y
(a + bθ) = β 2 for β ∈ Z[θ], and (a + bm) = y 2 for y ∈ Z (3.1)
(a,b)∈S (a,b)∈S

Then setting x = φ(β) and applying the homomorphism of Proposition 3.7 gives: [35]

 
Y Y Y
x2 ≡ φ(β)2 ≡ φ(β 2 ) ≡ φ  (a + bθ) ≡ φ(a+bθ) ≡ (a+bm) ≡ y 2 (mod n)
(a,b)∈S (a,b)∈S (a,b)∈S
(3.2)

The congruence of (3.2) is the heart of the Number Field Sieve. Note that in order to find
our factors using this congruence we must calculate (x + y, n) and (x − y, n). We therefore
need to find x, or what is equivalent, calculate the square root of a product of algebraic
numbers, a non-trivial procedure which we shall outline in §3.5. Conversely, finding y is
straight-forward as y 2 ∈ Z.

3.2.4 Choosing a suitable polynomial

To generate Z[θ], we require a monic, irreducible polynomial f (x) with integer coefficients.
A simple way of finding one is the base-m method. [10] We choose m first and construct our
1
polynomial to satisfy the condition f (m) ≡ 0 (mod n). m is chosen such that m ≈ n d .
Writing n in base-m then gives:

n = md + ad−1 md−1 . . . a1 m1 + a0 with 0 ≤ ai < m (3.3)

The coefficients in this expansion are used to construct the polynomial:

f (x) = xd + ad−1 xd−1 . . . a1 x + a0 (3.4)

By construction, f is monic and f (m) ≡ 0 (mod n) as required. However, f may be

reducible. In this case, there exists a polynomial-time algorithm [35] that will factor f into
its irreducible factors. Then f (x) = g(x)h(x) for some polynomials g(x), h(x), in which case
we can factorise n without needing to employ the GNFS. Otherwise, f (x) is irreducible as
required and we may proceed with sieving.

The base-m method was suggested in early papers on the GNFS. However, our initial choice
of polynomial can greatly affect the efficiency of the algorithm, with ‘tuned’ polynomials
yielding greater numbers of smooth values. This is a particularly active area of GNFS
research, for further details see [32] and [22].

3.2. Rings of algebraic integers

Chapter 3. The General Number Field Sieve 32

3.3 Factor bases in Z & Z[θ]

3.3.1 The rational factor base

By the congruence (3.2) and the definitions of (3.1), we need to find a set of coprime integers
Y Y
(a, b) such that the products (a + bθ) and (a + bm) are squares in their respective
(a,b)∈S (a,b)∈S
rings.
Y
To find (a + bm) square, we use essentially the same process as in the quadratic sieve,
(a,b)∈S
except we now have two variables a, b rather than the single variable x of (2.5).

In practice, we fix b ∈ Z and sieve over an interval [−u ≤ a ≤ u], seeking smooth values of
(a + bm). We then increment b by 1 and repeat the process.

Definition 3.8. The rational factor base is a set PR of primes p ≤ BR for some bound
BR .

To find the array positions for sieving, we note that p|(a + bm) ⇐⇒ a ≡ −bm (mod p).
Then ai = −bm + kp for some k ∈ Z and −u ≤ a ≤ u, so we can calculate all possible values
of ai in the interval. [8]

The array is initialised with the values of (a + bm) and we proceed to divide by p in the ai th
positions. The entire process is then repeated for the next p ∈ PR . We thus find smooth
values in a manner similar to that of the quadratic sieve. We must now extend the concept
of smoothness to the ring Z[θ].

3.3.2 The algebraic factor base

We begin with some definitions of algebraic number theory.

Definition 3.9. Let R be a ring. An element r ∈ R is a unit if ∃s ∈ R with rs = 1.

Definition 3.10. Let R be a ring. Two elements r, s ∈ R are associates if r = us with u

a unit of R.

Definition 3.11. A unique factorisation domain (UFD) is a ring R satisfying the fol-
lowing conditions: [40, §4.5]

ˆ Every r ∈ R that is not a unit is a product of irreducible elements of R.

3.3. Factor bases in Z & Z[θ]

Chapter 3. The General Number Field Sieve 33

ˆ If p1 , p2 , . . . pn , q1 , q2 , . . . qm ∈ R are irreducible and p1 p2 . . . pn = q1 q2 . . . qm then n = m

and pi , qi are associates.

The principal issue with extending the concept of smoothness is that Z[θ] is not necessarily
a unique factorisation domain. So the elements of Z[θ] may not be ‘factored’ uniquely into
irreducible elements. To resolve this, we instead consider factorisation of ideals into prime
ideals, which will be unique, provided we are working in a Dedekind domain.

Definition 3.12. A Dedekind domain is a ring R satisfying the following conditions:

ˆ R is a Noetherian Integral Domain. (Every ideal of R is finitely generated.)

ˆ Every non-zero proper ideal of R factors into prime ideals.

To find (a, b) pairs with (a + bθ) smooth, the general idea is to first choose an ‘algebraic’
factor base, a set of prime ideals of Z[θ]. We then consider the principal ideal ha + bθi
generated by each element (a + bθ) and check to see if it factorises completely into prime
ideals of our factor base. Those which do are smooth over the algebraic factor base and the
(a, b) pair is useful.

We now describe the details of determining smoothness in Z[θ]. We begin with an important
fact about the ring of integers.

Theorem 3.13. The ring of integers OK of a number field K is a Dedekind domain.

Proof. See [40, §5.2, Theorem 5.3]

This gives OQ(θ) the following important property:

Theorem 3.14. Every non-zero ideal of OQ(θ) can be written as a product of prime ideals,
uniquely up to the order of factors.

Proof. See [40, §5.2, Theorem 5.6]

We can use this property of the ring of integers to uniquely factorise ideals in the ring Q(θ)
into prime ideals and thereby extend our concept of smoothness. As the elements α ∈ Z[θ]
are algebraic integers, to simplify this approach we instead work with the norm of α.

Theorem 3.15. Let K = Q(θ) be a number field of degree d. Then there are exactly d
distinct monomorphisms σi : Q(θ) → C (i = 1, . . . , d).

Proof. See [40, §2.2, Theorem 2.4]

3.3. Factor bases in Z & Z[θ]

Chapter 3. The General Number Field Sieve 34

Definition 3.16. Let K = Q(θ) be a number field of degree d and let σ1 , . . . , σd be the d
monomorphisms σi : Q(θ) → C of Theorem 3.15.

The norm of an element α ∈ K is defined as: [40, §2.5]

n
Y
N (α) = σi (α)
i=1

We can also define the norm of an ideal:

Definition 3.17. Let I be a non-zero ideal. The norm of an ideal is defined as:

N (I) = |OK /I|

The following two results highlight the usefulness of these two functions.

Theorem 3.18. Given a monic, irreducible polynomial of degree d with integer coefficients,
a root θ ∈ C, and an element α ∈ Z[θ], N (α) is a multiplicative function N (α) : Z[θ] → Z.

Proof. See [40, §5.2]

Theorem 3.19. Given a monic, irreducible polynomial of degree d with rational coefficients,
a root θ ∈ C, and I a non-zero ideal of K, N (I) is a multiplicative function N (I) : OK → Z+ .
If a = hai is a principal ideal, then N (hai) = |N (a)|.

Proof. See [40, §5.3, Corollary 5.10]

Thus the norm conveniently maps elements α ∈ Z[θ] to integers. For a principal ideal
generated by α, the norm of the ideal is a positive integer and is equal to the absolute value
of the norm N (α). Rather than working with α ∈ C, we can now work with integers. To
simplify sieving, we restrict the algebraic factor base to first-degree prime ideals only. [8]

Definition 3.20. A first-degree prime ideal p of a Dedekind domain is a prime ideal such
that N (p) = p for some prime p.

This definition is justified by the following theorem, which relates prime ideals p to prime
numbers in Z.

Theorem 3.21. Let D be a Dedekind domain, and a an ideal of D:

ˆ If N (a) = p with p prime, then a is a prime ideal.

ˆ If a is a prime ideal, then N (a) = pm for some prime p with m ≤ d.

3.3. Factor bases in Z & Z[θ]

Chapter 3. The General Number Field Sieve 35

Proof. See [40, §5.3, Theorem 5.14]

First-degree prime ideals are convenient to work with as they may be simply represented by
pairs of integers (r, p), due to the following theorem:

Theorem 3.22. Let f (x) be a monic, irreducible polynomial with integer coefficients, and
θ ∈ C a root of f (x).

Consider the set of pairs (r, p) with r ∈ Z/pZ, f (r) ≡ 0 (mod p) and p a prime integer. There
exists a bijection between this set and the set of first-degree prime ideals of Z[θ].

Proof. We first require the following definitions:

Definition 3.23. A ring epimorphism is a surjective ring homomorphism.

Definition 3.24. The kernel of a ring homomorphism φ : R → S, denoted ker(φ), is the

set: ker(φ) = {r ∈ R : φ(r) = 0S }

We now show that each first-degree prime ideal maps to a unique (r, p) pair satisfying the
conditions of the theorem. Let p be a first-degree prime ideal of Z[θ]. Then N (p) = p for
some prime p by definition.

N (p) = p =⇒ Z[θ]/p ∼
= Z/pZ. There exists an epimorphism φ : Z[θ] → Z/pZ with
ker(φ) = p. [8, Theorem 3.1.7]

Let r = φ(θ) ∈ Z/pZ. Let f (x) = xd + ad−1 xd−1 . . . a1 x + a0 as in (3.4).

Then we have:

0 (mod p) ≡ φ (f (θ)) ≡ φ(θd + ad−1 θd−1 . . . a1 θ + a0 )

≡ φ(θ)d + ad−1 φ(θ)d−1 . . . a1 φ(θ) + a0

≡ rd + ad−1 rd−1 . . . a1 r + a0

≡ f (r) (mod p)

So r is a root of f (x) (mod p) and p maps to the unique pair (r, p). We now show that a
pair (r, p) with r ∈ Z/pZ, f (r) ≡ 0 (mod p) and p prime maps to a unique first-degree prime
ideal p.

There exists an epimorphism φ : Q[θ] → Q[r], φ(a) ≡ a (mod p) for all a ∈ Z and φ(θ) = r
(mod p). [8, Theorem 2.2.2]
Let ker(φ) = p so that p is an ideal of Z[θ]. Then Z[θ]/p ∼
= Z/pZ and N (p) = p. So (r, p)
maps to a unique first-degree prime ideal p of Z[θ].

3.3. Factor bases in Z & Z[θ]

Chapter 3. The General Number Field Sieve 36

Theorem 3.22 shows that there is a unique (r, p) representative for each first-degree prime
ideal in Z[θ]. We are finally in a position to define the algebraic factor base.

Definition 3.25. The algebraic factor base is a set PA of first-degree prime ideals of
Z[θ], represented by pairs (r, p) with r ∈ Z/pZ, f (r) ≡ 0 (mod p) and p a prime, p ≤ BA for
some bound BA . Each pair represents a unique first-degree prime ideal of Z[θ].

By the unique factorisation of a principal ideal hβi = pe11 pe22 . . . pekk to prime ideals pi , the
multiplicativity of N (α) and Theorems 3.19 and 3.21, we have: [8]

N (hβi) = |N (β)| = N (pe11 pe22 . . . pekk ) = N (pe11 )N (pe22 ) . . . N (pekk ) = (pf11 )e1 (pf22 )e2 . . . (pfkk )ek
(3.5)
for primes pi ; ei , fi ∈ Z+ and 1 ≤ i ≤ k.

Note that the primes need not be distinct, as the norms of different prime ideals may be
factorised by the same prime p, but to different powers. We now define a function that tracks
the powers of p in N (a + bθ) for (a + bθ) generating a principal ideal ha + bθi which factorises
fully over the algebraic factor base. [10, Remark 5.2]

Definition 3.26. Let f be a monic, irreducible polynomial of degree d with integer coeffi-
cients, and a root θ ∈ C.
Let (a, b) be coprime integers, p a prime integer and r ∈ R(p) = {r : f (r) ≡ 0 (mod p)}.

We define:

ordp (N (a + bθ)) if a + br ≡ 0 (mod p)

ep,r (a + bθ) =
0

otherwise

where ordp (N (a + bθ)) is the exponent of p in the prime factorisation of N (a + bθ).

Then by Definition 3.26,

Y
N (a + bθ) = ± pep,r (a+bθ)
p,r

To use the function ep,r we need to generalise for the case in which Z[θ] 6= OK . (This will
usually be the case in practice.) To do this, we consider the following group homomorphism.

Theorem 3.27. There exists, for each prime ideal pi ∈ Z[θ] a group homomorphism
lpi : Q(θ) → Z such that:

ˆ lpi (β) ≥ 0 for all β ∈ Z[θ], β 6= 0

3.3. Factor bases in Z & Z[θ]

Chapter 3. The General Number Field Sieve 37

ˆ lpi (β) > 0 if and only if pi divides hβi

Y
ˆ lpi = 0 for all but a finite number of pi ∈ Z[θ], and |N (β)| = N (pi lpi )

Proof. See §7 of [10] for an extended proof of this result.

Using this homomorphism, we obtain the following important results: [10, Corollary 5.5]

Theorem 3.28. Let (a, b) be coprime integers and p a prime ideal in Z[θ].
If p is not a first-degree prime ideal, then lp (a + bθ) = 0.

Proof. Let p be a prime ideal of Z[θ] with lp (a + bθ) > 0. As in Theorem 3.22, there exists
an epimorphism φ : Z[θ] → Z[θ]/p with ker(φ) = p.

Then Z[θ]/p ∼
= Fpe by Theorem 3.21, where Fpe is the finite field with pe elements and p
prime. So Z[θ]/p contains an isomorphic copy of Z/pZ.
lp (a + bθ) > 0 =⇒ p | ha + bθi by point 2 of Theorem 3.27, so (a + bθ) ∈ p.
Then ker(φ) = p =⇒ φ(a + bθ) ≡ 0 (mod p).

Suppose for a contradiction, p | b, then φ(b) ≡ 0 (mod p) and we have:

0 ≡ φ(a + bθ) ≡ a + b · φ(θ) ≡ a (mod p), so that p | a.
This is a contradiction as (a, b) = 1 by assumption. So p - b, which implies that b has an
inverse mod p.

0 ≡ a + b · φ(θ) (mod p) =⇒ b · φ(θ) ≡ −a (mod p).

Then bb−1 · φ(θ) ≡ −ab−1 (mod p) with b−1 the inverse of b mod p.
So φ(θ) ≡ −ab−1 (mod p), which implies φ(θ) ∈ Z/pZ and Im φ = Z/pZ.

Z[θ]/ker(φ) ∼
= Im φ and ker(φ) = p =⇒ Z[θ]/p ∼
= Z/pZ, so p is a first-degree prime ideal
of Z[θ] by Theorem 3.22. [8, Theorem 3.1.9]

Theorem 3.29. Let (a, b) be coprime integers and p a prime ideal in Z[θ].
If p is a first-degree prime ideal, corresponding to a pair (r, p), then lp (a + bθ) = ep,r (a + bθ).

Proof. Let lp (a + bθ) > 0. Then p | ha + bθi by Theorem 3.27 and (a + bθ) ∈ p.
Consider the epimorphism φ : Z[θ] → Z/pZ, with φ(θ) = r (mod p) and φ(a) = a (mod p)
for a ∈ Z. Then ker(φ) = p. (a + bθ) ∈ p =⇒ φ(a + bθ) ≡ 0 (mod p).
Then φ(a + bθ) ≡ a + br ≡ 0 (mod p).

Let a + br ≡ 0 (mod p) for the first-degree prime ideal p, represented by the pair (r, p).
Then a + br (mod p)≡ 0 ≡ φ(a + bθ) and a + bθ ∈ ker(φ). So a + bθ ∈ p.
a + bθ ∈ p =⇒ p | ha + bθi, so lp (a + bθ) > 0 by point 2 of Theorem 3.27.

3.3. Factor bases in Z & Z[θ]

Chapter 3. The General Number Field Sieve 38

We have shown lp (a + bθ) > 0 ⇐⇒ a + br ≡ 0 (mod p).

We now show for a first-degree prime ideal p represented by pair (r, p), that
p | N (a + bθ) ⇐⇒ a + br ≡ 0 (mod p). Then lp (a + bθ) = ep,r (a + bθ) as required.

Let σ1 , . . . , σd be the d monomorphisms σi : Q(θ) → C of Theorem 3.15.

By Definition 3.16:

N (a + bθ) = σ1 (a + bθ) · σ2 (a + bθ) · · · σd (a + bθ)

 a a a 
= bd ( + θ1 ) · ( + θ2 ) · · · ( + θd )
b b b
 a a a 
d
= (−b) (− − θ1 ) · (− − θ2 ) · · · (− − θd )
b b b
a
= (−b)d f (− )
b

So p | N (a + bθ) ⇐⇒ p | f (− ab ) as p - b.
p | f (− ab ) =⇒ f (− ab ) ≡ 0 (mod p), so a ≡ −br (mod p) for r with f (r) ≡ 0 (mod p). Thus
the (r, p) pair determines a first-degree prime ideal p.

To show uniqueness of the (r, p) pair corresponding to p, let lp1 (a+bθ) > 0 and lp2 (a+bθ) > 0
for first-degree prime ideals p1 & p2 , represented by pairs (r1 , p) and (r2 , p) respectively.
Then a + br1 ≡ 0 (mod p) and a + br2 ≡ 0 (mod p) =⇒ r1 ≡ r2 (mod p).
So p1 = p2 and the (r, p) pair with lp (a + bθ) > 0 is unique. [8, Theorem 3.1.9]

Applying Theorems 3.28 & 3.29, we have a way of determining whether an ideal factors over
the algebraic factor base; namely, it factors if N (a + bθ) factors completely into primes pi
of the (r, p) pairs that represent the first-degree prime ideals. Such an element (a + bθ) is
smooth over the algebraic factor base.

Now that we can find smooth values of (a+bθ), we need to consider how to find a square β 2 ∈
Z[θ] to satisfy the congruence (3.2). Unfortunately, the usual approach of forming a product
with only even exponents gives a necessary, but not sufficient, condition for constructing a
square β 2 ∈ Z[θ] (See Proposition 5.3 of [10]). This process ensures that N ( (a + bθ)) is a
Q
Q
square, which is not a strong enough condition to guarantee that (a + bθ) itself is a square
in Z[θ]. We consider the problem of finding β 2 ∈ Z[θ] in the next section.

3.3.3 Quadratic characters

Our issue arises, as mentioned previously, as we are working with ideals of Z[θ] and not of
OK (See §6 of [10] for further details). This problem was resolved by a proposal of Adleman.

3.3. Factor bases in Z & Z[θ]

Chapter 3. The General Number Field Sieve 39

[35] Adleman suggested the use of first-degree primes not in the factor base as a means of
Q
heuristically testing (a + bθ) for squareness in Z[θ].

Recall that our ring homomorphism in (3.2) is defined for β ∈ Z[θ]. In practice, we allow
Q
the product (a + bθ) to be square in Q(θ), rather than only Z[θ], as this is less restrictive.
By a clever use of the Legendre symbol, we can test the product for squareness in Z[θ]. We
first require a lemma of [10, 6.6]:

Y
Lemma 3.30. Let S be as in (3.1) and (a + bθ) = α2 for some α ∈ Q(θ).
(a,b)∈S

Let f be a monic, irreducible polynomial of degree d with integer coefficients, and a root θ ∈ C.
Y
Then α ∈ OQ(θ) and f 0 (θ)2 · (a + bθ) is a square in Z[θ].
(a,b)∈S

Y
Theorem 3.31. Let S be a set of pairs of coprime integers (a, b) with (a + bθ) = α2
(a,b)∈S
for some α2 ∈ Q(θ). Let q be an odd prime and s ∈ R(q) with R the set in Definition 3.26,
such that:

ˆ a + bs 6= 0 (mod q) for each (a, b) ∈ S

ˆ f 0 (s) 6= 0 (mod q)

Then:
Y  a + bs 
=1 (3.6)
q
(a,b)∈S

Proof. Let q be the kernel of the ring homomorphism φ : Z[α] → Fq which maps θ to s (mod
q). Then q corresponds to the pair (s, q).

Define χq : Z[θ] − q → {±1} as the composition of Z[θ] − q → Fq − {0} with the Legendre
symbol Fq − {0} → {±1}.
Y
Then χq (a + bθ) = ( a+bs 0 2
q ). We have by the previous lemma that f (θ) · (a + bθ) =
(a,b)∈S
δ 2 ∈ Z[θ] for some δ.

As the factors are not in q, δ ∈

/ q, then applying χq gives the result. [10, Proposition 8.3]

To put this theorem to use, we essentially generate a further set PQ of first-degree prime
ideals not in the algebraic factor base.

3.3. Factor bases in Z & Z[θ]

Chapter 3. The General Number Field Sieve 40

Definition 3.32. The quadratic character base PQ is a set of first-degree prime ideals,
represented by (s, q) pairs with pA < qi , where pA is the largest prime in the (r, p) pairs of
the algebraic factor base.

Y
By checking that (3.6) holds across all (s, q) pairs in PQ , it is highly likely that (a + bθ)
(a,b)∈S
is a square. By adding more (s, q) pairs to PQ , we can increase this probability.

To summarise , we have developed methods for testing whether an (a, b) pair is smooth over
Y
the algebraic factor base, and can test whether the product of such pairs (a + bθ) is a
(a,b)∈S
likely square in Z[θ]. In the next section, we outline how to apply these ideas to construct
the algebraic sieve.

3.4 Sieving

3.4.1 Technical implementation of the sieve

To sieve in Z[θ], we use a procedure almost identical in form to the sieving process in Z
outlined in §3.3.1. By Theorem 3.29, N (a + bθ) factorises over the primes of (r, p) ∈ PA if
and only if, a + br ≡ 0 (mod p).

Note that p | ha + bθi ⇐⇒ a ≡ −br (mod p). Then a = −br + kp for some k ∈ Z.

To sieve, we again fix b and sieve over an interval [−u ≤ a ≤ u]. Once the positions are
calculated, we initialise the sieve with the values N (a + bθ) and divide by p at the ai th
positions where ai = −br + kp. We then increment b and the process is repeated until
enough smooth values have been obtained.

Sieving in Z[θ] is thus ostensibly identical to sieving in Z, which simplifies computer imple-
mentation of the GNFS. One further point of implementation is to store the elements of PR
as pairs of integers (m (mod p), p), to align with the form of elements of PA . This further
simplifies the sieving code. [8, §3.8]

3.4.2 The Lanczos algorithm

Once we have found enough simultaneously smooth values in Z[θ] and Z, we need to perform
the linear algebra step to find a set S such that (3.1) holds. Due to the large size of the factor
base used in a GNFS factorisation, the exponent matrix becomes increasingly unwieldy to
work with. To give an idea of the size of this matrix, we first show the form of a binary

3.4. Sieving
Chapter 3. The General Number Field Sieve 41

vector vi representing an (a, b) pair with (a + bm) and (a + bθ) smooth over their respective
factor bases.
Exponents of pi ∈PR Quadratic character bits
z }| { z }| {
vi = |{z}
0 0 1 0 0 0 1 . . . 0 |1 1 0 1 1 {z
0 0 0 . . . 1} 0 0 1 1 0 0 . . . 0
Sign bit Exponents of pi ∈PA


0

if a + bm > 0
With the sign bit =
1

otherwise

To preserve multiplicity,for each (s, q) ∈ PQ , the corresponding quadratic character bit is

0 if a+bs
q =1


set as follows: PQ bit =
1 otherwise


Therefore, if there are k primes in FR , l first-degree prime ideals in FA , and m first-degree

prime ideals in FQ , the vector will consist of 1 + k + l + m bits. [8] For this reason, rather
than using Gaussian elimination to find a dependency, the block Lanczos algorithm is used.
This algorithm is particularly suited to dealing with a large, sparse matrix.

For further details on the block Lanczos algorithm, see [30].

3.5 Calculating the square root

After sieving and linear algebra processing, we obtain a set S of (a, b) pairs satisfying (3.1).
One final issue is that in order to calculate (x ± y, n) and obtain a factorisation, we need to
calculate x = φ(β).

We know that β ∈ Z[θ], so it may be written β = ad−1 θd−1 + ad−2 θd−2 + · · · + a1 θ + a0 .

Letting x = ad−1 md−1 + ad−2 md−2 + · · · + a1 m + ao , then satisfies the congruence (3.2). [8]
Y
As β 2 ∈ Z[θ] = (a+bθ), β 2 is the product of a very large number of algebraic numbers,
(a,b)∈S
so calculating the square root β directly is difficult.

There are a number of solutions to this problem, as discussed in [43]. We shall sketch one of
the earlier ideas, proposed by Couveignes in [12]. By a clever use of the Chinese Remainder
theorem, we can circumvent the difficulties of finding β and calculate x without requiring
intermediate values.

3.5. Calculating the square root

Chapter 3. The General Number Field Sieve 42

Theorem 3.33. The Chinese Remainder theorem:

Let p1 , p2 , . . . , pk be distinct primes and x1 , x2 . . . , xk any integers.
Y k
Set P = pi , Pi = P/pi , and ai = Pi−1 (mod pi ).
i=1

For the congruences:

z ≡ x1 (mod p1 )

z ≡ x2 (mod p2 )
..
.

z ≡ xk (mod pk )
k
X
z= ai xi Pi is the unique solution modulo P .
i=1

Proof. See [20, Theorem 3.10]

Our approach is to calculate x modulo primes pi , which can be done efficiently by the Shanks-
Tonelli algorithm, amongst other methods. If we use enough primes such that their product
P > x, and solve the system of congruences by Theorem 3.33, then we find x ≡ z (mod P ).

By rounding z/P to the nearest integer r = b Pz + 12 c, we have x = z − rP . [12] We can

calculate r efficiently without needing to calculate z directly by the following:
Pk
z ai xi Pi
= i=1
P P
Pk P
i=1 ai xi pi
=
P
k
X ai xi
=
pi
i=1
Pk ai xi
So r = b( i=1 pi ) + 12 c. We now calculate x (mod n) as follows: [8]

x (mod n) = z − rP (mod n)

= z (mod n) − rP (mod n)
k
X
= ai xi Pi (mod n) − rP (mod n)
i=1
k k
X X ai xi 1
= ai xi Pi (mod n) − b( ) + cP (mod n)
pi 2
i=1 i=1

In this manner, none of the intermediate values calculated will exceed n and x can be found
efficiently. For further details on calculating x (mod pi ), see [12] and [8, §4.7 & §4.8].

3.5. Calculating the square root

Chapter 3. The General Number Field Sieve 43

Y
Once x has been computed, we calculate the square root of y 2 = (a + bm) and generate
(a,b)∈S
our required congruence (3.2). Finally, we calculate (x ± y, n) and the factorisation of n is
complete.

3.5. Calculating the square root

Chapter 4

Time complexity

4.1 Big O notation

In order to compare the efficiency of the algorithms presented in previous chapters, we now
outline their time complexities. To measure time complexity, we consider the algorithm’s
asymptotic behaviour, that is, the number of elementary operations required to complete the
algorithm in the worst-case scenario. By design, an RSA modulus n, being a large semiprime
with no small prime factors, represents the worst-case for factorising.

To describe the time complexity of an algorithm, we use Big O notation. [39, §7]

Definition 4.1. Big O notation:

Let f be a function f : C → C and g a real valued function.

Then we say f (x) ∈ O(g(x)) as x → ∞ if ∃C, x0 ∈ R such that |f (x)| ≤ Cg(x) for all x ≥ x0 .

For the remainder of the chapter, let f (x) represent the number of elementary operations
of an algorithm as a function of the size of the input. When working with large inputs, the
highest order of the expression for running time dominates the other terms, so it is this term
that describes the asymptotic behaviour.

Example 4.2. The total number of steps taken to complete an algorithm with input x is
f (x) = 7x5 + 3x3 + 2x + 1.

The x5 term will dominate the runtime for large inputs, with the constant coefficient 7 having
relatively minimal effect.

We write f (x) ∈ O(x5 ).

44
Chapter 4. Time complexity 45

Some common time complexities are shown in Figure 4.1 below:

Figure 4.1: Comparison of common time complexities

As the runtime grows with the size of the input, the theoretical time complexity of the
algorithm translates directly to the amount of real-world computing time required to run
the algorithm.

Definition 4.3. We say that a problem is tractable [42, §2.4] if there is an algorithm to
solve it that runs in polynomial time or faster; i.e. f (x) ∈ O(xn ) for some n ∈ N.

It is important to note that an expression for the time complexity of an algorithm is de-
pendent upon the encoding of the input. [42] For our purposes, the RSA modulus n is
encoded in binary and therefore the input has size log2 (n) bits. So a function f (n) ∈ O(n)
is exponential in the size of the input.

We now outline the time complexities of the algorithms discussed in §2. We begin with the
exponential time algorithms.

4.2 Exponential time algorithms

k
Definition 4.4. An algorithm has exponential running time if f (x) ∈ O(2x ) for some
constant k.

4.2. Exponential time algorithms

Chapter 4. Time complexity 46

4.2.1 Trial division

√
As we may need to divide by all prime numbers up to n, the worst case running-time for
trial division depends on the number of primes less than n. This number is given by the
prime-counting function π(x), which by the prime number theorem is asymptotically:

Theorem 4.5. Prime number theorem:

x
π(x) ∼
ln x
Proof. See §22 of [18].

For an r-bit number, we need to check up to π(2r/2 ) primes. By Theorem 4.5:

2r/2
π(2r/2 ) ≈
ln 2r/2
2r/2
≈ r
2 ln 2

2r/2 r
So we need to make approximately r trial divisions, so f (x) ∈ O(2 2 ), which is expo-
2 ln 2
nential in the size of the input.

4.2.2 Fermat’s method

n+1 √
 
In the worst case, Fermat’s method will take up to − n steps to find a square
2
and generate a factor. [45]
√
Fermat’s method therefore has time complexity O( n), which is also exponential in the size
of the input.

4.2.3 Euler’s method

Provided n does not satisfy the conditions of Theorem 2.8, it can be factorised using Euler’s
√
method in time O( n).

4.2.4 Pollard’s rho algorithm

By considering the Birthday Paradox, for a prime p dividing n we would expect a sequence
√
of f (xi )’s to cycle before O( p) steps. [13, §5.2] This is only conjectured, as it is based on
the assumption that the f (xi ) values behave like random numbers. Pollard’s rho thus has
√ √
time complexity O( p) ≤ O( 4 n), so is heuristically exponential in the size of the input.

For a more rigorous analysis of Pollard’s rho algorithm, see [1].

4.2. Exponential time algorithms

Chapter 4. Time complexity 47

4.3 Subexponential time algorithms

We now consider the subexponential time algorithms, which are asymptotically faster than
the previous algorithms. We first require some additional notation.

Definition 4.6. Little-o notation:

Let f be a function f : C → C and g a real valued function.

Then we say f (x) ∈ o(g(x)) as x → ∞ if ∀ε ∈ R+ , ∃C such that |f (x)| ≤ εg(x) for all x ≥ C.

Little-o notation is used to show that a function f (x) grows much more slowly than some
function g(x).

Definition 4.7. An algorithm has subexponential running time if f (x) ∈ 2o(n) where o(n)
represents little-o notation as in Definition 4.6.

4.3.1 Dixon’s algorithm

Dixon’s algorithm was the first subexponential algorithm with a rigorous proof of its runtime,
hence its primacy in the discussion of §2.
 √ √ 
Proposition 4.8. Dixon’s method has expected runtime O e((3 2) ln n ln ln n)

We outline the derivation of this runtime with a sketch proof.

Suppose we have a list of integers L of length N in the range [1, n]. We seek values xi in this
range such that f (xi ) = x2i (mod n) is B-smooth. We choose xi ∈ L randomly and factorise
x2 (mod n) to determine whether it is B-smooth. This factorisation step takes O(B ln n)
operations. [15] Once B+1 B-smooth values are found, we proceed to the linear algebra step.
Gaussian elimination requires O(B 3 ) operations. The final step of calculating a gcd requires
O(ln n) operations.

Thus, the method can be reduced to an optimisation problem in which we select our bound B
on the factor base to minimise the number of f (xi )’s that need to be checked for smoothness.
We must also optimise the length N of our list L such that we are almost certain to find
enough smooth values of f (xi ).
√
(2 ln n ln ln n)
Proposition 4.9. Set B = e and N = (B 2 + 1). Then the average number of
 √ √ 
operations to factorise by Dixon’s algorithm is O e((3 2) ln n ln ln n) .

Proof. See §3 of [15].

4.3. Subexponential time algorithms

Chapter 4. Time complexity 48

As the general-purpose algorithms we have discussed may be considered optimisations of

Dixon’s algorithm, the derivation of their runtimes is similar. One major heuristic assump-
tion is that the numbers that are checked for smoothness in each algorithm (Pomerance
calls these ‘auxiliary numbers’ ) have the same probability of being smooth as a randomly
generated number of the same size. This may not necessarily be the case, as our generating
function may be particularly good (or bad) at generating smooth values. Thus, the key
to speeding up algorithms of this form is to generate smaller auxiliary numbers, which are
therefore more likely to be smooth, allowing relations to be found faster.

4.3.2 Continued Fraction method

Although the Continued Fraction method was the first subexponential algorithm, its runtime
has not been rigorously proved. Heuristically, the Continued Fraction method has expected
 √ 
runtime O e( 2 ln n ln ln n) . [45]

4.3.3 The Quadratic Sieve

The Quadratic Sieve improves upon earlier methods by checking for smoothness far more
quickly using the sieving process discussed in §2.3.4. This improves its expected runtime to
 √ 
O e( ln n ln ln n) . [35]

4.3.4 The General Number Field Sieve

The major speedup of the GNFS comes through generating auxiliary numbers bounded
0 1 2
by ec (ln n) (ln ln n) with c0 a constant. [35] This compares favourably with the auxiliary
3 3

√
numbers used in the Quadratic Sieve, which are around the size n.
 1 2
 q
This gives the GNFS expected running time O e c(ln n) 3 (ln ln n) 3
with c = 3 64
9 . [35]

See [28] for further discussion on the heuristic runtime of the GNFS.

4.3. Subexponential time algorithms

Chapter 5

Summary

The introduction of the RSA cryptosystem has stimulated significant research into a canon-
ical ‘hard’ problem. Since then, Legendre’s congruence has been fruitfully mined to produce
the current fastest known algorithm, the General Number Field Sieve. In 2009, Kleinjung
et al. factorised the 768-bit number RSA-768 using the GNFS. The sieving process was
distributed, taking almost two years, and the entire computation took more than 1020 oper-
ations. The team optimistically predicted that a 1024-bit modulus could be factored ‘...well
within the next decade.’ [23].

Although their prediction was not borne out, the factorisation of RSA-250, an 829-bit num-
ber, was announced on February 28th , 2020. [46] With the consistent increase in compu-
tational power, such records will continue to fall. However, without a further theoretical
breakthrough, ever larger keys should guarantee the security of RSA for the foreseeable fu-
ture. While the time complexity of our best algorithms remains non-polynomial, the problem
of factorising a large integer remains insurmountable.

One potential challenge to the security of RSA lies in recent developments in quantum com-
puting. In 1994, Peter Shor published a quantum algorithm that factorises n in O (log n)2+ .

[45] However, this polynomial-time algorithm remains theoretical until the development of
viable quantum computers. History has shown that even the most seemingly impregnable
cryptosystems eventually succumb to the determined cryptanalyst. Given that the RSA
problem is well-defined and understood, it seems inevitable that it too will eventually be
broken. The question remains: will this be via a classical theoretical, or a quantum techno-
logical, breakthrough?

49
Bibliography

[1] Bach, E. (1991). Toward a theory of Pollard’s rho method. Information and Computation,
90(2), 139-155.

[2] Barker, E., & Dang, Q. (2015). NIST special publication 800–57 part 3: Application-
specific key management guidance. NIST Special Publication, 800, 57.

[3] Bhaskar, J. (2008). Sum of two squares. University of Chicago (REU 2008).

[4] Brent, R. P., & Pollard, J. M. (1981). Factorization of the eighth Fermat number. Mathe-
matics of Computation, 36(154), 627. https://doi.org/10.1090/s0025-5718-1981-0606520-
5

[5] Brent, R. P. (1980). An improved Monte Carlo factorization algorithm. BIT, 20(2),
176–184. https://doi.org/10.1007/bf01933190

[6] Brent, R. P. (1999). Factorization of the tenth Fermat number. Mathematics of Compu-
tation, 68(225), 429–452. https://doi.org/10.1090/s0025-5718-99-00992-8

[7] Brent, R. P. (2000). Recent progress and prospects for integer factorisation algorithms.
In International Computing and Combinatorics Conference (pp. 3-22). Springer, Berlin,
Heidelberg.

[8] Briggs, M. E. (1998). An introduction to the general number field sieve (Dissertation,
Virginia Tech).

[9] Brillhart, J. (2009). A note on Euler’s factoring problem. The American Mathematical
Monthly, 116(10), 928-931.

[10] Buhler, J. P., Lenstra, H. W., & Pomerance, C. (1993). Factoring integers with the
number field sieve. In The development of the number field sieve (pp. 50-94). Springer,
Berlin, Heidelberg.

50
Bibliography 51

[11] da Costa Boucinha, F. (2011). A survey of cryptanalytic attacks on RSA. Instituto

superior técnico, Universidade Técnica de Lisboa.

[12] Couveignes, J. M. (1993). Computing a square root for the number field sieve. In The
development of the number field sieve (pp. 95-102). Springer, Berlin, Heidelberg.

[13] Crandall, R., & Pomerance, C. B. (2010). Prime Numbers: A Computational Perspective
(2nd ed.). Springer.

[14] Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE transactions
on Information Theory, 22(6), 644-654.

[15] Dixon, J. D. (1981). Asymptotically fast factorization of integers. Mathematics of Com-

putation, 36(153), 255. https://doi.org/10.1090/s0025-5718-1981-0595059-1

[16] Galbraith, S. (2012). The Mathematics of Public Key Cryptography. Cambridge: Cam-
bridge University Press.

[17] Gardner, M. (1977, August). Mathematical Games. In Scientific American. New York:
Munn & Co.

[18] Hardy, G. H., & Wright, E. M. (1979). An introduction to the theory of numbers. Oxford
University Press.

[19] Jensen, P. L. (2005). Integer factorization. University of Copenhagen.

[20] Jones, G. A., & Jones, J. M. (1998). Elementary Number Theory (Springer Undergrad-
uate Mathematics Series) (Corrected ed.). Springer.

[21] Khinchin, Y. A. (1997). Continued Fractions (Dover Books on Mathematics) (Revised

ed.). Dover Publications.

[22] Kleinjung, T. (2006). On polynomial selection for the general number field sieve. Math-
ematics of Computation, 75(256), 2037–2047. https://doi.org/10.1090/s0025-5718-06-
01870-9

[23] Kleinjung, T., Aoki, K., Franke, J., Lenstra, A. K., Thomé, E., Bos, J. W., ... &
Zimmermann, P. (2010, August). Factorization of a 768-bit RSA modulus. In Annual
Cryptology Conference (pp. 333-350). Springer, Berlin, Heidelberg.

[24] Lehman, R. S. (1974). Factoring large integers. Mathematics of Computation, 28(126),

637.

Bibliography
Bibliography 52

[25] Lehmer, D. H., & Powers, R. E. (1931). On factoring large numbers. Bulletin of the
American Mathematical Society, 37(10), 770–777. https://doi.org/10.1090/s0002-9904-
1931-05271-x

[26] Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1993). The factor-
ization of the ninth Fermat number. Mathematics of Computation, 61(203), 319-349.

[27] Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1993). The number
field sieve. In The development of the number field sieve (pp. 11-42). Springer, Berlin,
Heidelberg.

[28] Lenstra, A. K. (2000). Integer factoring. Towards a quarter-century of public key cryp-
tography, 31-58.

[29] Lenstra, H. W. (1987). Factoring Integers with Elliptic Curves. The Annals of Mathe-
matics, 126(3), 649. https://doi.org/10.2307/1971363

[30] Montgomery, P. L. (1995, May). A block Lanczos algorithm for finding dependencies over
GF (2). In International Conference on the Theory and Applications of Cryptographic
Techniques (pp. 106-120). Springer, Berlin, Heidelberg.

[31] Morrison, M. A., & Brillhart, J. (1975). A Method of Factoring and the Factorization
of F7 . Mathematics of Computation, 29(129), 183. https://doi.org/10.2307/2005475

[32] Murphy, B. A. (1999). Polynomial selection for the number field sieve integer factorisa-
tion algorithm. Australian National University.

[33] Pollard, J. M. (1975). A monte carlo method for factorization. BIT, 15(3), 331–334.
https://doi.org/10.1007/bf01933667

[34] Pomerance C. (1985). The Quadratic Sieve Factoring Algorithm. In: Beth T., Cot N.,
Ingemarsson I. (eds) Advances in Cryptology. EUROCRYPT 1984. Lecture Notes in
Computer Science, vol 209. Springer, Berlin, Heidelberg.

[35] Pomerance, C. (1996). A tale of two sieves. In Notices Amer. Math. Soc.

[36] Progress in general purpose factoring. (2017, October 8). AI Impacts.

https://aiimpacts.org/progress-in-general-purpose-factoring/

[37] Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital
signatures and public-key cryptosystems., Communications of the ACM, 21(2), 120–126.

Bibliography
Bibliography 53

[38] Silverman, R. D. (1987). The multiple polynomial quadratic sieve. Mathematics of Com-
putation, 48(177), 329. https://doi.org/10.1090/s0025-5718-1987-0866119-8

[39] Sipser, M. (2014). Introduction to the Theory of Computation (3rd ed.). Cengage India.

[40] Stewart, I., & Tall, D. (2001). Algebraic Number Theory and Fermat’s Last Theorem:
Third Edition (3rd ed.). A K Peters/CRC Press.

[41] Stinson, D. R., & Paterson, M. (2018). Cryptography: Theory and Practice (Textbooks
in Mathematics) (4th ed.). Chapman and Hall/CRC.

[42] Talbot, J., and Welsh, D. (2006). Complexity and Cryptography: An Introduction (1st
ed.). Cambridge University Press.

[43] Thomé, E. (2012, July). Square root algorithms for the number field sieve. In Inter-
national Workshop on the Arithmetic of Finite Fields (pp. 208-224). Springer, Berlin,
Heidelberg.

[44] Tornarı́a, G. (2002, April). Square roots modulo p. In Latin American Symposium on
Theoretical Informatics (pp. 430-434). Springer, Berlin, Heidelberg.

[45] Yan, S. Y. (2010). Primality Testing and Integer Factorization in Public-Key Cryptog-
raphy (Advances in Information Security, 11) Springer.

[46] Zimmerman, P. (2020) Factorisation of RSA-250. https://listserv.nodak.edu/cgi-

bin/wa.exe?A2=NMBRTHRY;dc42ccd1.2002

Bibliography