WillemdeGraaf - Strutture | UniTrentodegraaf/compalg/compalg.pdf · 2 Gro¨bner Bases A more...

Computational Algebra

Willem de Graaf

Contents

1 Grobner Bases 1

1.1 Grobner bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Polynomial rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.2 Polynomials in one indeterminate . . . . . . . . . . . . . . . . . . . . . 3

1.1.3 Monomial orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.4 Polynomial division for multivariate polynomials . . . . . . . . . . . . 5

1.1.5 Monomial ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.6 Grobner bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.1.7 Computing Grobner bases . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2 Applications of Grobner bases . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.2.1 Solving polynomial equations . . . . . . . . . . . . . . . . . . . . . . . 16

1.2.2 Applications of Grobner bases in geometry . . . . . . . . . . . . . . . 20

1.2.3 An application in combinatorics: Alon’s non-vanishing theorem . . . . 24

1.2.4 An application in cryptography: Polly-cracker . . . . . . . . . . . . . . 26

1.2.5 Solving Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2 Integer Factorisation 33

2.1 The Miller-Rabin primality test . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.2 Factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.2.1 The method of Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.2.2 The continued fraction method (CFRAC) . . . . . . . . . . . . . . . . 37

2.2.3 The elliptic curve method (ECM) . . . . . . . . . . . . . . . . . . . . . 47

2.2.4 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

2.3 Primality proving with elliptic curves . . . . . . . . . . . . . . . . . . . . . . . 56

2.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3 Polynomial Factorisation 59

3.1 Some generalities on polynomials . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.2 Berlekamp’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.3 The algorithm of Cantor-Zassenhaus . . . . . . . . . . . . . . . . . . . . . . . 65

3.4 Factorisation of polynomials over Q . . . . . . . . . . . . . . . . . . . . . . . . 67

3.4.1 Hensel lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

3.4.2 Hensel lifting for more factors . . . . . . . . . . . . . . . . . . . . . . . 74

3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

iv

4 Lattice Basis Reduction 774.1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774.2 Properties of Gram-Schmidt orthogonalisation . . . . . . . . . . . . . . . . . . 784.3 Reduced lattice bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 804.4 The LLL algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.4.1 Reduce(k, l) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824.4.2 Exchange(k) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.5 The knapsack cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Chapter 1

Grobner Bases

The term “Grobner bases” was introduced by Bruno Buchberger

in his 1965 Ph.D. thesis (An algorithm for finding the basis elements of the residue classring of a zero dimensional polynomial ideal, University of Innsbruck) under the supervisionof Wolfgang Grobner. However, similar notions in different settings were around before thatdate, and have been developed since. In 1900 Gordan appears to have used a very similarconcept. Furthermore, a “Grobner basis theory” for free Lie algebras was developed byShirshov in 1962 (Some algorithmic problems for Lie algebras, Sib. Mat. Zh). Also, theso-called Knuth-Bendix algorithm (Knuth and Bendix, Simple word problems in universalalgebra, 1970) is a similar development in the theory of finitely-presented groups.

In this chapter we describe the theory of Grobner bases, and some of its applications, forideals in a polynomial ring.

Throughout we use the notation N = Z≥0.

1.1 Grobner bases

1.1.1 Polynomial rings

Throughout k will denote a field, and k[x1, . . . , xn] will be the polynomial ring in n indeter-minates, with coefficients in k. That is

k[x1, . . . , xn] = {∑

i1,...,in

ci1...inxi11 · · · xinn | ci1...in ∈ k}.

Example 1.1.1 In the cases where we have one, two or three indeterminates we also write,respectively, k[x], k[x, y] and k[x, y, z].

2 Grobner Bases

A more compact notation for the exponents is useful on many occasions. For α =(α1, . . . , αn), αi ∈ N, we define xα = xα1

1 · · · xαnn . Such an element is called a monomial.

Example 1.1.2 x2yz10 is a monomial, and 2x2y + 3yz is a polynomial.

So in general we can write a polynomial as∑

α cαxα.

Recall that a ring R is said to be commutative if fg = gf for all f, g ∈ R. So polynomialrings are commutative.

Definition 1.1.3 Let R be a commutative ring. A subset I ⊂ R is called an ideal if

- 0 ∈ I;

- if f, g ∈ I then also f + g ∈ I;

- if f ∈ I and g ∈ R then gf ∈ I.

In this chapter we deal exclusively with polynomial rings k[x1, . . . , xn]. In such rings wehave a particular class of examples of ideals, which are described as follows.

Let f1, . . . , fs ∈ k[x1, . . . , xn] and set

I = {s∑

i=1

gifi | gi ∈ k[x1, . . . , xn]}.

Then obviously I is an ideal of k[x1, . . . , xn]. Later we will see that every ideal of k[x1, . . . , xn]is of this form.

Notation. We will denote the ideal I above with I = 〈f1, . . . , fs〉, and say that I isgenerated by f1, . . . , fs.

Fundamental problem: “Given I = 〈f1, . . . , fs〉 and g ∈ k[x1, . . . , xn] decide whetherg ∈ I.”

Example 1.1.4 Let R = k[x, y, z], f1 = xyz − xy, f2 = x2y − yz and g = yz2 − yz. Thequestion is whether g ∈ 〈f1, f2〉.

Observe that

xf1 − zf2 = −x2y + yz2

so we add f2 and find

xf1 − zf2 + f2 = yz2 − yz = g

and hence g = xf1 + (1− z)f2 ∈ 〈f1, f2〉.

Example 1.1.5 Let I ⊂ k[x, y, z] be the ideal generated by f1 = x2yz − yz − x, f2 =xy2z − xy − y, f3 = xyz2 − xy − z. Then x2 − z2 and y − z lie in I. But it certainly is notobvious.

We see that checking whether g ∈ 〈f1, . . . , fs〉 can be a rather complicated thing. But atleast we know that we have to find hi with g =

∑i hifi. To show that g 6∈ 〈f1, . . . , fs〉 seems

even more difficult.

1.1 Grobner bases 3

1.1.2 Polynomials in one indeterminate

If we are dealing with polynomials in a single indeterminate, then the fundamental problemhas an easy solution.

Lemma 1.1.6 Let I ⊂ k[x] be an ideal. Then there exists h ∈ k[x] with I = 〈h〉.

Proof. Let h be a nonzero element of I, of minimal degree. Let f ∈ I. Then f = qh + rwith q, r ∈ k[x] and deg(r) < deg(h).

Since r = f − qh ∈ I we get that r = 0 as h is of minimal degree in I. It follows thatf = qh. �

Now let I = 〈h〉 ⊂ k[x] and f ∈ k[x]. From the proof of the preceding lemma we get thefollowing procedure to check whether f ∈ I:

1) Write f = qh+ r with deg(r) < deg(h). (Polynomial division.)

2) If r = 0 then f ∈ I otherwise f 6∈ I.

(Note that if I is generated by h, then h is of minimal degree in I.)We want to find some analogous procedure in the multivariate case. The key remark is

that in the case of one indeterminate we use the degree of a polynomial. In other words, weuse an ordering on the monomials: xm < xn if m < n. We start by generalising that to themultivariate situation.

1.1.3 Monomial orders

Recall the notation xα = xα1

1 · · · xαnn , where α = (α1, . . . , αn).

Definition 1.1.7 An order ≤ on the set {xα} of the monomials of k[x1, . . . , xn] is called amonomial order if

1) ≤ is total, that is, for all α, β we have xα ≤ xβ or xβ ≤ xα.

2) ≤ is multiplicative, that is, if xα ≤ xβ then xαxγ ≤ xβxγ for all γ.

3) There are no infinite descending chains xα(1) > xα(2) > . . . (in other words, ≤ is a well-ordering).

We identify {xα | α ∈ Nn} and Nn by xα ↔ α.So from an order ≤ on the set of monomials we get an order on Nn by α < β if xα < xβ.

Then the conditions for ≤ to be a monomial order translate to:

1) ≤ is total.

2) If α ≤ β then α+ γ ≤ β + γ for all γ.

3) There are no infinite descending chains.

In the following, when we speak about monomial orders we freely interchange between anorder on the set of monomials and on Nn, whichever is the most convenient.

The following observation is useful.

4 Grobner Bases

Lemma 1.1.8 Set γ0 = (0, . . . , 0) ∈ Nn and let ≤ be a monomial order. Then α > γ0 for allα ∈ Nn, α 6= γ0.

Proof. If α < γ0 then α+α < α+ γ0 = α. In the same way we find that (k+1)α < kα. Sowe have constructed an infinite descending set. �

Example 1.1.9 (Lexicographical order.) This order is denoted <lex. By definition, α <lex βif αi < βi where i is the minimal index with αi 6= βi.

For example in k[x, y, z] we have

xy2z100 <lex x2yz

andxyz <lex xy

3.

The claim is that <lex is a monomial order.Proof. 1) It is obvious that it is a total order: if α 6= β then there is an index i with αi 6= βi.

2) Suppose that α <lex β and let i be minimal with αi 6= βi, and hence αi < βi. Then iis also the minimal index with (α+ γ)i 6= (β + γ)i and

(α+ γ)i = αi + γi < βi + γi = (β + γ)i.

Therefore (α+ γ) <lex (β + γ).3) The most difficult thing to show is that there are no infinite descending chains. For

this we use induction on n (i.e., the number of indeterminates).For n = 1 it is obvious that there are no infinite descending chains (here the order reduces

to the normal degree order).Assume that there are no infinite descending chains, with respect to <lex, when there

are n − 1 indeterminates. Also suppose that there is an infinite descending chain α(1) >lex

α(2) >lex . . ., with α(i) ∈ Nn.Observe that 0 ≤ α(i)1 ≤ α(1)1.Hence

{α(i) | i ≥ 1} =

α(1)1⋃

k=0

Ck

where Ck = {α(i) | i ≥ 1, α(i)1 = k}.So there has to be a k0 with Ck0 infinite. Then we set Ck0 = {(α2, . . . , αn) | α ∈ Ck0}.But this is an infinite descending chain with respect to the <lex order on n− 1 indetermi-

nates. So we have our contradiction. �

Example 1.1.10 (Graded lexicographical order.) Notation <glex.Define |α| = α1 + . . .+αn; this is the degree of the monomial xα. By definition α <glex β

if

- |α| < |β|

- or |α| = |β| and α <lex β.

It is obvious that <glex is a monomial order.

1.1 Grobner bases 5

1.1.4 Polynomial division for multivariate polynomials

As before we write R = k[x1, . . . , xn]. In this section we fix a monomial order ≤ on Nn.Let f =

∑α cαx

α ∈ k[x1, . . . , xn], and let α be maximal with respect to ≤ with cα 6= 0.Then xα is called the leading monomial of f , and denoted LM(f), whereas cα is called theleading coefficient and denoted by LC(f).

With this notation we have the following division algorithm, which is a generalisation ofthe division algorithm for polynomials in one indeterminate.

Algorithm 1.1.11 (Polynomial division with remainder)Given: f1, . . . , fs ∈ R, g ∈ R.We compute: r ∈ R such that g = h1f1 + . . . + hsfs + r with hi ∈ R and no monomial of

r is divisible by an LM(fi).

1) Set g := g, r := 0.

2) If g = 0 we stop.

3) Write xγ = LM(g), c = LC(g). If there is an fi such that LM(fi) divides xγ then we set

g := g − c

LC(fi)xβfi

where xβLM(fi) = xγ. Otherwise we set

g := g − cxγ and r := r + cxγ .

Return to 2).

Proposition 1.1.12 The algorithm 1.1.11 terminates correctly.

Proof. In every round of the algorithm LM(g) decreases. Hence the algorithm terminatesas there are no infinite descending chains.

Not that throughout the execution of the algorithm we have g − (g + r) ∈ I, whereI = 〈f1, . . . , fs〉. Indeed, this is surely true initially (when g = g, r = 0). Assume it holds forg and r. If they get replaced by g1, r1, with

g1 = g − c

LC(fi)xβfi and r1 = r,

theng − (g1 + r1) = g − (g + r) +

c

LC(fi)xβfi

so also g − (g1 + r1) ∈ I. If on the other hand g1 = g1 − cxγ and r1 = r + cxγ then

g − (g1 + r1) = g − (g + r) ∈ I.

So the property continues to hold in the next round of the algorithm. (The property g− (g+r) ∈ I is said to be a loop-invariant of the algorithm.)

So upon termination we have g = 0 and g − r ∈ I and therefore

g − r = h1f1 + . . .+ hsfs.

By construction we see that no LM(fi) divides a monomial in r. �

6 Grobner Bases

Remark 1.1.13 We note that the algorithm, and hence its output, depends strongly on thechosen monomial order. In the next example we see that there is another element of choicein the algorithm that can also affect the output.

Example 1.1.14 Let f1 = xy + 1, f2 = y + 1 e g = xy − y. We use the monomial order<=<glex.

We can perform the algorithm in two ways:

• First alternative:

1) g = xy − y, r = 0;

2) g = g − f1 = −y − 1;

3) g = g + f2 = 0;

4) r = 0.

• Second alternative:

1) g = xy − y, r = 0;

2) g = g − xf2 = −x− y;

3) g = g + x = −y, r = −x;4) g = g + f2 = 1;

5) g = g − 1 = 0, r = −x+ 1;

6) r = −x+ 1.

Remark 1.1.15 Let G ⊂ k[x1, . . . , xn] be a set of polynomials, and f ∈ k[x1, . . . , xn]. Letg ∈ G, and xα a monomial of f such that LM(g) divides xα. Let xβ be such that xα =xβLM(g), and set f = f − c

LC(g)xβg, where c is the coefficient of xα in f . Then we say that f

reduces to f modulo G, and we write fg→ f . Division with remainder can also be described

as a maximal sequence of reduction steps. The second alternative of the previous examplebecomes

gf2→ −x− y

f2→ −x+ 1.

Definition 1.1.16 Let r be the output of Algorithm 1.1.11 with input f1, . . . , fs ∈ R, andg ∈ R. Then r is called a remainder of g modulo f1, . . . , fs.

So from this example we see that there can be more than one remainder of g modulof1, . . . , fs. So the main problem is not solved as easily as in the univariate case. The mainidea is to find a different generating set G = {g1, . . . , gt} of the ideal I = 〈f1, . . . , fs〉, withthe property that the remainder of a g ∈ R modulo G is unique, and moreover it is zero ifand only if g ∈ I. Such a G will be called a Grobner basis.

First we study what happens in a relatively easy case.

1.1 Grobner bases 7

1.1.5 Monomial ideals

Definition 1.1.17 Let A ⊆ Nn (possibly infinite). Then the ideal

I = 〈xα | α ∈ A〉 ⊂ R = k[x1, . . . , xn]

is called a monomial ideal.

Lemma 1.1.18 Let I = 〈xα | α ∈ A〉 be a monomial ideal. Then h ∈ I if and only if all ofits monomials lie in I.

Proof. “⇐”. Obvious.“⇒”. Let h ∈ I and write h =

∑α∈A hαx

α with hα ∈ R, only finitely many of which arenonzero.

Let xγ be a monomial of h. So xγ is a monomial of at least one hαxα. But

hα =

m∑

i=1

µixβ(i) =⇒ hαx

α =

m∑

i=1

µixβ(i)+α.

So there is an i withxγ = xβ(i)xα ∈ I.

�

Lemma 1.1.19 Let the notation be as in the preceding lemma. We have xγ ∈ I if and onlyif xγ = xβxα for certain β ∈ Nn and α ∈ A.

Proof. Analogous to the proof of Lemma 1.1.18. �

Now we define a partial order � on Nn by α � β if αi ≤ βi for all i.

Example 1.1.20 We have (1, 2, 3) � (1, 3, 5). Furthermore, (1, 2, 3) � (1, 3, 2) and (1, 3, 2) �(1, 2, 3).

Hence not all elements are comparable with the order �. We say that α, β ∈ Nn withα � β and β � α are uncomparable with respect to �.

A set A ⊆ Nn of which any pair of elements is uncomparable is called an antichain.

Lemma 1.1.21 Every antichain in Nn is finite.

Proof. For n = 1 this is obvious as in that case � is equal to the normal order ≤ on theintegers. (So an antichain has at most one element.)

Let n > 1 be minimal such that there is an infinite antichain A ⊆ Nn. Let α ∈ A. Thenfor all β ∈ A with β 6= α there exists i with βi < αi (and j with βj > αj), because α and βare not comparable. Then

Ar {α} =

n⋃

i=1

{β ∈ A | βi < αi}.

So since A is infinite, at least one set Bi0 = {β ∈ A | βi0 < αi0} is infinite. Write δ = αi0 .

8 Grobner Bases

Then Bi0 = ∪δ−1j=0{β ∈ A | βi0 = j}.

So at least one of these sets is infinite; let it be C = {β ∈ A | βi0 = j0}. Set

C ′ = {(β1, . . . , βi0−1, βi0+1, . . . , βn) | β = (β1, . . . , βn) ∈ C}.

But then also C ′ is an antichain and |C ′| = |C| = ∞.As C ′ ⊆ Nn−1 we have reached a contradiction. �

Lemma 1.1.22 (Dickson) Let A ⊆ Nn e I = 〈xα | α ∈ A〉 ⊂ R = k[x1, . . . , xn]. Then thereexists an A′ ⊂ A, with A′ finite and I = 〈xα | α ∈ A′〉.

In other words, a monomial ideal is always generated by a finite number of monomials.Proof. Let B ⊆ A a maximal antichain (that means that there is no antichain B′ ⊆ A withB′ ⊇ B and B′ 6= B). By Lemma 1.1.21 B is finite.

Observe that for all α ∈ Nn the set {β ∈ Nn | β � α} is finite.Set A′ = B ∪ ⋃α∈B{β ∈ A | β � α}. We claim that I = 〈xα | α ∈ A′〉. The inclusion

“(⊇)” is obvious because A′ ⊆ A. In order to show “(⊆)” let β ∈ A. We have to show thatthere is a γ ∈ Nn and α ∈ A′ with xβ = xγxα.

If β ∈ B ⊆ A′ then there is nothing to show. Otherwise β 6∈ B and hence there is anα ∈ B such that α and β are comparable (otherwise B ∪ {β} is a bigger antichain). So thereare two possibilities: α � β or β � α.

If α � β then we take γ = β − α and hence xβ = xγxα. If β � α then β ∈ A′ so we cantake γ = (0, . . . , 0) and α = β. �

Theorem 1.1.23 Let ≤ be an order on Nn with

1) ≤ is total,

2) if α ≤ β then α+ γ ≤ β + γ for all γ ∈ Nn,

3) α ≥ γ0 = (0, . . . , 0) for all α ∈ Nn.

Then ≤ is a monomial order.

Proof. We must show that there are no infinite descending chains. So suppose that we haveα(1) ≥ α(2) ≥ . . ..

Let A = {α(i) | i ≥ 1} and I = 〈xα | α ∈ A〉. By Dickson’s lemma we have that thereexists a finite A′ ⊂ A, with I = 〈xα | α ∈ A′〉.

Write A′ = {β(1), . . . , β(r)} with β(1) > β(2) > . . . > β(r). We claim that α(i) ≥ β(r)for all i.

Indeed, xα(i) ∈ I so by Lemma 1.1.19 there exists a β(j) e γ ∈ Nn with xα(i) = xγxβ(j),that is, α(i) = γ + β(j).

By 3) we know that γ ≥ γ0 = (0, . . . , 0) hence

α(i) = γ + β(j) ≥ γ0 + β(j) = β(j) ≥ β(r).

Let m be such that α(m) = β(r). Since α(m) ≥ α(m+ 1) ≥ . . . ≥ β(r) and α(m) = β(r)it follows α(m) = α(m+ 1) = . . .. So the chain cannot be infinite. �

1.1 Grobner bases 9

Theorem 1.1.24 (Hilbert’s basis theorem) Every ideal of R = k[x1, . . . , xn] is generatedby a finite number of elements.

Proof. Let I ⊂ R be an ideal and J = 〈LM(f) | f ∈ I〉 the ideal generated by the leadingmonomials of the elements of I (with respect to a fixed monomial order).

Dickson’s lemma implies that there exist g1, . . . , gs ∈ I with

J = 〈LM(gi) | 1 ≤ i ≤ s〉.

These generate I. Indeed, let f ∈ I, then using polynomial division with remainder wefind r ∈ R such that there are h1, . . . , hs ∈ R with f = h1g1+ . . .+hsgs+ r and no monomialof r is divisible by an LM(gi).

But r = f −∑higi ∈ I hence LM(r) lies in J . So there exists i such that LM(gi) dividesLM(r) (Lemma 1.1.19) but this is impossible except when r = 0. It follows that f =

∑higi. �

Corollary 1.1.25 If Ik, for k ≥ 1, are ideals of R with I1 ⊆ I2 ⊆ I3 ⊆ . . . then there existsm with Im = Im+1 = Im+2 = . . ..

Proof. Let J = ∪k≥1Ik which is an ideal of R. Theorem 1.1.24 says that there areg1, . . . , gs ∈ J with J = 〈g1, . . . , gs〉. Let ki be such that gi ∈ Iki and set m = max(k1, . . . , ks).Then g1, . . . , gs ∈ Im and hence Im+i = Im because Im ⊆ Im+i is given and Im+i ⊆ J = Im. �

1.1.6 Grobner bases

Definition 1.1.26 Let I ⊂ R = k[x1, . . . , xn] be an ideal. Then the ideal 〈LM(f) | f ∈ I〉 iscalled the initial ideal of I. We write 〈LM(I)〉 = 〈LM(f) | f ∈ I〉.

Definition 1.1.27 Let I ⊂ R = k[x1, . . . , xn] be an ideal, and G ⊂ I with 〈LM(I)〉 =〈LM(g) | g ∈ G〉. Then G is called a Grobner basis of I.

Remark 1.1.28

• G = I is a Grobner basis of I.

• From Dickson’s lemma (see also the proof of Hilbert’s basis theorem) we immediatelyget that every ideal has a finite Grobner basis.

Lemma 1.1.29 Let I ⊆ k[x1, . . . , xn] be an ideal. Then G ⊂ I is a Grobner basis of I if andonly if for all f ∈ I there is a g ∈ G such that LM(g) divides LM(f).

Proof. We have that G is a Grobner basis of I if and only if

〈LM(g) | g ∈ G〉 = 〈LM(I)〉

so if and only if for all f ∈ I there exists g ∈ G such that LM(g) divides LM(f) (Lemma1.1.19). �

10 Grobner Bases

Proposition 1.1.30 Let I ⊂ R = k[x1, . . . , xn] be an ideal and G ⊂ I a Grobner basis. Letf ∈ R and r ∈ R a remainder of f modulo G. Then r is uniquely determined, that is, it doesnot depend on the choices made during the division algorithm. Moreover, r = 0 if and only iff ∈ I.

Proof. Suppose that

f = h1gi1 + . . .+ hsgis + r1 = h1gj1 + . . .+ htgjt + r2

with gik and gjk in G and ri ∈ R with the property that none of their monomials are divisibleby an LM(g) with g ∈ G.

Then

r1 − r2 = h1gi1 + . . .+ hsgis +−h1gj1 − . . .− htgjt ∈ Iso by Lemma 1.1.29 there exists g ∈ G such that LM(g) divides LM(r1−r2). But LM(r1−r2)is a monomial of r1 or of r2 (or of both). Hence r1 − r2 = 0 so that r1 = r2.

If f ∈ I then r1 ∈ I (because r1 = f −∑su=1 hugiu). So there exists g ∈ G such that

LM(g) divides LM(r1) (Lemma 1.1.29) whence r1 = 0. The other direction is trivial. �

1.1.7 Computing Grobner bases

As before we write R = k[x1, . . . , xn] and we fix a monomial order ≤. Let G ⊂ R.

Let r ∈ R be a remainder of f ∈ R modulo G. Then we write r = fG.

If fG = 0 then we say that f reduces to 0 modulo G.

Let f1, f2 ∈ Rr{0} and write xα(i) = LM(fi). Let γ be defined by γj = max(α(1)j , α(2)j).Then xγ is called the least common multiple of xα(1) and xα(2).

Furthermore,

S(f1, f2) =xγ

LC(f1)LM(f1)f1 −

xγ

LC(f2)LM(f2)f2

is called the S-polynomial of f1 and f2.

Example 1.1.31 Let f1 = 2xyz2−xy and f2 = 3x2y2z−5xyz. We use the order <glex. Theleast common multiple of the leading monomials of f1 and f2 is xγ = x2y2z2 and

S(f1, f2) =xy

2(2xyz2 − xy)− z

3(3x2y2z − 5xyz) = −1

2x2y2 +

5

3xyz2,

hence LM(S(f1, f2)) = x2y2.

We see that there is a remainder of S(f1, f2) modulo {f1, f2} which is not zero becausex2y2 is not divisible by LM(f1) or by LM(f2).

In particular, we see that {f1, f2} is not a Grobner basis of the ideal generated by it.

An element of the form cxα with c ∈ k is called a term.

Lemma 1.1.32 Let G ⊂ R = k[x1, . . . , xn] and f ∈ R. Then if f reduces to zero modulo Gwe have f = h1g1 + . . .+hsgs with gi ∈ G (not necessarily distinct) and where the hi ∈ R areterms with

LM(f) = LM(h1g1) > LM(h2g2) > . . . > LM(hsgs).

1.1 Grobner bases 11

Proof. This follows from the division algorithm. �

The next theorem gives us a criterion with which we can decide whether a given set G ⊂ Ris a Grobner basis (of the ideal it generates) or not.

Theorem 1.1.33 (Buchberger’s criterion) Let I ⊂ R be an ideal generated by a set G ⊂I. Then G is a Grobner basis of I if and only if S(g1, g2)

G= 0 for all g1, g2 ∈ G.

Proof.

“⇒” If G is a Grobner basis, then since S(g1, g2) ∈ I, this reduces to zero modulo G(Proposition 1.1.30).

“⇐” Let f ∈ I; we show that there exists a g ∈ G such that LM(g) divides LM(f). Thenwith Lemma 1.1.29 we conclude that G is a Grobner basis of I.

We can write f = h1g1 + . . . + hsgs where the hi ∈ R are terms and gi ∈ G. Writemi = LM(higi) and m = m1. After reordering, we may assume that

m = m1 = m2 = . . . = mv > mv+1 ≥ . . . ≥ ms.

Let us also assume that LC(gi) = 1 (if LC(gi) is not 1 then the same proof will go through,but the notation becomes a bit heavier).

Choose an expression of the form f = h1g1 + . . .+ hsgs with m minimal, and among theset of those expressions with v minimal.

Suppose that v > 1 and write hi = cixα(i). Then

f = c1xα(1)g1 + . . .+ csx

α(s)gs

= c1(xα(1)g1 − xα(2)g2) + (c1 + c2)x

α(2)g2 + . . .+ csxα(s)gs.

Now let xγ be the least common multiple of LM(g1) and LM(g2) and write xδ = m =LM(xα(1)g1) = LM(xα(2)g2). Then

xα(1)g1 − xα(2)g2 =xδ

LM(g1)g1 −

xδ

LM(g2)g2

because xδ = xα(i)LM(gi).Hence

xα(1)g1 − xα(2)g2 = xδ−γ

(xγ

LM(g1)g1 −

xγ

LM(g2)g2

)= xδ−γS(g1, g2).

But S(g1, g2) reduces to zero modulo G. Hence by Lemma 1.1.32

S(g1, g2) = u1gi1 + . . .+ utgit

where ui is a term and

xγ > LM(S(g1, g2)) = LM(u1gi1) > LM(u2gi2) > . . . > LM(utgit).

Therefore

xα(1)g1 − xα(2)g2 =

t∑

j=1

xδ−γujgij

12 Grobner Bases

and LM(xδ−γujgij ) < xδ = m. So since

f = c1(xα(1)g1 − xα(2)g2) + (c1 + c2)x

α(2)g2 + . . .+ csxα(s)gs

after subsituting we obtain an expression of the form f = h1g1 + . . .+ hsgs with v decreased,or in case v = 2 and c1 + c2 = 0, with m decreased. But this is impossible, hence v = 1.

It follows that m = LM(xα(1)g1) = LM(f) and hence LM(g1) divides LM(f). �

Algorithm 1.1.34Given: {g1, . . . , gs} generating the ideal I ⊂ k[x1, . . . , xn] and a fixed monomial order ≤.

We compute: a Grobner basis of I with respect to ≤.

1. Set G0 := {g1, . . . , gs}, and i := 0.

2. If S(f, g)Gi

= 0 for all f, g ∈ Gi then Gi is a Grobner basis and we stop.

3. If there are f, g ∈ Gi with r := S(f, g)Gi 6= 0 then we set Gi+1 := Gi ∪ {r}, i := i + 1,

and return to 2.

Proposition 1.1.35 Then algorithm 1.1.34 terminates correctly.

Proof.

When the algorithm terminates Gi is a Grobner basis of I because- it generates I as it contains g1, . . . , gs and Gi ⊂ I,- by Theorem 1.1.33 Gi is a Grobner of the ideal it generates.Now to termination. Consider the ideals Ji = 〈LM(g) | g ∈ Gi〉. We claim that Gi+1 ) Gi

implies that Ji+1 ) Ji. Indeed, Gi+1 = Gi ∪ {r} and LM(r) is not divisible by any LM(g) forg ∈ Gi. Hence LM(r) 6∈ Ji (Lemma 1.1.19). But LM(r) ∈ Ji+1 so Ji+1 ) Ji.

By Corollary 1.1.25 there are no infinite increasing chains of ideals in R. Hence the algo-rithm must terminate. �

Example 1.1.36 Let g1 = xyz − xy and g2 = x2y − yz. We use the order <glex withx >glex y >glex z.

We have G0 = {g1, g2} and

S(g1, g2) = xg1 − zg2

= x2yz − x2y − (x2yz − yz2)

= −x2y + yz2

g2→ yz2 − yz

= g3.

So G1 = {g1, g2, g3}. Next

S(g1, g3) = zg1 − xg3

= xyz2 − xyz − (xyz2 − xyz)

= 0


and

S(g2, g3) = z2g2 − x2g3

= x2yz2 − yz3 − (x2yz2 − x2yz)

= x2yz − yz3

g1→ −yz3 + x2yg3→ x2y − yz2

g2→ −yz2 + yzg3→ 0.

Hence G1 = {g1, g2, g3} is a Grobner basis of I.

When computing a Grobner basis one can use a number of tricks that often make lifeeasier. First of all, one can divide every element by a constant in order to make the leadingcoefficient equal to 1. A second trick is based on the following results.

Lemma 1.1.37 Let f, g ∈ k[x1, . . . , xn] and assume that the least common multiple of LM(f)and LM(g) is the product LM(f)LM(g) (so the greatest common divisor of LM(f) and LM(g)is 1). Let u, v ∈ k[x1, . . . , xn] be such that LM(u) < LM(f), LM(v) < LM(g). Then ug + vfreduces to 0 modulo {f, g}.Proof. The leading monomial of ug + vf occurs in ug or in vf but not in both. Indeed,if LM(ug) = LM(vf) then LM(u)LM(g) = LM(v)LM(f). So since LM(g) and LM(f) haveno common factors it follows that LM(g) divides LM(v). But LM(v) < LM(g) so this is notpossible.

It follows that LM(ug) 6= LM(vf) so the biggest of the two is LM(ug + vf).Suppose that LM(ug + vf) = LM(ug). Hence LM(ug + vf) is divisible by LM(g) with

factor LM(u). So in the division algorithm ug + vf is replaced by

ug + vf − cLM(u)g = (u− cLM(u))g + vf

where c ∈ k.We see that we have obtained an expression of the same form. So the division algorithm

proceeds until it obtains zero. �

Lemma 1.1.38 Let f, g ∈ k[x1, . . . , xn] such that LM(f) and LM(g) have no common factors.Then S(f, g) reduces to 0 modulo {f, g}.Proof. Write f = c1x

α + r1 and g = c2xβ + r2, with x

α = LM(f) and xβ = LM(g). Thenthe least common multiple of xα and xβ is xα+β. It follows that

S(f, g) =xα+β

c1xα(c1x

α + r1)−xα+β

c2xβ(c2x

β + r2)

=1

c1r1x

β − 1

c2r2x

α

=1

c1c2r1(g − r2)−

1

c1c2r2(f − r1)

=1

c1c2(r1g − r2f)

14 Grobner Bases

and LM(r1) < LM(f), LM(r2) < LM(g). By Lemma 1.1.37, r1g− r2f reduces to zero modulo{f, g}. �

Conclusion. When calculating a Grobner basis we don’t need to check S(f, g) if LM(f)and LM(g) don’t have common factors.

Example 1.1.39 One problem with Grobner bases is that on many occasions they are diffi-cult to compute because they can be very big. As an example consider

f1 = x3 + y + z2 − 1, f2 = x2 + y3 + z − 1, f3 = x+ y2 + z3 − 1.

A Grobner basis of the ideal generated by these polynomials with respect to <lex is:

x + y + 7467678205870943/65719095621171465*z^25 +

1906548593713883/4381273041411431*z^24 +

8191728039103700/13143819124234293*z^23 -

18118488190106417/65719095621171465*z^22 -

40197573291173158/13143819124234293*z^21 -

60670103256071060/13143819124234293*z^20 -

152406006738162748/65719095621171465*z^19 +

80624458839890252/13143819124234293*z^18 +

649226374687018607/65719095621171465*z^17 +

618150565337585002/65719095621171465*z^16 +

353034549878420633/65719095621171465*z^15 +

238802559571273606/65719095621171465*z^14 -

11655150926515255/4381273041411431*z^13 -

1972928184800696599/65719095621171465*z^12 -

775940019593808291/21906365207057155*z^11 -

1345970642704934506/65719095621171465*z^10 +

2087861421527788238/65719095621171465*z^9 +

3117371817891097726/65719095621171465*z^8 +

374132655781594758/21906365207057155*z^7 -

437890362723893518/65719095621171465*z^6 -

60670429063906802/1991487746096105*z^5 -

42413702095534382/65719095621171465*z^4 -

28132496530919371/21906365207057155*z^3 +

702615426148730872/65719095621171465*z^2 -

80217895633896968/21906365207057155*z - 1,

y^2 - y - 7467678205870943/65719095621171465*z^25 -

1906548593713883/4381273041411431*z^24 -

8191728039103700/13143819124234293*z^23 +

18118488190106417/65719095621171465*z^22 +

40197573291173158/13143819124234293*z^21 +

60670103256071060/13143819124234293*z^20 +

152406006738162748/65719095621171465*z^19 -

80624458839890252/13143819124234293*z^18 -

649226374687018607/65719095621171465*z^17 -


618150565337585002/65719095621171465*z^16 -

353034549878420633/65719095621171465*z^15 -

238802559571273606/65719095621171465*z^14 +

11655150926515255/4381273041411431*z^13 +

1972928184800696599/65719095621171465*z^12 +

775940019593808291/21906365207057155*z^11 +

1345970642704934506/65719095621171465*z^10 -

2087861421527788238/65719095621171465*z^9 -

3117371817891097726/65719095621171465*z^8 -

374132655781594758/21906365207057155*z^7 +

437890362723893518/65719095621171465*z^6 +

60670429063906802/1991487746096105*z^5 +

42413702095534382/65719095621171465*z^4 +

50038861737976526/21906365207057155*z^3 -

702615426148730872/65719095621171465*z^2 +

80217895633896968/21906365207057155*z,

y*z + 114351761873236539/148963283407988654*z^25 +

209291487801391117/446889850223965962*z^24 +

52236360062652115/148963283407988654*z^23 -

1468425502479577274/223444925111982981*z^22 -

858875628508250933/223444925111982981*z^21 -

616034236519743323/223444925111982981*z^20 +

8794492882346418295/446889850223965962*z^19 +

4815691490104347169/446889850223965962*z^18 +

1149199885582915487/446889850223965962*z^17 -

1088785538668067356/223444925111982981*z^16 -

2515633540839994712/223444925111982981*z^15 +

6870511665918010699/446889850223965962*z^14 -

33317003410103522629/446889850223965962*z^13 -

1138745048309366852/74481641703994327*z^12 -

2405659933320304387/223444925111982981*z^11 +

16532107971394002975/148963283407988654*z^10 +

38492638078382481727/446889850223965962*z^9 -

17305956248039834578/223444925111982981*z^8 -

3042243532386622694/223444925111982981*z^7 -

8470564338716612201/74481641703994327*z^6 +

109793303496803963/1194892647657663*z^5 -

1834169915554595837/74481641703994327*z^4 +

23672654350351476275/446889850223965962*z^3 -

2965819909779524184/74481641703994327*z^2 +

3212763377507509769/446889850223965962*z,

z^26 - 9*z^23 + 29*z^20 - 6*z^18 - 11*z^17 - 14*z^16 + 27*z^15 - 110*z^14 +

37*z^13 + 4*z^12 + 163*z^11 + 36*z^10 - 173*z^9 + 28*z^8 - 146*z^7 +

208*z^6 - 94*z^5 + 89*z^4 - 91*z^3 + 37*z^2 - 5*z

16 Grobner Bases

1.2 Applications of Grobner bases

In this second section we see a few applications of Grobner bases. Of course, they solve themain problem: given an ideal I ⊂ k[x1, . . . , xn] and f ∈ k[x1, . . . , xn] decide if f ∈ I. In orderto solve this problem we compute a Grobner basis G of I. Then f ∈ I if and only if fG = 0.

1.2.1 Solving polynomial equations

Definition 1.2.1 A field k is called algebraically closed if every polynomial in k[x] has azero in k.

Example 1.2.2 For example k = C.

The problem of this section is, given f1, . . . , fs in k[x1, . . . , kn], to decide if there is a vector(a1, . . . , an) ∈ kn with

f1(a1, . . . , an) = . . . = fs(a1, . . . , an) = 0

and in the affirmative case to find such (a1, . . . , an).If the field is algebraically closed the first part of the problem can be solved with Hilbert’s

Nullstellensatz.

Theorem 1.2.3 (Hilbert’s Nullstellensatz) Let k be an algebraically closed field and R =k[x1, . . . , xn]. Let f1, . . . , fs ∈ R. Then there exists a = (a1, . . . , an) ∈ kn with f1(a) = . . . =fs(a) = 0 if and only if the ideal I = 〈f1, . . . , fs〉 does not contain 1.

Here we give a recent proof of this famous theorem, due to Lev Glebsky (“A proof ofHilbert’s Nullstellensatz based on Groebner bases”, preprint, 2012). This proof uses Grobnerbases. First we show a few lemmas. For these we do not assume that k is necessarilyalgebraically closed, unless otherwise stated.

Lemma 1.2.4 Let I, J be ideals of R. Let t be an extra indeterminate. Consider the ideal Mof k[t, x1, . . . , xn] generated by all tf and (1− t)g for f ∈ I and g ∈ J . Then I ∩ J =M ∩R.

Proof. First of all, note that M consists of elements of the form h1tf + h2(1 − t)g forh1, h2 ∈ k[t, x1, . . . , xn].

Let h ∈ M ∩ R. Then h is independent of t, so substituting a value a ∈ k for t leavesh unchanged. But also h ∈ M so h = h1tf + h2(1 − t)g with f ∈ I, g ∈ J , h1, h2 ∈k[t, x1, . . . , xn]. Now setting t = 1 shows h = h1(0, x1, . . . , xn)f ∈ I and setting t = 0 provesh = h2(0, x1, . . . , xn)g ∈ J .

Conversely, let h ∈ I ∩ J . Then h = th+ (1− t)h ∈M . So h ∈M ∩R. �

Later we will see how this lemma leads to an algorithm for computing generators of theintersection of two ideals.

In the next lemma we consider polynomials in x1. If f ∈ k[x1] is such a polynomial, andI ⊂ R an ideal then we write

〈f〉+ I = {hf + g | h ∈ R, g ∈ I}

which is an ideal of R.

1.2 Applications of Grobner bases 17

Lemma 1.2.5 Let I ⊂ R be an ideal. Let f1, f2 ∈ k[x1] be such that gcd(f1, f2) = 1. SetIi = 〈fi〉+ I. Then I1 ∩ I2 = 〈f1f2〉+ I.

Proof. Let g1, . . . , gs ∈ R be such that I = 〈g1, . . . , gs〉. Then Ii = 〈fi, g1, . . . , gs〉. Let tbe an extra indeterminate. Let J be the ideal generated by tf1, (1 − t)f2, tgi, (1 − t)gi for1 ≤ i ≤ s. So J is also generated by tf1, (1− t)f2, g1, . . . , gs.

Now let h1, h2 ∈ k[x1] be such that h1f1 + h2f2 = 1. Then J is also generated by f1f2,h2f2 − t, g1, . . . , gs. Indeed let J ′ be the ideal generated by the latter polynomials. Sincetf1 = f1f2h2 − (h2f2 − t)f1 and (1 − t)f2 = f1f2h1 + (h2f2 − t)f2 we get J ⊂ J ′. But alsoJ ′ ⊂ J as f1f2 = (tf1)f2 + ((1 − t)f2)f1 and h2f2 − t = ((1− t)f2)h2 − tf1h1.

We claim that J ∩ R = 〈f1f2, g1, . . . , gs〉. The inclusion ⊃ is obvious. For the other one,let g ∈ J ∩R, then g = af1f2+ b(h2f2− t)+

∑i cigi for certain a, b, ci ∈ k[t, x1, . . . , xn]. Since

g ∈ R, the subsitution t 7→ h2f2 leaves g unchanged. But it also maps g to af1f2 +∑

i cigi(where a, ci is the image of a, ci under the subsitution). It follows that we also have ⊂.

Now Lemma 1.2.4 finishes the proof. �

Let a1, . . . , ak ∈ k. Then we define the ring homomorphism eva1,...,ak : R→ k[xk+1, . . . , xn]by eva1,...,ak(f) = f(a1, . . . , ak, xk+1, . . . , xn).

Lemma 1.2.6 Assume that k is algebraically closed. Let I ⊂ R be a proper ideal (i.e.,I 6= R). Then there is a ∈ k such that eva(I) is a proper ideal of k[x2, . . . , xn].

Proof. Set J = I ∩ k[x1]. This is an ideal of k[x1]. It cannot be all of k[x1] as otherwise1 ∈ I and I = R. We distinguish two cases. In the first case J 6= 0, so that J = 〈p〉 for somep ∈ k[x1] (Lemma 1.1.6). Write p = (x1−a1)m1 · · · (x1−ar)mr , where the ai ∈ k are pairwisedistinct. Now using Lemma 1.2.5 we get

I = 〈p〉+ I =

r⋂

i=1

(〈(x1 − ai)mi〉+ I).

So there is an i such that 〈(x1 − ai)mi〉 + I 6= R. Denote this ideal by Ji and write M =

〈x1 − ai〉+ I. Now

〈(x1 − ai)mi〉+ I ⊂M ⊂

√Ji.

(For the definition of√Ji see Definition 1.2.12). But also

√Ji 6= R, whence M 6= R. But M

has a generating set consisting of x1 − ai, g1, . . . , gs, with gi ∈ k[x2, . . . , xn]. It follows that1 6∈ evai(M), and therefore 1 6∈ evai(I) (as I ⊂M).

In the second case J = 0. Now we consider the rational function field k(x1) and thepolynomial ring S = k(x1)[x2, . . . , xn]. Then R can be viewed as a subset of S. Let I ′ be theideal of S generated by I. Then J = 0 implies that I ′ 6= S, i.e., I ′ is a proper ideal. Let G′ bea Grobner basis of I ′, consisting of monic elements. The coefficients of the elements of G′ liein k(x1), so are of the form p/q with p, q ∈ k[x1]. Let h be the product of all denominatorsthat occur in the coefficients of the elements of G′. Since k is infinite, there is a ∈ k withh(a) 6= 0. This means that eva(g) is a well defined element of k[x2, . . . , xn] for all g ∈ G′. Wehave that eva(G

′) is a Grobner basis of the ideal M of k[x2, . . . , xn] generated by it. (Indeed,let f =

∑i hieva(gi) ∈ M with hi ∈ k[x2, . . . , xn]; we must show that there is a g′ ∈ G′

such that LM(g′) divides LM(f). Consider f =∑

i higi ∈ I ′, and note that eva(f) = f . IfLM(f) = LM(f) then we are done. Otherwise eva(LC(f)) = 0. On the other hand, there

18 Grobner Bases

is a g ∈ G′ such that LM(g) divides LM(f). We now replace f by f = f − cxαg, wherec ∈ k(x1) is such that c(a) = 0. Also eva(f) = f , but LM(f) < LM(f). Continuing like thiswe eventually find an f ∈ I ′ such that eva(f) = f and LM(f) = LM(f).)

However, eva(G′) does not contain any constants, as J = 0. Therefore M 6= k[x2, . . . , xn].

So since eva(I) ⊂M , also eva(I) 6= k[x2, . . . , xn]. �

Proof.(of the Nullstellensatz). The proof is by induction on n, the case n = 1 being clear. Ifn > 1 then by Lemma 1.2.6 we get that there is an a1 ∈ k such that eva1(I) is a proper idealof k[x2, . . . , xn]. Hence by induction there are a2, . . . , an ∈ k such that f(a1, a2, . . . , an) = 0for all f ∈ I. �

The work of David Hilbert (1862 - 1943)

is of great importance for the development and use of Grobner bases. However, interest-ingly, his methods were not algorithmical at all. His proof of what is now known as Hilbert’sbasis theorem shows that every ideal has a finite number of generators, without giving a clueas to what these generators are, or how many are needed. This prompted Gordan, famously,to exclaim “Das ist nicht Mathematik. Das ist Theologie.” (This is not mathematics. Thisis theology.)

Using the Nullstellensatz we can decide whether or not a given set of polynomial equationshas a solution in an algebraically closed field. Indeed, we compute a Grobner basis G of theideal generated by the polynomials. Then 1 lies in the ideal if and only if 1G = 0.

Now we turn to the problem of actually determining a solution, if one exists. The followinglemma is trivial, but nonetheless important.

Lemma 1.2.7 Let I be the ideal generated by f1, . . . , fs ∈ k[x1, . . . , xn], and let a = (a1, . . . , an) ∈kn. Then f1(a) = . . . = fs(a) = 0 if and only if f(a) = 0 for all f ∈ I.

Proof. Note that f ∈ I if and only if there exist h1, . . . , hs ∈ R with f = h1f1+ · · ·+hsfs. �

From this lemma we see that solving the polynomial equations f1 = . . . = fs = 0 isequivalent to solving the equations g1 = . . . = gt = 0, where {g1, . . . , gt} is any generatingset of the ideal generated by the fi. Next we see that Grobner bases with respect to thelexicographical order are particularly useful in this respect.

Definition 1.2.8 Let I ⊂ k[x1, . . . , xn] be an ideal and 0 ≤ l ≤ n−1. Then I∩k[xl+1, . . . , xn],which is an ideal of k[xl+1, . . . , xn], is called the l-th elimination ideal of I.

The l-th elimination ideal eliminates the first l indeterminates.


Theorem 1.2.9 (Elimination theorem) Set R = k[x1, . . . , xn], and use the order <lex

with x1 >lex x2 >lex . . . >lex xn. Let I ⊂ R be an ideal and G a Grobner basis of I withrespect to <lex. Then G ∩ k[xl+1, . . . , xn] is a Grobner basis of I ∩ k[xl+1, . . . , xn].

Proof. Set Gl = G ∩ k[xl+1, . . . , xn] and Il = I ∩ k[xl+1, . . . , xn].

We need to show that 〈LM(Il)〉 = 〈LM(g) | g ∈ Gl〉.“⊃” Obvious as Gl ⊂ Il.

“⊂” Let f ∈ Il. Then f ∈ I and since G is a Grobner basis of I, there exists g ∈ G suchthat LM(g) divides LM(f). But f ∈ k[xl+1, . . . , xn] so also LM(g) ∈ k[xl+1, . . . , xn].

Now let xα be a monomial of g, xα 6= LM(g). If αi > 0 for some i ≤ l then xα >lex LM(g).But that is impossible.

Hence xα ∈ k[xl+1, . . . , xn] and therefore g ∈ k[xl+1, . . . , xn]. It follows that g ∈ Gl whenceLM(f) ∈ 〈LM(g) | g ∈ Gl〉. �

Conclusion. With a Grobner basis with respect to <lex we immediately find Grobner basesfor

I ∩ k[xn]

I ∩ k[xn−1, xn]

...

I ∩ k[x2, . . . , xn]

I ∩ k[x1, . . . , xn] = I.

So the Grobner basis has a triangular structure that may help to solve the correspondingpolynomial equations.

Note: it is possible that I ∩ k[xl+1, . . . , xn] = 0.

Example 1.2.10 Consider the polynomials

f1 = x2 + y + z − 1, f2 = x+ y2 + z − 1, f3 = x+ y + z2 − 1.

We want to solve the system f1 = f2 = f3 = 0.

A Grobner basis with respect to >lex consists of the polynomials

g1 = x+ y + z2 − 1

g2 = y2 − y − z2 + z

g3 = 2yz2 + z4 − z2

g4 = z6 − 4z4 + 4z3 − z2 = z2(z − 1)2(z2 + 2z − 1).

With I = 〈f1, f2, f3〉 we see that I∩k[z] is generated by g4, I∩k[y, z] is generated by g2, g3, g4.

Also we see that g4 = 0 gives a finite number of values of z, namely 0, 1 and −1±√2. If

z = 0 then also g3 = 0, but g2 = 0 implies that y can be 0 or 1. If y = z = 0, then from g1 = 0it follows that x = 1. We find the solution (1, 0, 0). Going on like this we find all solutions:

20 Grobner Bases

(1, 0, 0)

(0, 1, 0)

(0, 0, 1)

(−1−√2,−1−

√2,−1−

√2)

(−1 +√2,−1 +

√2,−1 +

√2).

Example 1.2.11 Theorem 1.2.9 and Lemma 1.2.4 give an algorithm for computing gener-ators of the intersection of two ideals I = 〈f1, . . . , fr〉, J = 〈g1, . . . , gs〉. Indeed, let t be anextra indeterminate, and

M = 〈tf1, . . . , tfr, (1− t)g1, . . . , (1− t)gs〉,

which is an ideal of k[t, x1, . . . , xn]. Let G be a Grobner basis of M with respect to a lexico-graphical ordering, such that t >lex xi for all i. Then G ∩ k[x1, . . . , xn] is a Grobner basis ofI ∩ J .

1.2.2 Applications of Grobner bases in geometry

Definition 1.2.12 Let I ⊂ k[x1, . . . , xn] be an ideal. Then√I = {f ∈ k[x1, . . . , xn] | there is m > 0 with fm ∈ I}

is called the radical of I.

Remark 1.2.13√I is an ideal of k[x1, . . . , xn].

Proof. Obviously 0 ∈√I. Let f ∈

√I and g ∈ k[x1, . . . , xn], so f

m ∈ I for a certain m > 0.Hence gmfm = (gf)m ∈ I so that gf ∈

√I.

If f, g ∈√I then we let m > 0 be such that fm, gm ∈ I. Then

(f + g)2m =2m∑

i=0

(2m

i

)f ig2m−i ∈ I

so f + g ∈√I. �

Lemma 1.2.14 Let I = 〈f1, . . . , fs〉 ⊂ k[x1, . . . , xn] be an ideal and f ∈ k[x1, . . . , xn]. Thenf ∈

√I if and only if 1 is contained in the ideal J = 〈f1, . . . , fs, 1− yf〉 ⊂ k[x1, . . . , xn, y].

Proof. “⇒” Suppose that fm ∈ I. Then ymfm ∈ J (because I ⊂ J). But also

(1− ymfm) = (1− yf)(1 + yf + (yf)2 + . . .+ (yf)m−1) ∈ J

so 1 ∈ J .“⇐” If 1 ∈ J then there exist pi, q ∈ k[x1, . . . , xn, y] with

1 =

s∑

i=1

pi(x1, . . . , xn, y)fi + q(x1, . . . , xn, y)(1 − yf).


Now we formally subsitite 1f for y and get

1 =

s∑

i=1

pi(x1, . . . , xn,1

f)fi.

Note that the pi(x1, . . . , xn,1f ) are rational expressions with denominators f r for certain

r ≥ 0.Hence there is an m with fmpi(x1, . . . , xn,

1f ) ∈ k[x1, . . . , xn] and therefore

fm =s∑

i=1

fmpi(x1, . . . , xn,1

f)fi

so fm ∈ I, in other words f ∈√I. �

So with Grobner bases one can check whether f ∈√I or not. This leads to the following

algorithm.

Algorithm 1.2.15Given: f1, . . . , fs generating the ideal I ⊂ k[x1, . . . , xn], and an f ∈ k[x1, . . . , xn].We decide f ∈

√I or not.

1. Compute a Grobner basis G of J = 〈f1, . . . , fs, 1− yf〉;

2. If 1G = 0 then f ∈√I, otherwise f 6∈

√I.

Definition 1.2.16 Let W = kn be a vector space over k of dimension n. Let I = 〈f1, . . . , fs〉be an ideal of k[x1, . . . , xn]. Then the set

V (I) = {(w1, . . . , wn) ∈W | f(w1, . . . , wn) = 0 for all f ∈ I}

is called the closed set corresponding to I.

Example 1.2.17 Let k = R. Let I ⊂ k[x, y] be generated by y − x2. Then V (I) consists ofthe points of the graph

V

22 Grobner Bases

Similarly, if I = 〈x2 + y2 − 1〉, then V (I) consists of the points of

V (I)

Theorem 1.2.18 (Hilbert’s Nullstellensatz, strong form) Let k be an algebraically closedfield and I ⊂ k[x1, . . . , xn] an ideal. Let J ⊂ k[x1, . . . , xn] be the ideal defined by

J = {f ∈ k[x1, . . . , xn] | f(w) = 0, ∀w ∈ V (I)}.

Then J =√I.

Proof. If f ∈√I then there exists m > 0 with fm ∈ I and hence fm(w) = 0 for all

w ∈ V (I). But fm(w) = (f(w))m so f(w) = 0 for all w ∈ V (I). Therefore f ∈ J .Now take f ∈ J , that is, f(w) = 0 for all w ∈ V (I). Let I be generated by f1, . . . , fs ∈

k[x1, . . . , xn]. Set I = 〈f1, . . . , fs, 1− yf〉 ⊂ k[x1, . . . , xn, y]. Let w = (w1, . . . , wn, wn+1) ∈kn+1. We consider two cases:

- (w1, . . . , wn) ∈ V (I). Then fi(w) = 0 for i = 1, . . . , s. But f(w) = 0 so (1− yf)(w) 6= 0.

- (w1, . . . , wn) 6∈ V (I). Then there is fi with fi(w) 6= 0.

The conclusion is that {w = (w1, . . . , wn+1) | h(w) = 0, ∀h ∈ I} = ∅. By the weak form ofHilbert’s Nullstellensatz (Theorem 1.2.3), 1 ∈ I (k is algebraically closed). Hence by Lemma1.2.14, f ∈

√I. �

Remark 1.2.19 One hasV (I) ∩ V (J) = V (I + J)

where I + J is the idealI + J = {f + g | f ∈ I, g ∈ J}.

Proof. Let v ∈ V (I) ∩ V (J) and h = f + g ∈ I + J with f ∈ I and g ∈ J . Then

h(v) = f(v) + g(v) = 0 + 0 = 0

so v ∈ V (I + J).Conversely, let v ∈ V (I + J). Since I ⊂ I + J we get h(v) = 0 for all h ∈ I, whence

v ∈ V (I). Analogously we get v ∈ V (J). Therefore v ∈ V (I) ∩ V (J). �

From this it follows that for X ⊂ kn there exists a unique minimal closed set containingX. This is called the closure of X. Now let

Id(X) = {f ∈ k[x1, . . . , xn] | f(v) = 0, ∀v ∈ X}


which is an ideal of k[x1, . . . , xn]. Then the closure of X is V (Id(X)). (Indeed, let J be suchthat the closure of X is V (J). Let f ∈ J , then f(v) = 0 for all v ∈ X, whence f ∈ Id(X).So J ⊂ Id(X) implying V (Id(X)) ⊂ V (J). But V (Id(X)) is a closed set containing X, so wealso get the reverse inclusion.)

Theorem 1.2.20 Let k be an algebraically closed field, and R = k[x1, . . . , xn], and I =〈f1, . . . , fs〉 ⊂ R. Let πl : k

n → kn−l be defined by πl(v1, . . . , vn) = (vl+1, . . . , vn).

Let Il = k[xl+1, . . . , xn] ∩ I, the l-th elimination ideal of I. Then V (Il) is the closure ofπl(V (I)).

Example 1.2.21 Let I = 〈xy − 1〉 ⊂ k[x, y]. Consider π1 : k2 → k with π1(v1, v2) = v2.

Then

V (I) = {(v1, v2) | v1v2 = 1} =⇒ π1(V (I)) = k r {0}.

Now I1 = 0 which implies V (I1) = k.

Proof.(of Theorem 1.2.20) Let J = Id(πl(V (I)) ⊂ k[xl+1, . . . , xn]. Then we claim thatJ =

√Il. In order to see “⊃”, let f ∈ √

Il. Then fm ∈ Il ⊂ I, for some m > 0. So, forv ∈ V (I) we have fm(v) = 0, and consequently f(v) = 0. It follows that f ∈ J .

For the reverse inclusion let f ∈ J . Then f(vl+1, . . . , vn) = 0 for all (v1, . . . , vn) ∈ V (I).It follows that f(v) = 0 for all v ∈ V (I) and hence, by Hilbert’s Nullstellensatz (Theorem1.2.18), f ∈

√I. In other words, fm ∈ I. But f ∈ k[xl+1, . . . , xn] so f

m also lives there.Therefore fm ∈ I ∩ k[xl+1, . . . , xn] = Il.

We conclude that V (J) = V (√Il). But the latter is equal to V (Il). �

Conclusion. In view of the elimination theorem, using Grobner bases we can find theclosure of πl(U), where U ⊂ kn is a closed set.

As an application we show how to find the closure of the image of a regular function.

A regular function h : kn → km is given by m polynomials h1, . . . , hm ∈ k[x1, . . . , xn], suchthat h(v) = (h1(v), . . . , hm(v)).

Let X = V (I) ⊂ kn where I = 〈f1, . . . , fs〉 ⊂ k[x1, . . . , xn]. We want to find the closureof h(X).

Let

Γ = {(v, h(v)) | v ∈ X} ⊂ kn+m.

This is called the graph of h.

Observe that Γ ⊂ kn+m is closed. Indeed, let J be the ideal of k[x1, . . . , xn, y1, . . . , ym]generated by

{f1, . . . , fs, y1 − h1, . . . , ym − hm}.

Then (v,w) ∈ Γ if and only if p(v,w) = 0 for all p ∈ J (w = h(v) if and only if (yi−hi)(v,w) =wi − hi(v) = 0).

By computing a Grobner basis we can compute the closure of πn(Γ) where πn : kn+m → km

is defined by

πn(v1, . . . , vn, w1, . . . , wm) = (w1, . . . , wm).

Now πn(Γ) = h(X) so we see that we can compute the closure of h(X) (here we alwaysassume the field k to be algebraically closed).

24 Grobner Bases

Example 1.2.22 Let S = {(t2, t3) | t ∈ C}. We compute the closure of S. Define h : C → C2

by h(t) = (t2, t3). Then S = {h(t) | t ∈ C}. Consider the graph of h:

Γ = {(u, h(u)) | u ∈ C}.

We have that Γ = V (I) where I = 〈y1 − t2, y2 − t3〉 ⊂ k[t, y1, y2].We compute a Grobner basis of I with respect to <lex with t >lex y1 >lex y2, and obtain

G = {t2 − y1, ty1 − y2, ty2 − y21, y31 − y22}.

So by the elimination theorem, a Grobner basis of I ∩ k[y1, y2] is G ∩ k[y1, y2] = {y31 − y22}.The conclusion is that the closure of S is V (J) where J is generated by y31 − y22.

Here we have V (J) = S, but this is not true in general.The set S is the parametric form of a curve in C2, whereas the representation as V (J) is

called the implicit form of the curve. It is not true in general that the parametric form andthe implicit form define exactly the same set of points.

Divertimento: the real Nullstellensatz

In general the Nullstellensatz does not hold when the field is not algebraically closed. How-ever, for the field is R there is an interesting variant of the theorem. It is called the realNullstellensatz, (see G. Stengle. A Nullstellensatz and a Positivestellensatz in semi-algebraicgeometry, Math.Ann.(1974),pp. 87-97).

For this let I be an ideal of R = R[x1, . . . , xn]. Then its real radical is defined as

R√I = {f ∈ R | f2m +

∑

i

r2i ∈ I for some m > 0, ri ∈ R}.

With this definition the real Nullstellensatz holds: let J be as in the strong form of theNullstellensatz, then

J =R√I.

Example: I = 〈x21 + x22〉; then it is not difficult to see that

R√I = 〈x1, x2〉.

1.2.3 An application in combinatorics: Alon’s non-vanishing theorem

Here we let k be a field. Let T1, . . . , Tn be finite subsets of k, and write ti = |Ti|. Then weform the set of points T = T1 × T2 × · · · × Tn ⊂ kn. We set

I(T ) = {f ∈ k[x1, . . . , xn] | f(p) = 0 for all p ∈ T}.

It is straightforward to see that T is an ideal of k[x1, . . . , xn]. For 1 ≤ i ≤ n set

fi =∏

s∈Ti

(xi − s).

These are elements of k[xi], and obviously lie in I(T ).

Lemma 1.2.23 {f1, . . . , fn} is a Grobner basis of I(T ) (with respect to any monomial or-dering).


Proof. The leading monomial of fi is xtii . Pairwise they have no common factors; therefore

the fi form a Grobner basis of the ideal they generate.

We need to show that the fi generate I(T ). For that we use induction on n. For n = 1 itis obvious, so suppose n > 1.

Let f ∈ I(T ) and write f = g0 + g1xn + · · · + grxrn, with gi ∈ k[x1, . . . , xn−1]. Suppose

that f 6∈ 〈f1, . . . , fn〉, and choose f with this property such that r is minimal.

First suppose that gi(u1, . . . , un−1) = 0 for all i and (u1, . . . , un−1) ∈ T1×· · ·×Tn−1. Thenby induction the gi lie in the ideal 〈f1, . . . , fn−1〉 ⊂ k[x1, . . . , xn−1]. Hence f ∈ 〈f1, . . . , fn−1〉 ⊂k[x1, . . . , xn]. So we obtain a contradiction.

Now assume that there is a (u1, . . . , un−1) ∈ T1 × · · · × Tn−1 with gj(u1, . . . , un−1) 6= 0 for

a certain j. Set f = f(u1, . . . , un−1, xn). Then f is not the zero polynomial. But it vanisheson Tn. Hence it is a multiple of fn. In particular, r ≥ tn. Now set f = f − grx

r−tnn fn.

Then f ∈ I(T ), but f = h0 + · · · + hr−1xr−1n , with hi ∈ k[x1, . . . , xn]. So again we obtain a

contradiction.

The conclusion is that I(T ) = 〈f1, . . . , fn〉. �

Theorem 1.2.24 (Alon’s non-vanishing theorem) Let p ∈ k[x1, . . . , xn] be of degree

n∑

i=1

(ti − 1).

Suppose that the coefficient of xt1−11 · · · xtn−1

n in p is nonzero. Then there is u = (u1, . . . , un) ∈T with p(u) 6= 0.

Proof. We use a degree compatible term ordering, i.e., if |α| < |β| then xα < xβ.

Suppose that p vanishes on all elements of T . Then p ∈ I(T ). So by the previous lemmawe can write

p = ui1fi1 + · · ·+ uimfim

where the uik are terms, and

LM(p) = LM(ui1fi1) > LM(ui2fi2) > · · · > LM(uimfim).

In particular this means that the degree of every LM(ui1fi1) is at most∑n

i=1(ti − 1).

Note that deg(fi) = ti. Suppose that the monomial xt1−11 · · · xtn−1

n occurs in a uikfik .Then the degree of uikfik has to exceed

∑ni=1(ti − 1), which is excluded. It follows that

xt1−11 · · · xtn−1

n occurs in no uikfik , which is a contradiction. �

Next we give an application in combinatorics of Alon’s non-vanishing theorem.

Let p be a prime and A,B ⊂ Fp. Then we define

A+B = {a+ b | a ∈ A, b ∈ B}.

Theorem 1.2.25 (Cauchy-Davenport) Let A,B be non-empty subsets of Fp. Then

|A+B| ≥ min(p, |A| + |B| − 1).

26 Grobner Bases

Proof. First assume that |A| + |B| ≤ p + 1. Suppose that there exists a set C ⊂ Fp with|C| = |A|+ |B| − 2, and A+B ⊂ C. (In other words, suppose that |A+B| < |A|+ |B| − 1).Put

f =∏

c∈C(x+ y − c) ∈ Fp[x, y].

Set T1 = A and T2 = B. Then f vanishes on T = T1×T2. Also deg(f) = |C| = t1−1+ t2−1.Furthermore, the coefficient of xt1−1yt2−1 is

(t1 − 1 + t2 − 1

t1 − 1

).

But this is nonzero in Fp as t1 − 1 + t2 − 1 = |A|+ |B| − 2 ≤ p− 1 < p. So we have obtaineda contradiction with Alon’s theorem.

If |A| + |B| > p + 1, then we take subsets A′ ⊂ A, B′ ⊂ B such that |A′|+ |B′| = p + 1.Then

|A+B| ≥ |A′ +B′| ≥ p.

(So |A+B| = p.) �

1.2.4 An application in cryptography: Polly-cracker

Here we briefly describe a cryptosystem based on the fact that it is difficult in general tocompute Grobner bases.

Alice wants to receive secret messages from Bob. To this end, Alice chooses a finite fieldFq (for example F2) and works in R = Fq[x1, . . . , xn]

Alice chooses a y ∈ Fnq and some polynomials f1, . . . , fs ∈ R with fi(y) = 0. The

public key is f1, . . . , fs and the secret key is y.In order to send a message Bob first encodes it as anm ∈ Fq, and then chooses polynomials

h1, . . . , hs ∈ R. Finally he sends the polynomial f = m+∑hifi to Alice.

Alice can read the message, because f(y) = m+∑hifi(y) = m.

With Grobner bases one can break the system. If G is a Grobner basis of 〈f1, . . . , fs〉 thenfG = m.

So Alice needs to choose the polynomials fi in such a way that a Grobner basis of theideal 〈f1, . . . , fs〉 is very hard to compute.

A strategy to choose the fi is the following: One takes a problem that is known to bevery hard to solve (a so-called NP-complete problem, for example), and one reformulates aparticularly difficult instance of that problem in terms of polynomial equations. Then onecan realistically hope that a Grobner basis is hard to compute.

For example, we can consider the 3-colouring problem from graph theory. A graph is givenas Γ = (V,E) (V : vertices, E: edges). A 3-colouring is a function ϕ : V → {1, 2, 3} with theproperty that if (v,w) ∈ E then ϕ(v) 6= ϕ(w). For example:

1

2 3

2

3

1


Now finding a 3-colouring is in general a very difficult problem (it is NP-complete).

Now we take F2 as the base field, and the indeterminates tv,i for v ∈ V and i ∈ {1, 2, 3}.Let B = B1 ∪B2 ∪B3 where

B1 = {tv,1 + tv,2 + tv,3 − 1 | v ∈ V }B2 = {tv,itv,j | v ∈ V, 1 ≤ i < j ≤ 3}B3 = {tu,itv,i | (u, v) ∈ E, 1 ≤ i ≤ 3}.

Set tv,i = 1 if the vertex v has colour i, and tv,i = 0 otherwise. This defines a zero ofall polynomials in B. Conversely, if we have a zero of all elements of B, then we can find a3-colouring. Indeed, from the vanishing of the elements of B1∪B2 we find the colour of everyvertex; and the vanishing of the elements of B3 expresses that two adjacent vertices cannothave the same colour.

Experiments show that it is difficult to break the Polly Cracker system with Grobnerbases. However, there are other methods to try and do that, that make the system insecure.For example, observe that if f = m+

∑i hifi is the message, then

m = f(0)−∑

i

hi(0)fi(0).

So it is enough to know the constant terms of the hi in order to reconstruct the message.Sometimes it is possible to get the constant terms by studying how it is possible to obtainthe polynomial f from the fi.

1.2.5 Solving Sudoku

A Sudoku is a puzzle in which one has to place the numbers 1, . . . , 9 in an 9×9 grid accordingto certain rules. To go into detail, consider a 9 × 9-grid consisting of 81 empty boxes. Thisgrid is itself divided into nine 3 × 3-blocks. Some of the boxes already have a number filledin. Then one has to complete the grid according to the following rule:

• In each row and in each column and in each 3 × 3-block each number 1, . . . , 9 has toappear exactly once.

The sudoku is said to be well-posed if there is exactly one solution. The key observation isthat a sudoku is an instance of a graph colouring problem. There are diverse methods to codesuch a problem into polynomial equations. Here we follow the exposition in a recent bookof Decker and Pfister (A First Course in Computational Algebraic Geometry, CambridgeUniversity Press 2013).

28 Grobner Bases

3 5 9 8

2

7 1 3 4

3 4 8 2

1 5 9 7

2 8 7 3

5 6 3 2

1

9 6 7 5

In order to get polynomials from a sudoku we first number the boxes from 1 to 81. Wework in the polynomial ring R = Q[x1, . . . , x81]. The value in each box of a completed sudokuis a zero of the polynomial Fi(xi) =

∏9k=1(xi − k). The polynomial Fi(xi) − Fj(xj) vanishes

on V (xi − xj), and therefore is divisible by xi − xj. So we get the polynomials

Gij =Fi − Fj

xi − xj.

Now we let E be the set of all pairs (i, j) such that i < j, and box i and box j are in thesame row, column, or 3 × 3-block. So (i, j) ∈ E if box i and box j cannot have the samecolour. (E is the set of edges in the corresponding graph colouring problem.) Now we let Ibe the ideal of R generated by all Fi, 1 ≤ i ≤ 81, and Gij for (i, j) ∈ E (in total these are891 polynomials).

Lemma 1.2.26 Let a = (a1, . . . , a81) ∈ C81. Then a ∈ V (I) if and only if ai ∈ {1, . . . , 9},and ai 6= aj for (i, j) ∈ E.

Proof. If ai ∈ {1, . . . , 9} for all i then Fi(a) = 0 for all i. But then also 0 = Fi(a)−Fj(a) =(ai − aj)Gij(a). So if ai 6= aj then Gij(a) = 0.

Conversely, suppose a ∈ V (I). Then Fi(a) = 0 so that ai ∈ {1, . . . , 9}. Suppose that thereis an (i, j) ∈ E with ai = aj = b. Note that Fi = (xi − xj)Gij + Fj . In this we substitute bfor xj , and get Fi(xi) = (xi − b)Gij(xi, b). But since Gij vanishes on a, we have Gij(b, b) = 0,and b is a zero of Fi with multiplicity at least 2. But that is impossible. �

Let S be a sudoku. Let A ⊂ {1, . . . , 81} be such that for i ∈ A the i-th box has thealready filled in value ai. Let IS be the ideal of R generated by I along with xi−ai for i ∈ A.

1.3 Exercises 29

Lemma 1.2.27 Suppose that S is well-posed, and let a = (a1, . . . , a81) be its unique solution.Let G be a Grobner basis of IS (with respect to any monomial ordering). Then xGi = ai.

Proof. Set

J = 〈x1 − a1, . . . , xn − an〉.Then f(a) = 0 for all f ∈ J . Conversely, suppose that f(a) = 0. Perform division withremainder, and get hi ∈ R with f = h1(x1 − a1) + · · ·+ h81(x81 − a81) + r, and no monomialin r is divisible by the leading monomial of a xi − ai. But LM(xi − ai) = xi, and therefore ris constant. Evaluating in a we see that r = 0. The conclusion is that J is precisely the idealof all f ∈ R with f(a) = 0.

Because of Lemma 1.2.26, V (IS) = {a}. So by Hilbert’s Nullstellensatz (Theorem 1.2.18),√IS = 〈x1 − a1, . . . , x81 − a81〉. So for each i, IS contains (xi − ai)

mi , for some mi. But italso contains the greatest common divisor of the univariate polynomials Fi and (xi − ai)

mi ,which is xi − ai. (Note that the greatest common divisor of two univariate polynomials p, q

can be written as ap+ bq, for some polynomials a, b.) So IS =√IS = J . Hence xi − ai

G = 0,whence xGi = ai. �

Of course, this is a very bad method for solving a sudoku! The polynomials correspondingto the sudoku above were tried in Magma; after more than seven hours on a 3.16 GHzprocessor, the system got out of memory (it needed more than 32GB).

1.3 Exercises

1. Consider the order <rlex defined by xα <rlex xβ if αk < βk where k is maximal with

αk 6= βk. Prove that <rlex is a monomial order.

2. We use <glex (graded lexicographical). Let f1 = y2 − z, f2 = z3 − y, f2 = z2 − 1, andg = xy2z2 + xy − yz. Find all possible remainders of g modulo f1, f2, f3.

3. Compute S(f, g) for f = 4x2z − 7y2, g = xyz2 + 3xz4, and f = x4y − z2, g = 3xz2 − y,using the order <lex.

4. Let g1 = x− z2, g2 = y− z3 ∈ k[x, y, z]. Prove that G = {g1, g2} is a Grobner basis withrespect to <lex. Prove that it is not a Grobner basis with respect to <glex. Compute aGrobner basis of the ideal generated by G with respect to <glex.

5. Let g1 = x2y − 1, g2 = xy2 − x. Compute a Grobner basis of the ideal I ⊂ k[x, y]generated by g1, g2, with respect to <glex.

6. Let I ⊂ k[x, y, z] be the ideal generated by g1 = x2yz − yz − x, g2 = xy2z − xy − y,g3 = xyz2 − xy − z. We use the order <glex.

(a) Compute g4 = S(g1, g2) (reduced modulo g1, g2, g3), and g5 = S(g1, g3) (reducedmodulo g1, . . . , g4).

(b) Compute S(g2, g5), reduced modulo g1, . . . , g5.

(c) Prove that I is also generated by h1 = x2z2−z2−x, h2 = xz3−xz−z, h3 = y−z.(d) Compute h4 = S(h1, h2), h5 = S(h1, h4), h6 = S(h2, h5).

30 Grobner Bases

(e) Prove that I is also generated by h2, h3, h5, h6. Show that they form a Grobnerbasis of I.

(f) Find u1, u2, u3 ∈ k[x, y, z] with y − z = u1g1 + u2g2 + u3g3

7. Let g1 = x2+2y2−3, g2 = xy− y2+3 in C[x, y]. Let I be the ideal generated by g1, g2.

(a) Find a Grobner basis of I with respect to <lex.

(b) Find a Grobner basis of I ∩ C[y].

(c) Find all solutions of the equations g1 = g2 = 0.

8. Let g1 = x2+y2+z2−4, g2 = x2+2y2−5, g3 = xz−1 in C[x, y, z]. Let I = 〈g1, g2, g3〉.

(a) We use the monomial order <lex. Compute g4 = S(g1, g2) (reduced modulog1, g2, g3), and g5 = S(g1, g3) (reduced modulo g1, . . . , g4), and g6 = S(g3, g5)(reduced modulo g1, . . . , g5).

(b) Prove that g4, g5, g6 generate I, and that they form a Grobner basis of I.

(c) Compute a Grobner basis of I ∩ C[y, z] and of I ∩ C[z].

(d) Find all solutions of g1 = g2 = g3 = 0.

9. Let I ⊂ C[x, y, z] be the ideal generated by g1 = x2yz − yz − x, g2 = xy2z − xy − y,g3 = xyz2 − xy − z. Let f1 = x− z4 + z2, f2 = y − z, f3 = z7 − 2z5 + z3 − z.

(a) Prove that I = 〈f1, f2, f3〉 (hint: use the result of exercise 6).

(b) Show that {f1, f2, f3} is a Grobner basis of I with respect to the order <lex (withx >lex y >lex z).

(c) Prove that f3 is square free (one can compute gcd(f3, f′3)).

(d) How many points a = (a1, a2, a3) ∈ C3 are there with f1(a) = f2(a) = f3(a) = 0?

10. A monomial order < is said to be an l-elimination order if a monomial having at leastone of x1, . . . , xl with positive exponent is bigger than every monomial in k[xl+1, . . . , xn].

(a) Let <l be the order defined by xα <l xβ if α1 + · · · + αl < β1 + · · · + βl or, if

these are equal, if α <glex β. Show that <l is a monomial order and that it is anl-elimination order.

(b) Let < be an l-elimination order, and let G be a Grobner basis of the ideal I ⊂k[x1, . . . , xn], with respect to <l. Prove that G∩ k[xl+1, . . . , xn] is a Grobner basisof I ∩ k[xl+1, . . . , xn].

11. Let f1, . . . , fr ∈ k[x1, . . . , xn]. Let J ⊂ k[t1, . . . , tr] the ideal consisting of all g ∈k[t1, . . . , tr] with g(f1, . . . , fr) = 0 (in other words, J is the ideal of all polynomialrelations among the fi). We want to compute generators of J .

(a) Let I ⊂ k[x1, . . . , xn, t1, . . . , tr] the ideal generated by t1 − f1, . . . , tr − fr. Provethat

J = I ∩ k[t1, . . . , tr](hint for one inclusion: use the monomial order <lex with ti >lex xj for all i, j; leth ∈ k[t1, . . . , tr] and perform division with remainder to write h =

∑gi(ti−fi)+p;

show that p ∈ k[x1, . . . , xn], and in fact p = h(f1, . . . , fr)).

1.3 Exercises 31

(b) Describe an algorithm for finding generators of J .

(c) Let r = 2, n = 1, x1 = x and f1 = x2, f2 = x3. Find generators of J .

12. Let I = 〈x2, y2〉 ⊂ k[x, y]. Prove that x+ y ∈√I, by computing a Grobner basis.

13. (Rational parametrisation.) Let

C = {(

2t

t2 + 1,1− t2

t2 + 1

)| t ∈ C, t2 6= −1}.

Let f1 = (t2 + 1)y1 − 2t, f2 = (t2 + 1)y2 − 1 + t2 ∈ C[t, y1, y2], and set

Γ = {(s, u1, u2) ∈ C3 | f1(s, u1, u2) = f2(s, u1, u2) = 0}.

(a) Let π1 : C3 → C2 be defined by π1(s, u1, u2) = (u1, u2). Prove that π1(Γ) = C.

(b) Use the order <lex, with t >lex y1 >lex y2. Compute S(f1, f2) (reduced modulof1, f2) and obtain f3. In the same way compute S(f2, f3) to obtain f4 and S(f3, f4)to obtain f5.

(c) Prove that {f3, f4, f5} is a Grobner basis of the ideal generated by f1, f2, withrespect to <lex.

(d) Find an ideal J ⊂ C[y1, y2] such that V (J) is the closure of C.

14. ConsiderS = {(uv, uv2, u2) ∈ C3 | u, v ∈ C}.

A Grobner basis of 〈uv − x, uv2 − y, u2 − z〉, with respect to the order <lex with u >lex

v >lex x >lex y >lex z is

{u2 − z, uv − x, ux− vz, uy − x2, v2z − x2, vx− y, vyz − x3, x4 − y2z}.

Find an ideal I ⊂ C[x, y, z] such that the closure of S is V (I). Find points on V (I) thatdo not lie in S. (So V (I) is strictly bigger than S.)

32 Grobner Bases

Chapter 2

Integer Factorisation

There are three types of algorithms that have to do with the problem of factorising an integerinto its prime factors:

1) primality testing (probabilistic): such a test proves that n is not prime, or that n is primewith high probability (such tests are typically fast),

2) algorithms for proving that a given number n, which tests have shown to be probablyprime, in fact is prime,

3) algorithms for factorising n, knowing that n is not prime.

The first algorithm that comes to mind, to solve all problems, is to divide n by all integersup to

√n. For large n this becomes impossibly slow. However, it can be used to eliminate

small factors (≤ 105 for example).

In this chapter we treat some other methods for these three problems. In the first sectionwe describe the Miller-Rabin test, which is one of the most efficient primality tests. Thesecond section has several methods for the last problem, i.e., we have an integer n and weknow that it is not prime. The problem is to factorise it. The main algorithms that wedescribe are CFRAC (based on continued fractions) and ECM (the elliptic curve method).Finally in the last section we briefly touch upon a method for proving that a given number,which has a high probability of being prime, in fact is prime. This method uses elliptic curves,and is often denoted by the acronym ECPP (elliptic curve primality proving).

2.1 The Miller-Rabin primality test

The Miller-Rabin primality test was invented by Gary Miller

34 Integer Factorisation

who in 1976 gave a deterministic version of the test (whose correctness depends on theGeneralised Riemann Hypothesis), and Michael Rabin

who in the 1980’s developed the probabilistic version of the test, which is still in use today.

Here we describe the test, following the article by Rene Schoof: Four primality testingalgorithms, Algorithmic number theory; MSRI Publications 44, Cambridge University Press,Cambridge 2008, 101–126.

Lemma 2.1.1 Let p be an odd prime and e ≥ 1, x integers. Then x2 = 1 mod pe impliesx = ±1 mod pe.

Proof. From x2 = 1 mod pe we get that pe divides (x+1)(x− 1). But p cannot divide bothfactors as p is odd. Hence pe divides one of them; whence the statement. �

Lemma 2.1.2 Let Cn be the cyclic group of order n, with generator g (so the order of g isn). Let e ≥ 1 and d = gcd(e, n). There are exactly d elements h ∈ Cn with he = 1.

Proof. Write h = gj , where 1 ≤ j ≤ n. Then he = 1 if and only if gej = 1, which isequivalent to n|ej. In turn this is the same as saying n

d | edj. But the latter happens if andonly if n

d |j. So for j we have the possibilities j = nd , 2

nd , . . . , d

nd . �

Theorem 2.1.3 Let n > 9 be an integer that is composite and odd. Write n − 1 = 2km,where k ≥ 1 and m is odd. Set

B = {x ∈ (Z/nZ)∗ | xm = 1 or there is i with 0 ≤ i < k and xm2i = −1}.

Then|B|ϕ(n)

≤ 1

4

(where ϕ(n) = |(Z/nZ)∗|).

Proof. Let l ∈ Z be maximal such that 2l divides p − 1 for all prime factors p of n. SetB′ = {x ∈ (Z/nZ)∗ | xm2l−1

= ±1}. We claim that B ⊂ B′. To see this, let x ∈ B. If

xm = 1 then xm2l−1

= 1. Secondly, suppose that xm2i = −1 for an i with 0 ≤ i < k. By xwe also denote the integer congruent to x mod n, and 1 < x < n. Then xm2i+1

= 1 mod pfor all primes p that divide n. So for all such p, the exact power of 2 that divides the orderof x mod p is 2i+1. So 2i+1|p − 1 (as (Z/pZ)∗ has p − 1 elements). It follows that i < l.

Furthermore, if i = l − 1 then xm2l−1

= −1 and if i < l − 1 then xm2l−1

= 1. The claim isproved.

2.1 The Miller-Rabin primality test 35

Now write n =∏s

i=1 peii , where the pi are distinct (odd) primes. Then by the chinese

remainder theorem we get

(Z/nZ)∗ = (Z/pe11 Z)∗ × · · · × (Z/pess Z)∗.

Now the group (Z/peii Z)∗ is cyclic of order (pi − 1)pei−1

i . So by Lemma 2.1.2 the number

of y ∈ (Z/peii Z)∗ with ym2l−1

= 1 is gcd((pi − 1)pei−1i ,m2l−1) = gcd(pi − 1,m)2l−1 (by the

definition of l we see that 2l−1|pi − 1; furthermore, pi 6 |m). For this reason, the number

of x ∈ (Z/nZ)∗ with xm2l−1

= 1 is∏s

i=1 gcd(pi − 1,m)2l−1. Analogously, the number of

solutions in (Z/peii Z)∗ of the equation Xm2l = 1 is gcd(pi−1,m)2l. This is twice the number

of solutions to the equation Xm2l−1

= 1. So by Lemma 2.1.1, it follows that the number ofsolutions to the equation Xm2l−1

= −1 is the same as the number of solutions to Xm2l−1

= 1.We conclude that

|B′| = 2

s∏

i=1

gcd(pi − 1,m)2l−1.

Now suppose that |B|/ϕ(n) > 14 . Since B ⊂ B′ and ϕ(n) =

∏si=1(pi − 1)pei−1

i we get

1

4< 2

s∏

i=1

gcd(pi − 1,m)2l−1

(pi − 1)pei−1i

. (2.1)

Observe that gcd(pi − 1,m)2l−1 divides pi−12 . From this it follows that the right hand side

of (2.1) is smaller than 21−s∏s

i=11

pei−1

i

. So s ≤ 2. Suppose first that s = 2. Then also

e1 = e2 = 1, so that n = pq, where p, q are distinct primes. Then (2.1) is equivalent to

2 >p− 1

gcd(p − 1,m)2lq − 1

gcd(q − 1,m)2l.

Both factors on the right are positive integers; so both have to be 1. Hence p − 1 = gcd(p−1,m)2l and q − 1 = gcd(q − 1,m)2l. Write p− 1 = ap2

l, q − 1 = aq2l with ap, aq odd. Then

ap, aq divide m. Consider the equation pq = 1 + 2km modulo ap. Since p = 1 mod ap we getap|q − 1. Analogously, aq|p − 1. This implies that ap = aq, which is a contradiction.

It follows that s = 1 and n = pe, e ≥ 2. Then (2.1) is equivalent to

4 >1

2

(p− 1)pe−1

gcd(p− 1,m)2l−1=

p− 1

gcd(p− 1,m)2lpe−1 ≥ pe−1

(as gcd(p− 1,m)2l divides p− 1). So the only possibility is p = 3, e = 2, but that contradictsn > 9. �

Now the main idea of the next algorithm is as follows. If n is prime then B is all of(Z/nZ)∗ (proof: exercise!). Therefore, if a random x ∈ (Z/nZ)∗ does not lie in B, then thatproves that n is not prime. On the other hand, if random elements x continue to lie in B,then probably n is prime, as otherwise the proportion of elements in B is less than a quarter.

Algorithm 2.1.4 Given: n > 9 odd.We return: false (meaning that n certainly is not prime) or fail (meaning that n is likelyto be prime).


1. Take a random integer x with 1 < x < n (uniform distribution).

2. If gcd(x, n) > 1 return false.

3. If xn−1 6= 1 mod n then return false.

4. Write n− 1 = 2km, with m odd. Compute the minimal i ≥ 0 with xm2i = 1 mod n. Ifi > 0 and xm2i−1 6= −1 mod n then return false. Otherwise return fail.

Note that the i in Step 4 exists as xm2k = 1 mod n by Step 3.

Theorem 2.1.5 If the previous algorithm returns false then n is composite. Furthermore,the probability of n being composite and the algorithm returning fail is ≤ 1

4 .

Proof. Suppose that i > 0 and xm2i = 1 mod n. If n is prime, then by Lemma 2.1.1 wesee that xm2i−1

= ±1 mod n. But it cannot be 1 as i is minimal. If it is not −1 either,then we conclude that n cannot be prime. If fail is returned then either xm = 1 mod n orxm2i−1

= −1 mod n, implying that x ∈ B (the set from Theorem 2.1.3). (NB: after Step 2we know that x mod n lies in (Z/nZ)∗.) But the probability of a random element lying in Bis ≤ 1

4 . �

Example 2.1.6 Let n = 1729. This is a Carmichael number, i.e., it is not prime, butxn−1 = 1 mod n for all positive integers x < n, with gcd(x, n) = 1. We have n− 1 = 26 · 27.So we take m = 27. Let x = 3. Then x27 = 664 mod n and x27·2 = 1 mod n. Hence theMiller-Rabin test shows that n is not prime.

2.2 Factorisation

2.2.1 The method of Fermat

Note that we may assume that n is odd. Set

A = {(a, b) | 0 < a ≤ b and n = ab}and

B = {(s, t) | 0 ≤ s < t and n = t2 − s2}.There is a bijection σ : A→ B with σ(a, b) =

(b−a2 , b+a

2

).

Indeed: (b+ a

2

)2

−(b− a

2

)2

= ab = n

andσ−1(s, t) = (t− s, t+ s).

The conclusion is that finding a factorisation n = ab is equivalent to finding s and t withn = t2 − s2. So we have the following algorithm.

Algorithm 2.2.1 Given: n odd and non-prime.We compute: a, b > 1 with n = ab.

2.2 Factorisation 37

1. Set t0 = ⌈√n⌉ = min{k ∈ Z | k ≥ √n}.

2. If t2i − n = s2i is a square then set a = (ti + si), and b = (ti − si). Otherwise setti+1 = ti + 1, and continue.

This algorithm terminates correctly because if n = t2 − s2 with s < t then t2 = n + s2

implies t >√n.

Example 2.2.2 Take n = 39. then

t0 = 7 ⇒ 72 − 39 = 10t1 = 8 ⇒ 82 − 39 = 25 = 52

hence (8 + 5)(8 − 5) = 39.

This algorithm works well if s is small, because in that case t is close to√n and hence only

a few steps are needed, even if the factors themselves are big. So if one wants to construct anumber that is difficult to factor (as in the cryptosystem RSA, for example) then the factorscannot be chosen close to each other.

Pierre de Fermat (1601 - 1665)

was a french lawyer, in mathematics most famous for his work in number theory, althoughhe did not publish most of his results, preferring to mention the problems he had solved toother mathematicians and challenging them to also come up with a solution.

2.2.2 The continued fraction method (CFRAC)

Factor bases

Some more advanced methods use a similar idea to Fermat’s algorithm. But instead of lookingfor s and t with n = t2 − s2, they try to find x and y with

- x2 − y2 = 0 mod n;

- 0 < y < x < n;

- x+ y 6= n.

If we have such x, y then we can factorise n because (x+ y)(x− y) is divisible by n, butx+ y and x− y are not. Hence a = gcd(x+ y, n) and b = gcd(x− y, n) are nontrivial factorsof n (which means a, b 6= 1 and a, b 6= n).


Example 2.2.3 Take n = 377, then

3352 = 256 mod 377 = 162 mod 377

so with x = 335 and y = 16 we get

gcd(335 + 16, n) = 13 and gcd(335 − 16, n) = 29

and n = 13 · 29.

So the idea is to find x with 0 < x < n such that x2 mod n is a square y2. Not all xcan be chosen for this: for example if n = 15 and x = 2, then x2 mod n = 4 but y = 2doesn’t work as y = x. But also x = 13 is not good as x2 mod n = 4 but with y = 2 we getx+ y = n. (Note that in this case x = −2 mod n.) A better try is x = 7 with which we find72 mod n = 4 and

gcd(7 + 2, 15) = 3 and gcd(7− 2, 15) = 5.

Notation. By x mod n we denote the unique integer with −n2 < s ≤ n

2 , congruent tox mod n.

Definition 2.2.4 A set B = {p0 = −1, p1, . . . , pr} with pi prime for i ≥ 1, is called a factorbase.

Definition 2.2.5 An integer k is called a B-number (or B-smooth) if k = pe00 pe11 · · · perr .

In order to find x such that x2 mod n is a square we try the following scheme:

- we choose a factor base;

- we generate a lot of integers bi such that b2i mod n is B-smooth.

The aim is to find a product bi1 · · · bim such that

(bi1 · · · bim)2 mod n = pe00 pe11 · · · perr

with ei even for all i, and hence pe11 · · · perr = y2.

Example 2.2.6 Like in Example 2.2.3 we take n = 377 and B = {−1, 2}. Then

192 = −16 mod n and − 16 = p0p21

972 = −16 mod n and − 16 = p0p21.

Therefore (19 · 97)2 = p20p41 mod n. So we set x = 19 · 97 = 335 mod n, and y = 16. Indeed,

gcd(335 + 16, 377) = 13 and gcd(335 − 16, 377) = 29 are factors of n.

So the idea is to combine the factorisations of several b2i mod n such that a square arises.A famous method for generating bi with good properties for this purpose is based on theclassical theory of continued fractions.


Continued fractions

A continued fraction is an expression of the form

a0 +1

a1 +1

a2 +1

a3 +1

a4

with ai ∈ Z, a0 ≥ 0 and ai ≥ 1 for i ≥ 1.Notation. The expression above is denoted by [a0; a1, a2, a3, a4].More generally we say that a continued fraction is a sequence of the form [a0; a1, . . . , an],

with ai ∈ Z, a0 ≥ 0, ai ≥ 1 for i ≥ 1. This corresponds to a rational number γ, whichis defined as follows. If n = 0 then γ = a0. If n > 0, then let γ′ be the rational numbercorresponding to [a1; a2, . . . , an], and set

γ = a0 +1

γ′.

Let x > 0 in R. We want to find a0, a1, . . . such that the continued fractions [a0; a1, . . . , ak]are good approximations of x; we want them to converge to x when k → ∞ (it is not clearyet that it is always possible to find such ai; we will show that in this section).

The ai, if they exist, must be defined in the following way: Write x = a0 + 1x1

witha0 = ⌊x⌋ = max{n ∈ Z | n ≤ x}.

Set x1 =1

x−a0. Next, write x1 = a1 +

1x2

with a1 = ⌊x1⌋ and hence x2 =1

x1−a1and so on.

More formally, set x0 = x and for i ≥ 0:

ai = ⌊xi⌋,

xi+1 =1

xi − ai.

Example 2.2.7 Let x =√2. Then x0 = x and

a0 = 1 ⇒ x1 =1√2− 1

= 1 +√2

a1 = 2 ⇒ x2 =1√2− 1

= 1 +√2

a2 = 2 ⇒ x3 =1√2− 1

= 1 +√2

continuing like this we find ai = 2 for all i ≥ 1. Now, for example,

[1; 2, 2, 2, 2] = 1 +1

2 +1

2 +1

2 +1

2

=41

29.

We have that 2− (4129 )2 = 1

841 ; so it is a reasonable approximation of√2.


Lemma 2.2.8 For x ∈ Q the algorithm for computing the continued fraction correspondingto x terminates (that is, at a certain point we find xi − ai = 0). The resulting continuedfraction is equal to x.

Proof. Write x = ab and a = q1b+ r1 with 0 ≤ r1 < b. Then

a0 = q1 and x1 =1

ab − q1

=b

r1.

Now write b = q2r1 + r2 with 0 ≤ r2 < r1 and get

a1 = q2 and x2 =r1r2.

So we find a sequence of ri with 0 ≤ ri+1 < ri; therefore the algorithm must terminate.By induction on the number of steps one shows that the continued fraction that is found

this way, is equal to x. �

When the continued fraction for x produces the integers a0, a1, . . ., we writebici

= [a0; a1, . . . , ai]where gcd(bi, ci) = 1. These rational numbers are called the convergents of the continued frac-tion for x.

Example 2.2.9 For x =√2 we get

1 +1

2 + 12

=7

5=b2c2.

Theorem 2.2.10 Let a0, a1, . . ., be the integers that are produced by the algorithm for com-puting the continued fraction for x ∈ R, x > 0. Set

β0 = a0, β1 = a0a1 + 1, βi = aiβi−1 + βi−2,γ0 = 1, γ1 = a1, γi = aiγi−1 + γi−2,

for i ≥ 2. Then

1) βiγi−1 − βi−1γi = (−1)i−1, i ≥ 1;

2) gcd(βi, γi) = 1;

3) bi = βi and ci = γi, where bi, ci ∈ Z≥0 are such that gcd(bi, ci) = 1 and bici

= [a0; a1, . . . , ai].

Proof. 1) We use induction. For i = 1 we have

β1γ0 − β0γ1 = (a0a1 + 1)1− a0a1 = 1 = (−1)0.

For i ≥ 1 we get, using the induction hypothesis

βi+1γi − βiγi+1 = (ai+1βi + βi−1)γi − βi(ai+1γi + γi−1)

= βi−1γi − βiγi−1

= −(−1)i−1

= (−1)i.


2) If p divides γi and βi then by 1) it also divides (−1)i−1, which is impossible for a primep.

3) Also here we use induction on i. For i = 0 we get

b0c0

= a0 =β0γ0

and for i = 1b1c1

= a0 +1

a1=β1γ1.

Note that [a0; a1, . . . , ai, ai+1] is obtained from [a0; a1, . . . , ai] by substituting ai+1

ai+1for

ai. By induction we now have

[a0; a1, . . . , ai] =βiγi

=aiβi−1 + βi−2

aiγi−1 + γi−2

hence

[a0; a1, . . . , ai+1] =

(ai +

1ai+1

)βi−1 + βi−2

(ai +

1ai+1

)γi−1 + γi−2

=ai+1(aiβi−1 + βi−2) + βi−1

ai+1(aiγi−1 + γi−2) + γi−1

=ai+1βi + βi−1

ai+1γi + γi−1

=βi+1

γi+1.

It follows that βi+1 = bi+1 and γi+1 = ci+1 (since gcd(βi+1, γi+1) = 1). �

Remark 2.2.11 It follows that bici−1 − cibi−1 = (−1)i−1. Divide by cici−1 to get

bici

− bi−1

ci−1=

(−1)i−1

cici−1

and hence ∣∣∣∣bici

− bi−1

ci−1

∣∣∣∣ =1

cici−1.

But ci > ci−1 > . . . ≥ 1 so ∣∣∣∣bici

− bi−1

ci−1

∣∣∣∣ −→ 0.

Theorem 2.2.12 The notation is as in Theorem 2.2.10. Then biciconverges to x when i→ ∞.

Proof. For i ≥ 0 we set xi = xi − ai. Then we claim that

x = a0 +1

a1 +1

a2 + . . .1

ai + xi

.


Indeed, for i = 0 we have a0 + x0 = x0 = x. For i > 0 we use induction; by the inductionhypothesis we get

a1 +1

a2 +1

a3 + . . .1

ai + xi

= x1,

which establishes the claim.

Conclusion: x is obtained from [a0; a1, . . . , ai+1] by substituting 1xi

for ai+1. But

[a0; a1, . . . , ai+1] =bi+1

ci+1=ai+1bi + bi−1

ai+1ci + ci−1

hence

x =1xibi + bi−1

1xici + ci−1

=bi + xibi−1

ci + xici−1.

Nowbi+xibi−1

ci+xici−1< bi

ciif and only if xi(bici−1 − bi−1ci) > 0. But by Theorem 2.2.10 that is

the same as (−1)i−1xi > 0, which in turn is equivalent to i being odd. In the same way it is

shown that bi+xibi−1

ci+xici−1< bi−1

ci−1if and only if i is even. It follows that x is always between two

successive convergents.

From Observation 2.2.11 we have that the distance between bici

and bi−1

ci+−

goes to 0. Hencebici

converges to a limit that has to be x (as x is always in the middle). �

Factorisation with continued fractions

Lemma 2.2.13 Let x ∈ R, x > 1. Let bici

be the convergents of the continued fraction for x.Then

|b2i − c2i x2| < 2x.

Proof. By the observation in the proof of Theorem 2.2.12 we have

∣∣∣∣bi+1

ci+1− bici

∣∣∣∣ =1

ci+1ci.

Set δ = 1ci+1ci

.

bi+1

ci+1x bi

ci

δ

Now

|b2i − c2i x2| = |c2i x2 − b2i | = c2i

∣∣∣∣x− bici

∣∣∣∣∣∣∣∣x+

bici

∣∣∣∣ .


And∣∣∣x− bi

ci

∣∣∣ < δ while

∣∣∣∣x+bici

∣∣∣∣ = x+bici

= 2x+bici

− x < 2x+ δ

hence|b2i − c2i x

2| < c2i δ(2x+ δ).

Therefore

|b2i − c2i x2| − 2x < 2x

(−1 + δc2i +

δ2c2i2x

)= 2x

(−1 +

cici+1

+1

2xc2i+1

).

But 12xc2i+1

< 1ci+1

because x > 1 and ci+1 ≥ 1. Moreover, ci + 1 ≤ ci+1 because ci < ci+1.

Hence

|b2i − c2i x2| − 2x < 2x

(−1 +

cici+1

+1

ci+1

)< 2x

(−1 +

ci+1

ci+1

)= 0

and therefore|b2i − c2i x

2| < 2x.

�

Corollary 2.2.14 Let n > 16 be an integer and bici

the convergents of the continued fraction

of√n. Then |b2i mod n| < 2

√n.

Proof. By Lemma 2.2.13 we have |b2i − c2in| < 2√n. But b2i − c2in is an integer congruent

to b2i mod n and contained in the interval (−2√n, 2

√n). Hence it is contained in the interval(

−n2 ,

n2

)(as n > 16). It follows that b2i − c2in is equal to b2i mod n. �

Idea of the factorisation algorithm: Let B = {p0 = −1, p1, . . . , pr} be a factor base. Letbici

be the convergents of the continued fraction of√n.

Then b2i mod n is always “small”. So among the b2i mod n there are often B-smoothnumbers. On the other hand, bi mod n “jumps” through the entire interval [0, n]. So one canreasonably hope to quickly find bi1 , . . . , bit such that (bi1 · · · bit)2 mod n is a square.

Algorithm 2.2.15 Given: n which is not prime.Calculate: two factors of n.

1. Choose a factor base B = {p0 = −1, p1, . . . , pr}.

2. Compute the continued fraction for√n and find a0, a1, a2, . . ..

3. Compute b0 = a0, b1 = a0a1 + 1, bi+1 = ai+1bi + bi−1.

4. For the bi such that b2i mod n is B-smooth we write b2i mod n = pei0

0 · · · peirr until we

find a product (bi1 · · · bit)2 mod n = pe00 · · · perr with ei even for all i. Set x = bi1 · · · bitand y = p

e02

0 · · · per2r .

5. If we are not unlucky, then gcd(n, x+ y) and gcd(n, x− y) are factors of n.


Remark 2.2.16 The algorithm is based on heuristic ideas; it is not guaranteed that it man-ages to factor n. However, we know that n is composite. Hence if we do not find thefactorisation in reasonable time we can try again; for example with a larger factor base.Implementations have shown that the algorithm works well in practice.

Example 2.2.17 (Factorisation of Fermat numbers)The Fermat numbers are Fn = 22

n

+ 1.Fermat thought that these were all prime numbers. In fact, Fn is prime for 0 ≤ n ≤ 4.

However, Euler has shown thatF5 = 641 · 6700417.

In 1880 Landry proved that

F6 = 274177 · 67280421310721.

And in 1970 Morison and Brillhart, using the continued fraction method on an early computer,got

F7 = 59649589127497217 · P22

where P22 is a prime of 22 digits. (On my laptop this factorisation now takes less than amillisecond.)

Remark 2.2.18 In order to compute the continued fraction for√n the following observation

can help. For α ∈ R, α > 0 and m ∈ Z, m > 0, we have⌊αm

⌋=⌊⌊α⌋m

⌋.

Proof. Write α = u + β with u an integer and β ∈ R, 0 ≤ β < 1. Write u = qm + r with0 ≤ r < m. Then ⌊ α

m

⌋=

⌊u

m+β

m

⌋=

⌊q +

r + β

m

⌋= q

because r + β < m and hence r+βm < 1. On the other hand,

⌊⌊α⌋m

⌋=⌊ um

⌋=⌊q +

r

m

⌋= q.

�

Example 2.2.19 We want to factorise n = 33.The continued fraction for

√33:

a0 = 5 x0 = x− a0 =√33− 5

x1 =1√33−5

= 5+√33

8

a1 = 1 x1 = x0 − a1 =−3+

√33

8

x2 =1x1

= 8−3+

√33

= 3+√33

3

a2 = 2 x2 = x1 − a2 =−3+

√33

3

x3 =3+

√33

8

a3 = 1 x3 = x2 − a3 =−5+

√33

8

x4 = 5 +√33

a4 = 10 . . .


The bi:b0 = a0 = 5 b20 mod 33 = −8b1 = a0a1 + 1 = 6 b21 mod 33 = 3b2 = a2b1 + b0 = 17 b22 mod 33 = −8.

Hencex = b0b2 = 5 · 17 = 19 mod 33 and y = 8

so that

gcd(x+ y, n) = gcd(27, 33) = 3 and gcd(x− y, n) = gcd(11, 33) = 11.

Example 2.2.20 Let us factorise n = 197209. Taking the bi modulo n we get

a0 = 444 b0 = 444 b20 mod n = −73 = −1 · 73a1 = 12 b1 = 5329 b21 mod n = 145 = 5 · 29a2 = 6 b2 = 31428 b22 mod n = −37 = −1 · 37a3 = 23 b3 = 159316 b23 mod n = 720 = 24 · 32 · 5a4 = 1 b4 = 191734 b24 mod n = −143 = −11 · 13a5 = 5 b5 = 131941 b25 mod n = 215 = 5 · 43a6 = 3 b6 = 193139 b26 mod n = −656 = −24 · 41a7 = 1 b7 = 127871 b27 mod n = 33 = 3 · 11a8 = 26 b8 = 165232 b28 mod n = −136 = −23 · 17a9 = 6 b9 = 133218 b29 mod n = 405 = 34 · 5

Hence x = b3 · b9 = 126308 mod n and y = 22 · 33 · 5 = 540. Now gcd(x + y, n) = 991 andgcd(x− y, n) = 199.

Divertimento: solving the Pell equation

Let d be a positive square-free integer. The problem is to find integral solutions x, y ∈ Z tothe equation

x2 − dy2 = 1

which is called the Pell equation. Here we show how this can be done using continued fractions.First of all we consider the continued fraction of

√d. We get real numbers x0, x1, . . . and

integers a0, a1, . . . with

x0 =√d, ai = ⌊xi⌋, xi+1 =

1

xi − ai.

Moreover we get the convergents bici.

It is a fact, which we do not prove here, that the continued fraction of√d is periodic.

This means that there is an s > 1 such that xs+1 = x1, which also implies as+1 = a1. Wetake s > 1 to be the smallest such number. This also means that xks+1 = x1 for k = 1, 2, . . ..So since xi = a1 +

1xi+1

we get

xks = aks +1

x1= a1 +

1

x1.

Setting xi = xi − ai we have, as seen in the proof of Theorem 2.2.12

√d = a0 +

1

a1 +1

a2+... 1

ai+xi

.


Now aks + xks = aks +1x1

= aks + x0 − a0 = aks − a0 +√d. Set u = aks − a0, which lies in

Z. Then we see that we get√d from the ks-th convergent bks

cksby substituting aks 7→ u+

√d.

For brevity we write j0 = ks. Then bkscks

= (aj0bj0−1 + bj0−2)/(aj0cj0−1 + cj0−2). Hence

√d =

(u+√d)bj0−1 + bj0−2

(u+√d)cj0−1 + cj0−2

.

Multiplying by the denominator on the right-hand side we get

(ucj0−1 + cj0−2)√d+ dcj0−1 = bj0−1

√d+ ubj0−1 + bj0−2,

yielding ucj0−1 + cj0−2 = bj0−1 and ubj0−1 + bj0−2 = dcj0−1. We multiply the first equationby bj0−1, the second by cj0−1 and subtract. This gives

bj0−1cj0−2 − bj0−2cj0−1 = b2j0−1 − dc2j0−1.

By Theorem 2.2.10, the left-hand side of this equation is (−1)j0 . We conclude:

• if s is even then the (s− 1)-st convergent gives a solution to the Pell equation,

• if s is odd, then the (2s − 1)-st convergent gives a solution to the Pell equation.

Example 2.2.21 Consider d = 14. Then for the continued fraction of√d we get

i ai xi+1 bi ci

0 3√14+35 3 1

1 1√14+22 4 1

2 2√14+25 11 3

3 1√14 + 3 15 4

4 6√14+35 101 27

We see that s = 4, and therefore x = 15, y = 4 give a solution to the Pell equation. Indeed,152 − 14 · 42 = 1.

The Pell equation has a long and interesting history. Apparently it was considered byArchimedes who posed the “cattle problem”, whose solution goes via a Pell equation. It wasalso studied by the indian mathematician Brahmagupta (598 - 670), who was the first to givea method for solving it. Much later Fermat challenged other mathematicians to find a methodto solve the equation. He accompanied his challenge with some particularly difficult cases;therefore it is very plausible that Fermat knew how to solve the equation. The challenge wasmainly taken up by English mathematicians such as Brouncker and Wallis. Wallis publisheda book, also describing a method to solve the Pell equation, which was due to Brouncker.However, when Euler worked on the equation, he confused Brouncker with Pell, and called itthe Pell equation. It is still referred to under his name, althouh Pell never worked on it. Eulercame up with a rudimentary form of the continued fraction method to solve the equation.Later Lagrange proved rigorously that this method is correct.

There are many interesting questions related to the Pell equation. One is how the solution(x, y) grows with d. For example, when d = 139 the smallest solution is x = 77563250,y = 6578829. For more information on this and other problems we refer to the book byMichael Jacobson and Hugh Williams, Solving the Pell equation, Springer Verlag 2009.


2.2.3 The elliptic curve method (ECM)

In 1999, Richard Brent (Factorization of the tenth Fermat number, Math. Comp 225), usingECM (Elliptic Curve Method) has found the factorisation of the Fermat number F10

45592577 · 6487031809 · 4659775785220018543264560743076778192897 · P252

where P252 is a prime of 252 digits. (This factorisation now takes about 102 seconds on mylaptop.)

In this section we describe this method for factoring integers that uses ellptic curves. Itis due to H. W. Lenstra, Jr.

Elliptic curves

Let k be a field and x3 + ax+ b ∈ k[x] a polynomial with three distinct roots. Then

E(k) = {(x, y) ∈ k2 | y2 = x3 + ax+ b} ∪ {O}

where O is a symbol, is called an elliptic curve.

Remark 2.2.22 Let f(x) = x3 + ax+ b. Then f has three distinct roots if and only if theredoes not exist α ∈ k with f(α) = f ′(α) = 0.

Let P = (α, β) ∈ E(k); we want to construct the line tangent to E(k) in P . To computethe slope we consider the derivative of y2 = x3 + ax+ b, that is,

2ydy

dx= 3x2 + a = f ′(x).

If f has three distinct roots then it is impossible that β2 = f(α) = 0 and f ′(α) = 0 at the

same time. So the tangent line has a well defined slope, namely 3α2+a2β (β = 0 means that the

line is vertical).

Write x3 + ax+ b = (x− α1)(x− α2)(x− α3) and define

∆ = −∏

i<j

(αi − αj)2

which is called the discriminant of the polynomial x3 + ax+ b. The latter has three distinctroots if and only if ∆ 6= 0. Furthermore, it is possible to show that ∆ = 4a3 +27b2. (We willnot go into that here.)

Conclusion: y2 = x3 + ax+ b defines an elliptic curve if and only if ∆ = 4a3 + 27b2 6= 0.

If k = R we can make a graph of the curve. It will look like this:


Note that the graph has to be symmetric with respect to the x-axis, as the equation isy2 = f(x). Hence (x0, y0) ∈ E(k) implies (x0,−y0) ∈ E(k).

One of the main points of elliptic curves is that we can define an addition + on it thatmakes it into an abelian group. This is done as follows:

- The neutral element is O, i.e., P +O = O + P = P for all P ∈ E(k).

- If P1, P2 ∈ E(k), P1 6= P2 and P1, P2 6= O then we construct the line ℓ through P1 and P2.The line ℓ intersects E(k) in a third point P3 = (x3, y3), and we set P1+P2 = (x3,−y3).

P1

P2

P3

P1 + P2

- If P1 = P2 ∈ E(k), P1 6= 0, then ℓ will be the tangent line at E(k) through P1; after whichwe do the same thing.


P1

P3

P1 + P1

- If the line ℓ is vertical then the sum will be O.

Theorem 2.2.23 The set E(k) with the operation + is an abelian group.

Here we do not prove this theorem; the difficult point is to show the associative law:

(P1 + P2) + P3 = P1 + (P2 + P3).

Addition formulas

Let P1, P2 ∈ E(k), P1 6= P2, P1, P2 6= O where Pi = (xi, yi).The line ℓ through P1 and P2 is

y − y1 =y2 − y1x2 − x1

(x− x1).

Set m = y2−y1x2−x1

; we compute the points of intersection of ℓ and the curve y2 = x3 + ax + b.We get

(m(x− x1) + y1)2 = x3 + ax+ b ⇐⇒ x3 −m2x2 + ux+ v = 0

for certain u and v.Two solutions of this equation are x1 and x2 because P1 and P2 are on the curve and on

the line. Hence

x3 −m2x2 + ux+ v = (x− x1)(x− x2)(x− x3) = x3 − (x1 + x2 + x3)x2 + . . .

so x1 + x2 + x3 = m2. Therefore

x3 = m2 − x1 − x2

y3 = m(x3 − x1) + y1.

It follows that P1 + P2 = (m2 − x1 − x2,−m(x3 − x1)− y1).We note that the sum does not depend on a and b. However, the points P1 and P2 of

course do.If P1 = P2 then we consider the tangent line ℓ. Take the derivative with respect to x of

y2 = x3 + ax+ b, i.e., 2y dydx = 3x2 + a. We get


- If y1 6= 0 then

m =3x21 + a

2y1

so the line ℓ has equation y = m(x− x1) + y1. It follows that P1 + P1 = (x3,−y3) with

x3 = m2 − 2x1

y3 = m(x3 − x1) + y1.

- If y1 = 0 then P1 + P1 = O. (Note that it is impossible that y1 = 3x21 + a = 0.)

Example 2.2.24 Take y2 = x3 + 17 and P1 = (−1, 4). Then

m =3(−1)2 + 0

8=

3

8

x3 =9

64+ 2 =

137

64

y3 =3

8

(137

64+ 1

)+ 4 =

2651

512.

So P1 + P1 =(13764 ,−2651

512

).

Factorisation with elliptic curves

The main idea is to use the group law on an elliptic curve together with the reduction modulop of its points.

Let p be a prime, and define

Ap =

{α

β∈ Q | p does not divide β

}.

N.B. If p does not divide β then there exists γ ∈ Z with γβ = 1 mod p. Write γ = β−1 mod p.

Define ψp : Ap → Fp, with ψp

(αβ

)= αβ−1 mod p. We have that Ap is a ring, and ψp is a

ring homomorphism.

Let a, b ∈ Z such that 4a3 + 27b2 6= 0 mod p. Then

E(Fp) = {(x, y) ∈ F2p | y2 = x3 + ax+ b} ∪ {O}

is an elliptic curve over Fp.

Moreover,

E(Q) = {(x, y) ∈ Q | y2 = x3 + ax+ b} ∪ {O}is an elliptic curve over Q.

Define ϕp : E(Q) → E(Fp) in the following way. Let P =(αβ ,

γδ

)∈ E(Q). If p does not

divide β, δ then

ϕp(P ) =

(ψp

(α

β

), ψp

(γδ

))

otherwise ϕp(P ) = O.


Theorem 2.2.25 The map ϕp is a group homomorphism. In other words, ϕp(P1 + P2) =ϕp(P1) + ϕp(P2).

Here we only prove a special case of this theorem.

Definition 2.2.26 Let p be a prime and P =(u1

v1, u2

v2

)∈ Q2. Then we say that P is good

for p if p does not divide v1 or v2.

Lemma 2.2.27 Let E(k) = {(x, y) | y2 = x3 + ax + b} ∪ {O} be an elliptic curve witha, b ∈ Z and p > 2 a prime not dividing ∆ = 4a3 + 27b2. Let ϕp : E(Q) → E(Fp) be thereduction modulo p. Let P1, P2 ∈ E(Q) be two points that are good for p. Then ϕp(P1+P2) =ϕp(P1) + ϕp(P2).

Proof. Let Pi = (xi, yi). Here we also write x mod p for ψp(x).- Suppose P1 6= P2, ϕp(P1) 6= ϕp(P2) and x1 mod p 6= x2 mod p. In this case one uses the

same addition formulas over Q and over Fp. Since mod p respects addition and multiplica-tion, we get that ϕp(P1 + P2) = ϕp(P1) + ϕp(P2). The same reasoning holds when P1 = P2.(Then of course ϕp(P1) = ϕp(P2)).

- Suppose that P1 6= P2 and x1 mod p = x2 mod p. Write x2 = x1 + prx with x ∈ Q,x mod p 6= 0. Then y21 = y22 mod p because x31 + ax1 + b = x32 + ax2 + b mod p and hencey1 = ±y2 mod p. We calculate

y22 = x32 + ax2 + b

= (x1 + prx)3 + a(x1 + prx) + b

= x31 + ax1 + b+ (3x21 + a)prx+ ∗pr+1

= y21 + (3x21 + a)prx+ ∗pr+1

where ∗ is a rational number we don’t want to write down.

Hence(y2 + y1)(y2 − y1) = (3x21 + a)prx+ ∗pr+1.

Now we distinguish three cases. In the first we have y1 = y2 mod p, and y2 + y1 6= 0 mod pIn this case

y2 − y1 = (3x21 + a)prx(y2 + y1)−1 + ∗pr+1

for some ∗.To compute P1 + P2 in E(Q) we use

m =y2 − y1x2 − x1

=3x21 + a

y2 + y1+ ∗p

as x2 − x1 = prx.

Hencem mod p =3x2

1+a2y1

mod p which is exactly them that is used for computing ϕp(P1)+ϕp(P2). Hence

ϕ(P1 + P2) = ϕp(P1) + ϕp(P2).

In the second case we have y1 = −y2 mod p and y2 − y1 6= 0 mod p. Then

m =y2 − y1prx

.


Since r > 0 we get ϕp(P1 + P2) = O, which is equal to ϕp(P1) + ϕp(P2).

In the third case we have y2 + y1 = 0 mod p and y2 − y1 = 0 mod p. Then, sincep > 2, we get y1 mod p = y2 mod p = 0. Hence ϕp(P1) = ϕp(P2) = (ψp(x1), 0). Henceϕp(P1) + ϕp(P2) = O. Also 3x21 + a 6= 0 mod p, otherwise p|∆. So pr is the highest powerof p that divides (y2 + y1)(y2 − y1). Since p divides both factors we get that y2 − y1 is onlydivisible by ps for some s < r. Therefore, when computing the sum in E(Q) we use an m ofthe form a

b with p|b. It follows that ϕp(P1 + P2) = O. �

The idea lying behind the elliptic curve method for factorising integers is the following.The group E(Fp) is finite, so for P ∈ E(Fp) there exists k with

P + . . . + P︸︷︷︸k

= O.

Let Q ∈ E(Q) with ϕp(Q) = P . Then by Theorem 2.2.25

ϕp(Q+ . . .+Q︸︷︷︸k

) = P + . . .+ P︸︷︷︸k

= O.

Hence kQ = Q+ . . .+Q is equal to O or it has coordinates with a denominator divisible byp.

Algorithm 2.2.28 Given: a composite number n.We compute: a factor of n

1. We choose a curve y2 = x3 + ax+ b, a, b ∈ Z, with a point P on E(Q).

2. Let d = gcd(n, 4a3 +27b2). If d = n we choose a different curve. If d > 1 and d < n wehave found a factor of n.

3. Assume d = 1. Set k = lcm(2, 3, . . . ,K) for a certain K.

4. Compute kP =(u1

v1, u2

v2

). Let di = gcd(vi, n). If di is bigger than 1, and smaller than

n, then we have found a factor. Othewise we retry with a bigger K, or a different curve.

N.B. We know that n is not prime. The method works if

- (let p be a prime dividing n),

- if the order of ϕp(Q) divides k then ϕp(kQ) = kϕp(Q) = O; so if kQ 6= O then p dividesthe denominator of u or of v.

Theorem 2.2.29 (Hasse) We have

p+ 1− 2√p ≤ |E(Fp)| ≤ p+ 1 + 2

√p.

Remark 2.2.30 If |E(Fp)| divides k then we find p. For example when K ≥ p+ 1 + 2√p.


Example 2.2.31 Suppose that 61 divides n. Let Ea be the curve y2 = x3 + ax+ 3− a andP = (1, 2). We have

a |Ea(F61)| order of (P mod 61)−4 68 68−3 54 9−2 76 38−1 69 690 48 121 68 42 66 333 72 64 67 67

Now 4P = O ∈ E1(Q) and 6P =(5182560116208676 , ∗

)∈ E3(Q) and 61 divides 16208676.

Remark 2.2.32 It is enough to compute kP modulo n. Observe that if rP =(u1

v1, u2

v2

)and

gcd(vi, n) 6= 1, then we have found a factor. Otherwise if gcd(vi, n) = 1 then there exist ci, diwith civi + din = 1 and hence ui

vimod n = uici mod n. This allows us to work with integer

coordinates modulo n.

Example 2.2.33 Let’s factorise n = 39. Let E be the curve given by y2 = x3 + x − 1 andP = (1, 1) a point on it. We have ∆ = 31 and gcd(31, 39) = 1. Take k = 6.

We have 2P = (2,−3). Let’s compute 4P :

m =3x21 + a

y1=

12 + 1

−6= −13

6

and since gcd(6, 39) = 3 we have found a factor.

Example 2.2.34 Now for something more difficult. Take n = 185 with the curve of Example2.2.33 and k = 8. Again ∆ = 31 and gcd(31, 185) = 1 so y2 = x3 + x− 1 defines an ellipticcurve modulo every prime that divides n.

Also, 2P = (2,−3).Now we compute 4P . Again m = −13

6 . Now

185 = 1 · 185 + 0 · 66 = 0 · 185 + 1 · 65 = 1 · 185 − 30 · 61 = −1 · 185 + 31 · 6

hence 6−1 mod 185 = 31. It follows that

m mod 185 = −13 · 31 mod 185 = 152 mod 185.

So

x3 = m2 − 2x1 = 1522 − 2 · 2= 160 mod 185

y3 = m(x3 − x1) + y1 = 152(160 − 2)− 3

= −37 mod 185.


Hence 4P = (160, 37) mod 185.Now we compute 8P . We have

m =3x21 + a

2y1=

3 · 1602 + 1

74.

Furthermore,185 = 1 · 185 + 0 · 7474 = 0 · 185 + 1 · 7437 = 1 · 185 − 2 · 740 = −2 · 185 + 5 · 74

so gcd(185, 74) = 37 and 185 = 5 · 37.Here we note that the order of P in E(Q) is ∞, while the order of P in E(F37) is 8.

Example 2.2.35 In his 1987 paper (Speeding the Pollard and Elliptic Curve Methods ofFactorization, Math. Comp.), Peter Montgomery proposes to use elliptic curves Eα,β givenby the equation

βy2 = x3 + αx2 + x.

The discriminant of the polynomial on the right is ∆ = α2 − 4. So we take α 6= ±2, and ofcourse β 6= 0.

First we derive the addition formulas on this curve. This goes in the same way as before.For i = 1, 2, let Pi = (xi, yi) be points on Eα,β. Suppose that x1 6= x2 and set m = y2−y1

x2−x1,

and let y = mx + b be the equation of the line through P1, P2. Then intersecting this linewith the curve leads to the equation β(mx + b)2 = x3 + αx2 + x, which is the same asx3+(α−βm2)x2+∗x+∗ = 0. We know two solutions to this equation, namely x1 and x2. Sothe polynomial on the left hand side is (x−x1)(x−x2)(x−x3) = x3+(−x1−x2−x3)x2+ · · · .Hence

x3 = βm2 − α− x1 − x2

is the x-coordinate of the sum P3 := P1 +P2 = (x3, y3). Now we perform some manipulation,using βy2i = x3i + αx2i + xi:

x3(x1 − x2)2 = β(y1 − y2)

2 − (x1 − x2)2(α+ x1 + x2)

= −2βy1y2 + x21x2 + x1x22 + 2αx1x2 + x1 + x2

= −2βy1y2 +x2x1

(x31 + αx21 + x1) +x1x2

(x32 + αx22 + x2)

= β(x2y1 − x1y2)

2

x1x2.

Set P4 = P1 − P2 = P1 + (−P2) and write P4 = (x4, y4). Since −P2 = (x2,−y2) we getx4(x1 − x2)

2 = β(x2y1 + x1y2)2/x1x2. We multiply the two formulas we obtained:

x3x4(x1 − x2)4 = β2

(x22y21 − x21y

22)

2

x21x22

=(x22(x

31 + αx21 + x1)− x21(x

32 + αx22 + x2))

2

x21x22

= (x21x2 + x2 − x1x22 − x1)

2

= (x1 − x2)2(x1x2 − 1)2.


The conclusion isx3x4(x1 − x2)

2 = (x1x2 − 1)2. (2.2)

Next we consider the case where P1 = P2. In this case the x-coordinate of the sum P3 =P1 + P2 = 2P1 is

x3 = βm2 − α− 2x1 where m =3x21 + 2αx1 + 1

2βy1.

Now on the one hand, x3 · 4βy21 = 4x1x3(x21 + αx1 + 1). On the other hand,

x3 · 4βy21 = (3x21 + 2αx1 + 1)2 − 8βx1y21 − 4αβy21

= (3x21 + 2αx1 + 1)2 − (8x1 − 4α)(x31 + αx21 + x1)

= (x21 − 1)2.

So in this case we get4x1x3(x

21 + αx1 + 1) = (x21 − 1)2. (2.3)

Let Q be a point of Eα,β(Q), and write the x-coordinate of kQ as uk

dk, where uk, dk ∈ Z (but

not necessarily gcd(uk, dk) = 1). Set P1 = Qk+1, P2 = Qk. Then P3 = P1 + P2 = Q2k+1 andP4 = P1 − P2 = P1. Then (2.2) implies that

u2k+1

d2k+1=d1(uk+1uk − dk+1dk)

2

u1(uk+1dk − ukdk+1)2

so we can set u2k+1 = d1(uk+1uk − dk+1dk)2 and d2k+1 = u1(uk+1dk − ukdk+1)

2. If we setP1 = kQ, then from (2.3) we get

u2kd2k

=u4k − 2u2kd

2k + d4k

4(u3kdk + αu2kd2k + ukd

3k),

so that u2k = (u2k − d2k)2 and d2k = 4ukdk(u

2k + αukdk + d2k).

The point is that these formulas make it possible to compute uk mod n, dk mod n ratherquickly. Moreover, if the order of Q modulo p divides k, then p divides dk and hence gcd(n, dk)finds p. So we compute dk mod n for some k with many divisors, and compute gcd(n, dk). Ifno divisor is found then we increase k, or try with another curve. This way the computationof various inverses modulo n is avoided.

For example, one can take α = a and β = 4a+ 10, and Q = (2, 1), for various a.

2.2.4 Complexity

Here we list some known facts about the complexity of the methods that we have seen (andsome that we havan’t seen), without bothering about the proofs.

- The algorithm trying division by k = 2, 3, . . . ,√n has complexity O(p) (order p), where

p is the smallest prime factor of n. But, in the worst case, O(p) = O(√n) and

√n = n

1

2 =exp

(12 log n

)and log n ∼= “number of digits of n” = size of n. So exp

(12 log n

)is exponential

in the input size.- The elliptic curve method has estimated complexity O(exp

√log p log(log p)) where p is

the smallest factor of n. This is called “subexponential”.- The continued fraction method has estimated complexity O(exp

√2 log p log(log p)).

- Two other famous methods are: the quadratic sieve with complexity O(exp√

log n log(log n)),and the number field sieve, with complexity O(exp (log p)1/3(log(log p))2/3).


2.3 Primality proving with elliptic curves

In 1986 Goldwasser and Kilian published a method for proving that a given n, of which ithas been established that it is prime with high probability, in fact is prime. It uses ellipticcurves, and is based on the following theorem.

Theorem 2.3.1 Let E be an elliptic curve with equation y2 = x3 + ax + b with a, b ∈ Z.Suppose that for 1 ≤ i ≤ r there are distinct prime numbers pi and points Pi ∈ E(Q), suchthat

• Pi is good for n, 1 ≤ i ≤ r,

• piPi is not good for n, 1 ≤ i ≤ r,

• p1 · · · pr > (n14 + 1)2.

Then n is prime.

Proof. Let p be a prime factor of n. Since the Pi are good for n, they are also good for p.So we get points ϕp(Pi) ∈ E(Fp). Moreover, piϕp(Pi) = O for all i. So ϕp(Pi) has order pi.Hence pi divides |E(Fp)| and therefore so does p1 · · · pr. So we get

(n14 + 1)2 < p1 · · · pr ≤ |E(Fp)| < p+ 1 + 2

√p = (

√p+ 1)2

implying that p >√n. So the prime factors of n are greater that

√n. We conclude that n is

prime. �

Example 2.3.2 Let n = 1873 and let E be given by y2 = x3 − 3x+6; and P = (1, 2). Then101P is not good for n. (Note that this can be established by doing some additions modulo

n.) But 101 > (n14 + 1)2 = 57.4 . . .. It follows that n is prime.

The basic problem with this test is to find a suitable elliptic curve E and points Pi onit that are good for n, but for which there exist relatively small primes pi such that piPi

are not good for n. (Note that the pi need to be small with respect to n, otherwise theproof that the pi are prime is as difficult as proving this for n.) In 1993 Atkin and Morainpublished a method for that, using the theory of complex multiplication. In practice thisworks surprisingly well, and huge numbers have been shown to be prime with this method.

2.4 Exercises

1. The smallest Carmichael number is n = 561. Show that it is not prime, using theMiller-Rabin test.

2. Factorise 203 and 899 with the method of Fermat.

3. In this exercise we find the factorisation of n = 8616460799 with Fermat’s method. Sowe need to find t > s such that t2 − s2 = n.

2.4 Exercises 57

(a) We have n mod 3 = 2. Show that k2 mod 3 is 0 or 1 for k ∈ Z. Prove that ift2 mod 3 = 1, then t2 − n cannot be a square. Conclude that t has to be divisibleby 3.

(b) We have n mod 8 = 7. Show that k2 mod 8 is 0,1,4. Prove that if t2−n is a square,then t2 = 0 mod 8. Conclude that t is divisible by 4.

(c) Prove that t is divisible by 12.

(d) Now try for t all multiples of 12, bigger than ⌈√n⌉. Factorise n into a product oftwo smaller integers.

(e) The English economist W. S. Jevons (1835-1882) wrote: ”Given any two numbers,we may by a simple and infallible process obtain their product, but it is quiteanother matter when a large number is given, to determine its factors. Can thereader say what two numbers multiplied together produce the number 8616460799?I think it unlikely that anyone but myself will ever know.”

4. Find the first 7 convergents of the continued fraction of√5.

5. Factorise 299, 341, 1537 and 1139 with the continued fraction method.

6. Let a > 1 be an integer and

θ =a+

√a2 + 4

2.

Show that for the continued fraction of θ we have a = a0 = a1 = a2, . . ..

7. Let N be a positive integer that is not a square. For i ≥ 0 let xi and ai be as inthe algorithm for computing the continued fraction of

√N . We consider the following

statement:

xi =ui +

√N

viwhere ui, vi ∈ Z satisfy vi divides N − u2i .

(a) Show that the statement is true for i = 0.

(b) Suppose that the statement is true for some i ≥ 0. Show that

xi+1 =vi(aivi−ui+

√N)

N−(aivi−ui)2.

(c) Show that vi divides N − (aivi − ui)2.

(d) Show that by setting ui+1 = aivi − ui, vi+1 =N−u2

i+1

viwe obtain the statement

for i + 1. (Remark: this gives a method for computing the ui, vi that is easy toimplement on a computer.)

(e) Show that vi+2 = vi − a2i+1vi+1 + 2ai+1ui+1 (so that we can avoid a division whencomputing vi+2).

8. Let

x =1 +

√5

2.

Let a0, a1, . . . be the integers corresponding to the continued fraction of x.


(a) Prove that ai = 1 for i ≥ 0.

(b) Let Fn be the n-th Fibonacci number (that is, F0 = 1, F1 = 1, Fn+1 = Fn+Fn−1).Prove that the convergents of the continued fraction of x are Fn+1

Fnfor n ≥ 0.

9. Consider the ellptic curve with equation y2 = x3 +x− 1. Let P = (1, 1) ∈ E. Compute3P = P + P + P .

10. In this exercise we factorise n = 65 = 5 · 13 with the elliptic curve method. Let E bethe elliptic curve with equation y2 = x3 + 2x+ 1 and P = (1, 2), a point.

(a) Check that the equation defines an elliptic curve modulo every prime that dividesn.

(b) Compute all points of E(F5) (here it can be handy to make a table of all squaresmodulo 5, and all x3 + 2x+ 1 for x ∈ F5). Show that kϕ5(P ) = O implies that kis divisible by 7. (Here ϕ5(P ) is the reduction modulo 5 of P .)

(c) Compute all points of E(F13). Prove that 4ϕ13(P ) = O.

(d) Compute 4P modulo n, and factorise n.

11. Again we consider n = 65, but now we take the elliptic curve E with equation y2 =x3 + 3x+ 2 and point P = (2, 4).

(a) Check that the equation defines an elliptic curve modulo every prime that dividesn.

(b) Compute all points of E(F5). Show that kϕ5(P ) = O if and only if k is divisibleby 5.

(c) Compute 5P modulo n and factorise n.

12. Factorise n = 115 with the elliptic curve method. (For example with the curve y2 =x3 + 2x− 3 and point P = (2, 3).)

Chapter 3

Polynomial Factorisation

The problem considered in this chapter is to find the factorisation of a polynomial in k[x],where k is a field.

The algorithms depend heavily on k. Here we treat algorithms for finite fields k = Fq,with q = pn, and k = Q.

3.1 Some generalities on polynomials

Lemma 3.1.1 For f, g ∈ k[x] there exist unique q, r ∈ k[x] with deg(r) < deg(g) and f =qg + r (division with remainder).

Lemma 3.1.2 Let I ⊂ k[x] be an ideal. Then I is generated by a single element, that is,there is a g ∈ k[x] with I = {fg | f ∈ k[x]}.

Proof. Let g ∈ I be a nonzero element of minimal degree. For h ∈ I write h = qg + r withdeg(r) < deg(g). This implies r ∈ I whence r = 0 and h = qg. �

Lemma 3.1.3 Let f1, f2 ∈ k[x]. Then there exists a unique monic g ∈ k[x] with

1) g divides f1, f2;

2) if h divides f1, f2 then h divides g.

Proof. Let I ⊂ k[x] be the ideal generated by f1, f2, that is, I = {h1f1 + h2f2 | hi ∈ k[x]}.Then by the previous lemma I is generated by a monic g (of monimal degree). Now f1, f2 ∈ Ihence g divides f1 and f2.

If h divides f1, f2 then g = h1f1+h2f2 (since g ∈ I = 〈f1, f2〉); we conclude that h dividesg.

In order to show uniqueness, let g′ ∈ k[x] with the same properties as g. Then by 1) and2), g′ divides g. Analogously g divides g′. Since g and g′ are monic we get g = g′. �

Definition 3.1.4 The polynomial g from the previous lemma is called the greatest commondivisor of f1 and f2.

60 Polynomial Factorisation

From the proof of Lemma 3.1.3 it follows that there exist h1, h2 such that h1f1+h2f2 = g.In the same way as for the integers we have a euclidean algorithm for computing the greatestcommon divisor, and the h1, h2. It is based on the following lemma.

Lemma 3.1.5 Write f1 = qf2 + r with deg(r) < deg(f2). Then gcd(f1, f2) = gcd(f2, r).

Proof. Set

D1 = {h ∈ k[x] | h divides f1, f2} and D2 = {h ∈ k[x] | h divides f2, r}.

Then D1 = D2. So the elements of maximal degree of D1 and D2 coincide. �

To compute gcd(f1, f2) we replace (f1, f2) by (f2, r) and so on. At a certain point we findthe pair (g, 0) and gcd(g, 0) = g

Example 3.1.6 Let f1 = x7 + 1, f2 = x4 + x2 + x ∈ F2[x]. Then

f1 = (x3 + x+ 1)f2 + x3 + x+ 1.

Set f3 = x3 + x+ 1, then

f2 = xf3 + 0

hence gcd(f1, f2) = gcd(f2, f3) = gcd(f3, 0) = f3.

N.B. A polynomial h ∈ k[x] is called irreducible if h 6∈ k and for every factorisation h = abwith a, b ∈ k[x] we have that a or b lies in k.

Lemma 3.1.7 Let a ∈ k[x] be irreducible and suppose that a divides bc where b, c ∈ k[x].Then a divides b or a divides c.

Proof. If a does not divide b then gcd(a, b) = 1 so there exist h1, h2 with h1a + h2b = 1whence c = h1ac+ h2bc. Therefore a divides c. �

Theorem 3.1.8 Let f ∈ k[x], then there exist c ∈ k, irreducible monic f1, . . . , fr ∈ k[x] ande1, . . . , er ∈ Z>0 with f = cf e11 · · · f err . Moreover, this factorisation is “essentially unique”;meaning that if we have another one f = dgd11 · · · gdss , then c = d, r = s, and after a permu-tation of the indices, fi = gi, ei = di.

Proof. Note that c is the coefficient of the highest degree monomial in f , hence it is uniquelydetermined. So without loss of generality we may assume that f is monic. If f is irreduciblethen there is nothing to prove. So suppose that f = ab where a, b ∈ k[x] are monic withdeg(a),deg(b) < deg(f). By induction on the degree a and b are products of irreduciblepolynomials, hence so is f .

To show uniqueness suppose that f = f e11 · · · f err = gd11 · · · gdss , where also the gi areirreducible and monic.

By Lemma 3.1.7 f1 divides a gi. But gi is irreducible and monic, hence f1 = gi. Cancellingboth from the products, and by induction on the degree we conclude that the factorisation isesentially unique. �

3.1 Some generalities on polynomials 61

Corollary 3.1.9 Let p, q, r ∈ k[x] with gcd(q, r) = 1. Then gcd(p, qr) = gcd(p, q) gcd(p, r).

Proof. Let f, g ∈ k[x]. Then by the previous theorem we can write f = c1fe11 · · · f emm ,

g = c2fd11 · · · fdmm , where the fi are monic and irreducible and ei, di ∈ Z≥0. From this it

follows that gcd(f, g) = fa11 · · · farr , where ai = min{di, ei}.So since gcd(q, r) = 1, the factorisation of qr is obtained by appending the factorisation

of r to that of q. This implies the statement of the corollary. �

Problem. Given a monic f ∈ k[x] find monic irreducible f1, . . . , fr such that f =f e11 · · · f err .

Let R1, . . . , Rs be rings. We recall the construction of the direct product: R = R1×· · ·×Rs

is the set consisting of (r1, . . . , rs) with ri ∈ Ri; the ring operations are defined as follows

(r1, . . . , rs) + (r′1, . . . , r′s) = (r1 + r′1, . . . , rs + r′s)

and

(r1, . . . , rs)(r′1, . . . , r

′s) = (r1r

′1, . . . , rsr

′s).

Then R is again a ring.

We denote the ideal generated by f ∈ k[x] by 〈f〉, so 〈f〉 = {gf | g ∈ k[x]}. Also, we write[h]f = h + 〈f〉 for the coset of h modulo 〈f〉. If it is clear which f is meant, then we alsowrite [h]. The polynomial h is called a representative of the coset [h]f ; note that a coset doesnot have a unique representative, indeed, all h+ gf are representatives of the same coset. Iff = xn + an−1x

n−1 + · · ·+ a0 then every coset has a unique representative of degree < n.

The quotient ring k[x]/〈f〉 consists, by definition, of all cosets [h]f for h ∈ k[x]. They areadded and multiplied by [h1] + [h2] = [h1 + h2], [h1][h2] = [h1h2]. It is routine to show thatthese operations are well-defined, i.e., do not depend on the chosen representatives.

Theorem 3.1.10 (Chinese remainder theorem) Let f1, f2 ∈ k[x] be such that gcd(f1, f2) =1. Then there is an isomorphism

ϕ : k[x]/〈f1f2〉 → k[x]/〈f1〉 × k[x]/〈f2〉,

defined by ϕ([h]f1f2) = ([h]f1 , [h]f2).

Proof. First we show that ϕ is well-defined. Let h′ ∈ k[x] be such that [h]f1f2 = [h′]f1f2 .Then h′ = h+ gf1f2, so [h′]fi = [h]fi , i = 1, 2.

From the definitions of addition and multiplication in the various rings that appear, it isobvious that ϕ respects these operations.

We show that ϕ is injective. Suppose that ϕ([h]f1f2) = ([0]f1 , [0]f2). That means that his divisible by both f1 and f2. Since gcd(f1, f2) = 1 it follows that f1f2 divides h, so that[h]f1f2 = [0]f1f2 .

Finally we show that ϕ is surjective. There are polynomials a, b ∈ k[x] with af1+ bf2 = 1.So [af1]f2 = [1 − bf2]f2 = [1]f2 and similarly [bf2]f1 = [1]f1 . Let h1, h2 ∈ k[x] and seth = h2af1 + h1bf2. Then [h]f1 = [h1bf2]f1 = [h1]f1 [bf2]f1 = [h1]f1 , and analogously,[h]f2 = [h2]f2 . We conclude that ϕ([h]f1f2) = ([h1]f1 , [h2]f2). �


3.2 Berlekamp’s algorithm

In this section we describe an algorithm due to Elwyn Berlekamp (1940- )

for factorising a polynomial over a finite field. Berlekamp is known, among other things, forhis work in coding theory and game theory.

Definition 3.2.1 Let f ∈ k[x] be monic and f = f e11 · · · f err with fi irreducible and monic.Then the f eii are called the primary factors of f .

In the following we write h = g mod f to express that h− g is divisible by f , or, in otherwords, [h]f = [g]f .

Lemma 3.2.2 Let f ∈ Fq[x] be monic and v ∈ Fq[x] with vq = v mod f . Then

f =∏

a∈Fq

gcd(f, v − a).

Proof. In Fq[Y ] we have

Y q − Y =∏

a∈Fq

(Y − a)

(because aq = a for all a ∈ Fq). Substituting v for Y we obtain

vq − v =∏

a∈Fq

(v − a).

But vq − v is divisible by f , so f = gcd(f, vq − v).

Observe that gcd(v − a, v − b) = 1 if a 6= b, a, b ∈ Fq. Indeed, if g divides v − a and v − bthen g divides b− a 6= 0.

Using Corollary 3.1.9 we see that

f = gcd(f, vq − v)

= gcd(f,∏

a∈Fq

(v − a))

=∏

a∈Fq

gcd(f, v − a).

�

3.2 Berlekamp’s algorithm 63

Lemma 3.2.3 Let f ∈ Fq[x] be monic and

V = {[h] ∈ Fq[x]/〈f〉 | [h]q = [h]}.

Write f = f e11 · · · f err where the fi are irreducible and distinct. Then V is a vector space overFq of dimension r.

Note that [h]q = [hq] so [h]q = [h] is the same as hq = h mod f .

Proof. Let v = [h], w = [g] ∈ V , then v+w = [h+ g] and (h+ g)q = hq + gq = h+ g mod f ,so that v + w ∈ V . Furthermore, let α ∈ Fq, then αv = [αh] and (αv)q = αqvq = αvq =αv mod f , whence αv ∈ V . It follows that V is a vector space over Fq.

By Theorem 3.1.10 there exists a ring isomorphism

ϕ : Fq[x]/〈f〉 → Fq[x]/〈f e11 〉 × · · · × Fq[x]/〈f err 〉,

where ϕ([h]f ) = ([h]fe11, . . . , [h]fer

r).

Observe that by applying ϕ we get that [h]qf = [h]f is equivalent to [h]qfeii

= [h]feii

for

1 ≤ i ≤ r.

Let [h]f ∈ V then, as just seen, hq = h mod f eii . By Lemma 3.2.2 it now follows

f eii =∏

a∈Fq

gcd(f eii , h− a). (3.1)

But h− a and h− b are coprime when a, b ∈ Fq and a 6= b. Hence in (3.1) there is only onenontrivial factor gcd(f eii , h−ai), for a unique ai ∈ Fq. Therefore f

eii = gcd(f eii , h−ai), imply-

ing that f eii divides h − ai. It follows that h = ai mod f eii and ϕ([h]) = ([a1]fe11, . . . , [ar]fer

r).

So ϕ(V ) ⊂ Fq× . . .×Fq where Fq ⊂ Fq[x]/〈f eii 〉 are the constant polynomials (more precisely:the cosets that have a representative in Fq).

But aq = a for all a ∈ Fq. So if [h] ∈ Fq[x]/〈f〉 is such that ϕ([h]) = ([a1]fe11, . . . , [ar]fer

r)

where ai ∈ Fq, then [h]q = [h] and [h] ∈ V . Hence Fq × . . .× Fq ⊂ ϕ(V ).

It follows that ϕ(V ) = Fq × . . . × Fq (r factors), implying that V is a vector space ofdimension r. �

Now we give Berlekamp’s algorithm for finding the primary factors of a monic f ∈ Fq[x].

Algorithm 3.2.4 Given: f ∈ Fq[x], monic.Compute: the primary factors of f .

1. Let {v1 = 1, v2, . . . , vr} be such that {[v1], . . . , [vr]} is a basis of V = {[h] ∈ Fq[x]/〈f〉 |[h]q = [h]}.

2. Set P1 = {f} and for j = 2, . . . , r let

2a) Pj be the set consisting of the nontrivial elements of the sets {gcd(h, vj − a) | a ∈Fq}, where h ∈ Pj−1.

3. Return Pr.

Lemma 3.2.5 The algorithm of Berlekamp finds the primary factors of f .


Proof. Write P = Pr. We have to show that

- f is the product of the elements in P ;

- the elements of P are coprime;

- the elements of P are powers of irreducible polynomials.

First we claim that the product of the elements of Pj is f . This is certainly true for j = 1.Suppose the claim holds for Pj−1. Let h ∈ Pj−1, then h divides f , whence vqj = vj mod h. Soby Lemma 3.2.2,

h =∏

a∈Fq

gcd(h, vj − a).

Also the elements of Pj are coprime. Indeed, the elements of Pj are of the form gcd(h, vj−a), for a ∈ Fq, h ∈ Pj−1. Now for different a ∈ Fq such factors are coprime. But also fordifferent h (and the same a), because by induction the elements of Pj−1 are coprime.

Now let h ∈ P . Suppose that h is not a power of an irreducible. Then from what is saidabove it follows that h is divisible by f eii and by f

ejj , i 6= j. To ease notation we assume that

i = 1 and j = 2.

We fix a j ≥ 1. Then for j ≤ l ≤ r and g ∈ Pl there exists aj ∈ Fq (depending on g) withvj = aj mod g. Again we use induction to show this. Note that the elements of Pj are factorsof vj − a, for various a ∈ Fq. Hence for l = j the statement holds. Now let g ∈ Pl, l > j.Then g is a factor of a g ∈ Pl−1. By induction vj = aj mod g, hence also vj = aj mod g.

We apply this to h ∈ P = Pr to conclude that there is aj ∈ Fq with vj = aj mod h for1 ≤ j ≤ r.

Now let [v] ∈ V and write [v] =∑r

j=1 βj [vj ], βj ∈ Fq. Since h divides f we get v =∑j βjvj mod h, and by the above

v =

r∑

j=1

βjaj mod h.

Set av =∑r

j=1 βjaj; then v = av mod h, and av ∈ Fq.

Since f e11 , f e22 divide h we get v = av mod f e11 and v = av mod f e22 . But as seen in the proofof Lemma 3.2.3, ϕ : V → Fq×. . .×Fq is an isomorphism. But ϕ(v) = ([av ]fe1

1, [av]fe2

2, ∗, . . . , ∗),

in other words, the first two coordinates are always equal. This implies that ϕ is not surjec-tive, and hence we have obtained a contradiction. �

Remaining problem. Given f ∈ Fq[x], f = ge with g irreducible, find g and e.

For this we compute f ′ = ddxf = eg′ge−1. There are two cases:

1) f ′ = 0. Then we claim that f is a polynomial in xp where q = pm, p a prime. Indeed,the exponents of x that occur in f are disible by p. Hence f = h(xp) = h1(x)

p. We computeh1, which again is a power of g, and continue with h1.

2) f ′ 6= 0. Then g = fgcd(f,f ′) since gcd(f, f ′) = ge−1.

Example 3.2.6 Let f = x4 + x3 + x + 1 ∈ F2[x]. Write v ∈ F2[x]/〈f〉 as v = a0 + a1x +a2x

2+a3x3, ai ∈ F2 (more precisely: the last expression is the unique representative of degree

< deg(f) of a coset in F2[x]/〈f〉).

3.3 The algorithm of Cantor-Zassenhaus 65

Since a2i = ai we get v2 = a0 + a1x2 + a2x

4 + a3x6. Modulo f we have:

x4 = x3 + x+ 1

x5 = x4 + x2 + x = x3 + x+ 1 + x2 + x

= x3 + x2 + 1

x6 = x4 + x3 + x = x3 + x+ 1 + x3 + x

= 1

hence

v2 = a0 + a1x2 + a2(x

3 + x+ 1) + a3 mod f

= a0 + a2 + a3 + a2x+ a1x2 + a2x

3 mod f

and therefore

a0 + a2 + a3 = a0a2 = a1a1 = a2a2 = a3

⇐⇒ a1 = a2 = a3

so a basis of V is {v1 = 1, x+ x2 + x3}. So, in particular, r = 2.

In step 2a) we replace f with

h1 = gcd(f, x+ x2 + x3) = x2 + x+ 1

h2 = gcd(f, 1 + x+ x2 + x3) = x2 + 1.

So P = {h1, h2}. We have h′1 = 1 so that gcd(h1, h′1) = 1, thus h1 is irreducible. Furthermore,

h′2 = 0 implies h2 = (x+ 1)2 and (x+ 1)′ = 1 so it is irreducible.

We conclude that f = (x+ 1)2(x2 + x+ 1) is the factorisation of f .

3.3 The algorithm of Cantor-Zassenhaus

The algorithm of Berlekamp has the disadvantage to have to compute gcd(f, v−a) for a ∈ Fq.If q gets large this is very laborious. Here we sketch a different aproach, due to David G.Cantor (1935-2012) and Hans Zassenhaus (1912-1991), based on the possibility of makingrandom choices. For this we assume that q is odd.

Lemma 3.3.1 Let γ ∈ F∗q, then γ

q−1

2 = ±1. Moreover, γq−1

2 = 1 if and only if γ is a square

in Fq and γq−1

2 = −1 if and only if γ is not a square.

Proof. Let α ∈ F∗q be a primitive element: αq−1 = 1, αk 6= 1 for k < q − 1. Then γ = αi,

and

γq−1

2 =(α

q−1

2

)i.

We have that(α

q−1

2

)2= 1 implies α

q−1

2 = ±1 (there are only two roots of 1 in Fq) but

αq−1

2 6= 1 so αq−1

2 = −1. Hence γq−12 = (−1)i.


Hence if γ is a square then γ = α2k, and hence γq−1

2 = (−1)2k = 1. If γ is not a square

then γ = α2k+1 so that γq−1

2 = (−1)2k+1 = −1. �

As before, we consider the space

V = {[h] ∈ Fq[x]/〈f〉 | [h]q = [h]}.

Let [h] ∈ V , then

hq − h = h(h

q−1

2 − 1)(

hq−1

2 + 1).

Note that these factors are coprime, so by Corollary 3.1.9,

f = gcd(f, hq − h) = gcd(f, h) gcd(f, hq−1

2 − 1) gcd(f, hq−1

2 + 1).

This factorisation of f is trivial (that is, f = f ·1 ·1) if and only if f divides one of h, hq−1

2 −1,

hq−1

2 + 1.We may assume that deg(h) < deg(f) so f does not divide h.Let ϕ : Fq[x]/〈f〉 → Fq[x]/〈f e11 〉×· · ·×Fq[x]/〈f e11 〉 be the isomorphism of Theorem 3.1.10,

where the f eii are the primary factors of f . Then as seen in the proof of Lemma 3.2.3,ϕ(V ) = Fq × · · · × Fq (r factors); so ϕ([h]) = ([a1], . . . , [ar]), ai ∈ Fq.

Now f divides hq−1

2 −1 if and only if hq−1

2 = 1 mod f and hence if and only if ϕ([h])q−1

2 =

([1], . . . , [1]); or aq−1

2

i = 1 for all i. By Lemma 3.3.1 we have that ai ∈ F∗q is a square for all i.

Analogously f divides hq−1

2 + 1 if and only if ai ∈ F∗q is not a square for all i.

Set

C = {(a1, . . . , ar) ∈ F∗qr | ai is a square ∀i}

∪ {(a1, . . . , ar) ∈ F∗qr | ai is not a square ∀i}.

We have

|C| =(q − 1

2

)r

+

(q − 1

2

)r

= 2

(q − 1

2

)r

.

If we take [h] ∈ V by random choice (where we use a uniform distribution) then the probabilitythat we do not find a factorisation is

P(ϕ(v) ∈ C) =|C||V | =

2(q−12

)r

qr= 2

(1− 1

q

2

)r

<1

2.

So if k times we randomly choose a v the probability of not finding a factorisation is less than(12

)k.Hans Zassenhaus (1912-1991)

3.4 Factorisation of polynomials over Q 67

made many contributions to abstract algebra. He was a pioneer in the area of computationalalgebra, using computers from the time when they were invented (i.e., the 50’s). In compu-tational algebra his main interest lay with computational number theory; he wrote a bookabout the subject together with Michael Pohst. But he also worked on algorithmic problemsrelated to Lie algebras.

3.4 Factorisation of polynomials over Q

First we show that the factorization of polynomials over Q is the same as the factorization ofpolynomials over Z.

Definition 3.4.1 Let f ∈ Z[x], f = a0 + a1x+ . . .+ anxn, ai ∈ Z. Then

c(f) = gcd(a0, a1, . . . , an)

is called the content of f .

Lemma 3.4.2 Let f, g ∈ Z[x] with c(f) = c(g) = 1, then c(fg) = 1.

Proof. Suppose that c(fg) > 1. Then there exists a prime p dividing all coefficients of fg.For h ∈ Z[x] we write f for the polynomial h mod p which lies in Fp[x]. Then 0 = fg =

f g 6= 0 because f 6= 0 6= g as they have content 1. �

Lemma 3.4.3 (Gauss) Let f, g ∈ Z[x]. Then c(fg) = c(f)c(g).

Proof. Write a = c(f), b = c(g). Then fa ,

gb ∈ Z[x]. But

fg = abf

a

g

b⇒ c(fg) = c

(abf

a

g

b

)= ab · c

(f

a

g

b

).

Now c(fa

)= c

( gb

)= 1 hence, by Lemma 3.4.2, c

(fagb

)= 1 and therefore c(fg) = ab. �

Theorem 3.4.4 Let f ∈ Z[x] and suppose that there exist g, h ∈ Q[x] with f = gh. Thenthere exist a, b ∈ Q such that ag, bh ∈ Z[x] and f = (ag)(bh).

In other words, every factorisation of f in Q[x] comes from a factorisation in Z[x].Proof. First assume that c(f) = 1. Let a, b ∈ Q be such that ag, bh ∈ Z[x] and c(ag) =c(bh) = 1. We have

abf = (ag)(bh) ∈ Z[x] and c(abf) = c(ag)c(bh) = 1.

Write ab = st with t ≥ 1; then all coefficients of f are divisible by t because s

tf ∈ Z[x].But c(f) = 1 so t = 1.

Now c(abf) = c(sf) = 1 hence s = ±1. Therefore (ag)(bh) = ±f . If this is −f then wereplace a with −a and obtain f = (ag)(bh).

If c(f) > 1, then write γ = c(f). We have that 1γ f = ( 1γ g)h and the content of 1

γ f is 1.

So by the above, there are a, b ∈ Q such that aγ g, bh lie in Z[x] and 1

γ f = aγ g · bh. It follows

that f = ag · bh. �

So in order to factorise f ∈ Q[x] we can make some reductions


- assume f ∈ Z[x] (otherwise we multiply by an s ∈ Z);

- the problem does not change if we look for factors in Z[x] (by Theorem 3.4.4);

- assume that f is square-free; otherwise we write f = g2h and then f ′ = 2gg′h + g2h′ so gdivides gcd(f, f ′); so we can factorise gcd(f, f ′) and f

gcd(f,f ′) .

Idea. We factorise f mod p, p a prime, and we “lift” the factors to elements of Z[x]. Thisprocess is called Hensel lifting.

3.4.1 Hensel lifting

Kurt Hensel (1861 - 1941)

invented p-adic numbers. The next theorem shows that a factorisation of a polynomialmodulo p leads to a p-adic factorisation.

Theorem 3.4.5 (Hensel) Let f ∈ Z[x] and p a prime, not dividing the leading coefficientof f . Let g, h ∈ Z[x] be such that

- deg(g) + deg(h) = deg(f);

- gcd(g, h) = 1 mod p;

- f = gh mod pk for a certain integer k > 0.

Then there exist u, v ∈ Z[x] with deg u < deg g, deg v ≤ deg h; and after setting g = g + pku,h = h+ pkv, we have deg(h) = deg h, and

f = gh mod pk+1.

Moreover, the u and v with these properties are uniquely determined modulo p.

Proof. Set g = g + pku, h = h+ pkv for certain u, v ∈ Z[x]. Then

f − gh = f − gh− pkvg − pkuh− p2kuv

and this has to be 0 modulo pk+1.Observe that f − gh is divisible by pk.So we want u, v such that

f − gh

pk− vg − uh = 0 mod p.

Set e = f−ghpk

.


We know that gcd(g, h) = 1 mod p. So there exist a, b ∈ Z[x] with ag + bh = 1 mod p.Hence eag + ebh = e mod p.

So we could take v = ea and u = eb but this can increase the degree. The trick is to firstadjust eb. Write eb = qg + r with deg(r) < deg(g). Then

eag + (qg + r)h = e mod p ⇔ (ea+ qh)g + rh = e mod p.

Now we try v = ea + qh mod p and u = r mod p. Of course, we are only interested in uand v modulo p.

With this choice we have f = gh mod pk+1 and deg(u) < deg(g). We need to check thedegree of v.

Since e = f−ghpk

we get deg(e) ≤ deg(f). Moreover, uh + vg = e mod p and deg(uh) <

deg(f) because deg(u) < deg(g). Hence deg(vg mod p) ≤ deg(f), and therefore

deg(v mod p) ≤ deg(h).

It also follows that deg(h) ≤ deg(h). However, if this inequality is strict then f = gh mod pk+1

implies that p divides the leading coefficient of f , contrary to the assumption on p. Hencedeg(h) = deg(h).

In order to show uniqueness, let u0, v0 ∈ Z[x] have the same properties. Then v0g+u0h =vg + uh mod p, or

(u0 − u)h = (v − v0)g mod p.

Since g, h are coprime modulo p this implies that g divides u0−u mod p. But that is impossi-ble because of the degrees; hence u0−u = 0 mod p. From that we also get v−v0 = 0 mod p. �

Remark 3.4.6 Note that the g, h in the conclusion of the preceding theorem satisfy thesame properties as g and h, except that k has changed to k + 1. So we can continue andobtain a factorisation mod pk+2, pk+3, . . .. In the limit this then yields a p-adic factorisation.

The proof of the theorem also gives a method for constructing g, h. One computes

- e = f−ghpk

;

- a, b with ag + bh = 1 mod p (extended euclidean algorithm);

- q, r with eb = qg + r and deg(r) < deg(g) (division with remainder);

- u = r mod p and v = ea+ qh mod p.

Then g = g + pku e h = h+ pkv.

Example 3.4.7 Let f = x4 + 2x3 − 3x2 − 4x− 1, g = x2 + 1 and h = x2 + 2x+ 2. We have

gh = x4 + 2x3 + 3x2 + 2x+ 2 = f mod 3

hence

e =f − gh

3= −2x2 − 2x− 1 = x2 + x+ 2 mod 3.


We do all computations modulo p because we are interested in u and v only modulo p. Inparticular e, a, b, q, v can be computed modulo p. We compute (everything modulo 3):

h = x2 + 2x+ 2 = 1 · h + 0 · gg = x2 + 1 = 0 · h + 1 · g

2x+ 1 = h − g2x2 + x = xh − xgx+ 1 = xh + (1− x)g

2 = (x+ 1)h − xg1 = (2x+ 2)h + xg.

Hence a = x, b = 2x+ 2 modulo 3. Therefore, modulo 3,

eb = (x2 + x+ 2)(2x + 2) = 2x3 + x2 + 1 = (2x+ 1)g + x = qg + r.

So u = r = x and

v = ea+ qh = (x2 + x+ 2)x+ (2x+ 1)(x2 + 2x+ 2) = 3x3 + 6x2 + 8x+ 2

= 2x+ 2 mod 3.

We see that deg(v) < deg(h) mod p but it is not guaranteed that v has degree ≤ deg(h)without the modulo p operation.

Now

g1 = g + 3u = x2 + 3x+ 1

h1 = h+ 3(2x+ 2) = x2 + 8x+ 8.

Indeed we havef − g1h1 = −9x3 − 36x2 − 36x− 9 = 0 mod 9.

For k = 2 we get

e =f − g1h1

9= −x3 − 4x2 − 4x− 1 = 2x3 + 2x2 + 2x+ 2 mod 3.

Since g1 = g mod p and h1 = h mod p the same a and b of the previous step can also be usedhere. So

eb = x4 + 2x3 + 2x2 + 2x+ 1 = (x2 + 2x+ 1)g1 + 0 = qg1 + r.

We get u = r = 0 and

v = ea+ qh1 = (2x3 + 2x2 + 2x+ 2)x+ (x2 + 2x+ 1)(x2 + 8x+ 8)

= 2x+ 2 mod 3.

Now

g2 = g1 + 9u = g1 = x2 + 3x+ 1

h2 = h1 + 9(2x + 2) = x2 + 26x+ 26.

And f = g2h2 mod 27. Continuing we find

g3 = x2 + 3x+ 1

h3 = x2 + 80x+ 80.

And f = g3h3 mod 81, and so on.


So, starting with a factorisation modulo p, we find factorisations modulo pk, for any kwe want. Now we describe how we can get the factorisation in Z[x] from the factorisationmodulo pk, when k is big enough.

Definition 3.4.8 Let f =∑n

i=0 fixi ∈ C[x]. The norm of f is

||f || =

√√√√n∑

i=0

|fi|2.

Lemma 3.4.9 Let h ∈ C[x], a ∈ C. Then

||(x− a)h|| = |a|||(x − a−1)h||.

Proof. Write h =∑m

i=0 hixi. We have

(x− a)h = hmxm+1 + (hm−1 − ahm)xm + . . . + (h0 − ah1)x− ah0

=m+1∑

i=0

(hi−1 − ahi)xi

where we set h−1 = hm+1 = 0.In general we have

|u− v|2 = (u− v)(u − v) = uu− uv − uv + vv

= |u|2 − uv − uv + |v|2.

Hence

||(x− a)h||2 =

m+1∑

i=0

|hi−1 − ahi|2

=∑

(|hi−1|2 − ahi−1hi − ahi−1hi + |ahi|2)

=∑

(|hi|2 − ahi−1hi − ahi−1hi + |ahi−1|2) =∑

|ahi−1 − hi|2.

Because∑ |hi−1|2 =

∑ |hi|2 and

|ahi|2 = |a|2|hi|2 = |ahi|2.

Therefore

||(x− a)h||2 = ||(ax− 1)h||2

= |a|2||(x− a−1)h||2

= |a|2||(x− a−1)h||2.

�

Theorem 3.4.10 (Landau-Mignotte) Let f ∈ Z[x] and g ∈ Z[x] be a factor of f , deg(g) =m. Write g =

∑mi=0 gix

i. Then

|gi| ≤(m

i

)||f ||.


Proof. Let b1, . . . , bs and a1, . . . , at in C be the zeros of f “with multiplicity” (so a zero ofmultiplicity k appears k times), where |bi| > 1 and |ai| ≤ 1.

Write f =∑n

i=0 fixi. Then

f = fn

s∏

i=1

(x− bi)

t∏

j=1

(x− aj)

so by Lemma 3.4.9

||f || = ||fns∏

i=1

(x− bi)

t∏

j=1

(x− aj)|| = |a1 · · · at|||fnt∏

j=1

(x− a−1j )

s∏

i=1

(x− bi)||.

Write h =∑

i hixi, then ||h|| ≥ |h0| since ||h||2 =

∑ |hi|2. Hence

||f || ≥ |a1 · · · at||fn||a−11 · · · a−1

t ||b1 · · · bs|.

For z ∈ C, |zz−1| = 1, so we get

||f || ≥ |fnb1 · · · bs|.Now let γ1, . . . , γm be the zeros of g. Then g = gm(x− γ1) · · · (x− γm), whence

gi = (−1)igmσm−i(γ1, . . . , γm)

where σi(x1, . . . , xm) is the i-th elementary symmetric polynomial in x1, . . . , xm; that is

σi(x1, . . . , xm) =∑

1≤j1<j2<...<ji≤m

xj1 · · · xji .

We have that σi(x1, . . . , xm) is a sum of(mi

)monomials of degree i.

We assume that the γi are ordered in such a way that |γ1| ≥ |γ2| ≥ . . . ≥ |γm|. Then

|σi(γ1, . . . , γm)| ≤(m

i

)|γ1 · · · γi|

≤(m

i

)|b1 · · · bs|

≤(m

i

) ||f |||fn|

whence

|gi| ≤ |gm|(

m

m− i

) ||f |||fn|

= |gm|(m

i

) ||f |||fn|

.

We have |gm| ≤ |fn| because gm divides fn. Therefore

|gi| ≤(m

i

)||f ||.

�


Lemma 3.4.11 Let g ∈ Z[x], g =∑m

i=0 gixi, and B > 0 with |gi| < B. Let M be an integer

with M > 2B and write g modM =∑m

i=0 gixi where gi ∈

(−M

2 ,M2

]. Then

g =m∑

i=0

gixi

in other words: g = g modM and gi = gi.

Proof. Suppose that gi 6= gi. Then gi − gi = kM with |k| ≥ 1. But |gi| ≤ M2 , so

|gi| = |kM + gi| ≥M

2> B

but this is a contradiction. �

Based on these results we have the following procedure for factorising a polynomial f inZ[x]. We assume that f is square-free. We choose a prime p such that p does not dividethe leading coefficient of f , and such that f mod p is also square-free. For simplicity first weassume that f mod p is the product of at most two irreducible factors.

- If f mod p is irreducible then f ∈ Z[x] is irreducible, and we stop.- Otherwise f mod p = (g mod p)(h mod p), where g mod p and h mod p in Fp[x] are

irreducible and distinct. (These factors can be found using Berlekamp’s algorithm.)- By Hensel lifting we find gk and hk such that f = gkhk mod pk.- Using the theorem of Landau-Mignotte we find a B so that the coefficients of a factor

of f have absolute value < B.Let M = pk0 with k0 such that M > 2B. Then we find gi, hi such that

g := gk0 modM =∑

gixi, gi ∈

(−M

2,M

2

]

h := hk0 modM =∑

hjxj, hi ∈

(−M

2,M

2

].

Then f = gh is the factorisation of f or f is irreducible. Indeed, if f is not irreduciblethen f = gh, for certain g, h ∈ Z[x]. (We know that f has at most two factors over Z,as this is the case modulo p.) Now f mod pk0 = gk0hk0 mod pk0 = (g mod pk0)(h mod pk0).However, by Theorem 3.4.5, the factorisation f mod pk0 = gk0hk0 mod pk0 is unique. Henceg mod pk0 = gk0 mod pk0 = g mod pk0 and h mod pk0 = hk0 mod pk0 = h mod pk0 (or theother way round, of course). So by Lemma 3.4.11, g = g and h = h.

Example 3.4.12 As in Example 3.4.7, let f = x4 + 2x3 − 3x2 − 4x + 1. Then ||f ||2 =1 + 4 + 9 + 16 + 1 = 31. Let α2x

2 + α1x+ α0 be a factor of f . Then

|α2| ≤(2

2

)√31, |α1| ≤

(2

1

)√31, |α0| ≤

(2

0

)√31

so |αi| ≤ 2√31. Hence |αi| ≤ 11, since αi ∈ Z, so we can take B = 11.

We know that f = g3h3 mod 27 where g3 = x2 + 3x+ 1 and h3 = x2 + 26x+ 26.We choose M = 27 > 2B = 22. Now

g3 modM = x2 + 3x+ 1

h3 modM = x2 − x− 1

and f = (x2 + 3x+ 1)(x2 − x− 1); so we have factorised f .


3.4.2 Hensel lifting for more factors

Given f ∈ Z[x] and f1, . . . , fr ∈ Z[x], and p a prime such that fi, fj are coprime modulo p.We assume that deg(f1) + . . .+ deg(fr) = deg(f), f = f1 · · · fr mod p.

We compute f1, . . . , fr ∈ Z[x] with fi = fi mod p and f = f1 · · · fr mod pk for a certaink.

1) Let m =⌈r2

⌉and g = f1 · · · fm, h = fm+1 · · · fr.

2) By Hensel lifting we compute g, h ∈ Z[x] with g = g mod p, h = h mod p and f =gh mod pk.

3) Recursively we compute f1, . . . , fr with fi = fi mod p, g = f1 · · · fm mod pk, h = fm+1 · · · fr modpk.

4) f = f1 · · · fr mod pk.

The algorithm

Now we describe a procedure for factorising a square-free f ∈ Z[x].

1) We choose a prime p such that f mod p is square-free, and p does not divide the leadingcoefficient of f .

2) With Landau-Mignotte we compute a B such that

|coefficient of a factor of f | ≤ B

and we choose k such that M = pk > 2B.

3) Let f1, . . . , fr be the irreducible factors of f mod p (obtained with Berlekamp’s algorithm).

4) By Hensel lifting we get f1, . . . , fr ∈ Z[x] such that f = f1 · · · fr mod pk and fi = fi mod p.

5) For all S ⊂ {1, . . . , r} we compute

gS =∏

i∈Sfi and hS =

∏

i 6∈Sfi.

We write the coefficients of gS and hS modulo M in(−M

2 ,M2

].

If f = gShS then we have found a factorisation. If for all S, fS 6= gShS then f is irreducible.

Example 3.4.13 (Swinnerton-Dyer polynomials) Let p1 = 2, p2 = 3, . . . , pn be the firstn primes, and consider the field

Fn = Q(√p1, . . . ,

√pn).

Let fn be the minimal polynomial of αn =√p1 + · · · +√

pn. Using Galois theory one showsthat fn has degree 2n and the roots of fn are

ǫ1√p1 + · · ·+ ǫn

√pn

3.5 Exercises 75

where ǫi ∈ {−1, 1}. Using a bit of algebraic number theory one sees that fn ∈ Z[x] (the√pi lie in the ring of integers of Fn, hence so does αn; therefore fn ∈ Z[x]). Now let p be a

prime, then all polynomials x2 − pi have their roots in the quadratic extension Fp2 of Fp. Itfollows that fn mod p factorises into linear factors over Fp2 . Hence over Fp, it factorises intolinear or quadratic factors. So fn mod p has at least 2n−1 factors over Fp. Now fn, beingthe minimal polynomial of αn, is irreducible in Q[x]. But in order to show that using thealgorithm outlined in this section one needs to inspect at least 22

n−1

subsets S. So we seethat at least for some polynomials this algorithm is not without its drawbacks.

3.5 Exercises

1. Prove that x4 + x+ 1 ∈ F2[x] is irreducible.

2. Factorise x7 + 1 ∈ F2[x] and x4 + x + 1 ∈ F3[x]. (In coding theory, the factorisation

of x7 + 1 ∈ F2[x] implies that there are 8 = 23 cyclic codes of length 7 over F2. Thefactorisation is used to find their generator polynomials; see J. H. van Lint, Introductionto Coding Theory, Chapter 6. )

3. Prove that x5 + x3 + 1 ∈ Q[x] is irreducible by factorising it modulo a suitably chosenprime.

4. Let f = x4 + 5x3 + 6x2 − x − 1 and g = x2 + 1, h = x2 + 2x + 2. Then g mod 3and h mod 3 are irreducible in F3[x] and f = gh mod 3. Let gk, hk be the polynomialsobtained from g, h by Hensel lifting. (So g1 = g, h1 = h, and f = gkhk mod 3k.)

(a) Compute gk, hk for k = 2, 3.

(b) Prove that gk = x2 + 3x+ 1 and hk = x2 + 2x+ 3k − 1 for k ≥ 2.

(c) Show that the coefficients of a factor of f are ≤ 24 in absolute value. Factorise f .

5. Let f = x5+2x3+2x2+x+1. Factorise f mod 3, and prove that f ∈ Q[x] is irreducible.

6. In this exercise we show that f = x4 + 1 ∈ Q[x] is irreducible, but f mod p factorisesmodulo every prime p.

(a) Factorise f mod 2 (hint: it is easy to find a root of f).

(b) Let p be an odd prime. Let V be the space of v ∈ Fp[x]/〈f〉 such that vp = v mod f .Compute a basis of V , treating the cases p = 1+4k, k even and odd, and p = 3+4k,k even and odd, separately. Concluse that f mod p factorises for all primes p.

(c) Factorise f mod 5.

(d) By Hensel lifting find g, h ∈ Z[x] with f = gh mod 125.

(e) Find a bound on the coefficients of a possible factor of f in Z[x] (Landau-Mignotte).Prove that f is irreducible.

Chapter 4

Lattice Basis Reduction

Here we describe the LLL algorithm, named after its inventors, A.K. Lenstra, H. W. LenstraJr. and L. Lovasz (Factoring polynomials with rational coefficients, Mathematisch Annalen,261, 515-534 (1982)).

Notation: we work in the real vector space Rn. For an element x ∈ Rn, its i-th coordinateis written x(i), so x = (x(1), . . . , x(n)). The standard inner product, for x, y ∈ Rn, is(x, y) =

∑ni=1 x(i)y(i). The vectors x, y ∈ Rn are said to be orthogonal if (x, y) = 0. The

norm of an x ∈ Rn is ‖x‖ =√

(x, x). For x1, . . . , xk ∈ Rn we denote their linear span by〈x1, . . . , xk〉L.

4.1 Lattices

A lattice in Rn is the Z-span of a basis of it. More in detail: a lattice in Rn is a setL = {m1x1 + · · · + mnxn | mi ∈ Z}, where x1, . . . , xn is a basis of Rn. One of the mainproblems concerning lattices is that they can contain rather “short” vectors, although a basismay be formed by rather “long” vectors. The ability to find short vectors in a lattice hasmany applications.

Here we write elements of Rn as row vectors. A basis x1, . . . , xn of Rn corresponds to thematrix X whose rows are the xi. Now let L be as above, and let Y be a second basis of L.Then there is an n × n-integral matrix C with det(C) = ±1, such that Y = CX (the proofof this is left as an exercise). Conversely, if C is an n × n-matrix with determinant ±1 andY = CX, then the rows of Y , y1, . . . , yn also form a basis of L.

Example 4.1.1 Let L ⊂ R3 be the lattice spanned by

x1 = (4629703, 1594165, 2781628), x2 = (−1641,−565,−986), x3 = (37652, 12964, 22623).

78 Lattice Basis Reduction

Let X be the matrix with rows x1, x2, x3, and

A =

1579935 −2846 −53628−560 1 1912849 −23 −436

, Y =

3 1 21 −5 12 0 7

.

Then det(A) = 1 and X = AY . So the rows of Y also form a basis of L. The basis X is “bad”since it consists of vectors of large length. With respect to X, the basis Y is very “good”.The question is: given a basis like X, how do we find a “good” basis? Here it is even notimmediately clear how we can decide whether a given other basis is “good” (maybe it is just“better”, but not yet “good”). The LLL algorithm succeeds in finding a “reasonably good”basis, and it also quantifies what is meant by “reasonably good”. For example, using the LLLalgorithm on the basis X above, yields the basis

3 1 2−1 −1 51 −5 1

.

4.2 Properties of Gram-Schmidt orthogonalisation

Let U ⊂ Rn be a subspace. Then U⊥ = {x ∈ Rn | (x, u) = 0 for all u ∈ U} is called theorthogonal complement of U . Every x ∈ Rn can uniquely be written as x = u + u⊥, whereu ∈ U , u⊥ ∈ U⊥. Indeed, U ∩ U⊥ = 0, and dimU + dimU⊥ = n, so a basis of Rn can beformed by concatenating a basis of U and a basis of U⊥. The vectors u and u⊥ are called theprojection of x on U and on U⊥ respectively.

Proposition 4.2.1 Let x1, . . . , xn be a basis of Rn. For 1 ≤ j ≤ n let x∗j be the projection

of xj on 〈x1, . . . , xj−1〉⊥L (so x∗1 = x1). Then

1. 〈x1, . . . , xj〉L = 〈x∗1, . . . , x∗j〉L for 1 ≤ j ≤ n.

2. (x∗i , x∗j ) = 0 for 1 ≤ i < j ≤ n.

3.

x∗j = xj −j−1∑

i=1

µjix∗i , where µji =

(xj ,x∗

i )(x∗

i ,x∗

i ). (4.1)

Proof.

1. Here we use induction on j, the statement for j = 1 being trivial. Let U = 〈x1, . . . , xj〉L.Then xj+1 = u + x∗j+1 for a u ∈ U . So 〈x1, . . . , xj , xj+1〉L = 〈x1, . . . , xj , x∗j+1〉L =〈x∗1, . . . , x∗j , x∗j+1〉L (where the last equality follows from the induction hypothesis).

2. This follows immediately from 1. along with the definition of x∗j .

3. From 1. and the definition of x∗j it follows that there are µji with x∗j = xj−

∑j−1i=1 µjix

∗i .

Let 1 ≤ i0 ≤ j− 1, then from 2. we have 0 = (x∗i0 , x∗j ) = (x∗i0 , xj)−µj,i0(x

∗i0, x∗i0). So we

have 3.

�

4.2 Properties of Gram-Schmidt orthogonalisation 79

Definition 4.2.2 The basis x∗1, . . . , x∗n defined in Proposition 4.2.1 is called the Gram-Schmidt

orthogonalisation of the basis x1, . . . , xn. The µji are called the Gram-Schmidt coefficients(GS-coefficients, for short).

For the rest of this section we let x1, . . . , xn be a basis of Rn, with Gram-Schmidt or-thogonalisation x∗1, . . . , x

∗n. By µji we denote the GS-coefficients, for 1 ≤ i < j ≤ n. For

convenience we set µjj = 1 for all j and µji = 0 if j < i. Also, for 1 ≤ k ≤ n we let Xk be thek × n-matrix with rows x1, . . . , xk. Similarly, we let X∗

k be the matrix with rows x∗1, . . . , x∗k.

By Mk we denote the k × k-matrix whose (j, i)-th entry is µji. Then (4.1) translates to

Xk =MkX∗k . (4.2)

Also we consider the k×k-matrix Gk whose (i, j)-entry is (xi, xj). It is called the Gram matrixof x1, . . . , xk. We have that Gk is symmetric, and Gk = XkX

Tk . The k-th Gram determinant

is dk = det(Gk).

Lemma 4.2.3 dk = ‖x∗1‖2 · · · ‖x∗k‖2.

Proof. Using (4.2) and det(Mk) = 1, we compute: dk = det(Gk) = det(XkXTk ) =

det((MkX∗k)(MkX

∗k)

T ) = det(Mk(X∗k(X

∗k)

T )MTk ) = det(X∗

k (X∗k)

T ) = ‖x∗1‖2 · · · ‖x∗k‖2 (sincethe x∗i are orthogonal). �

Lemma 4.2.4 Let j be an integer with 1 ≤ j < n. Define xi = xi if i 6= j, j + 1, and xj =xj+1, xj+1 = xj . Let x∗1, . . . , x

∗n denote the Gram-Schmidt orthogonalisation of x1, . . . , xn.

Then x∗i = x∗i if i 6= j, j + 1, x∗j = x∗j+1 + µj+1,jx∗j , and

x∗j+1 =‖x∗j+1‖2‖x∗j‖2

x∗j − µj+1,j

‖x∗j‖2‖x∗j‖2

x∗j+1.

Proof. If i 6= j, j + 1 then 〈x1, . . . , xi−1〉L = 〈x1, . . . , xi−1〉L, and xi = xi, so then the resultfollows from the definition of x∗i and x∗i . For i = j we compute

x∗j = xj −j−1∑

i=1

(xj , x∗i )

(x∗i , x∗i )x∗i

= xj+1 −j−1∑

i=1

(xj+1, x∗i )

(x∗i , x∗i )

x∗i

= xj+1 −j−1∑

i=1

µj+1,ix∗i

= xj+1 −j∑

i=1

µj+1,ix∗i + µj+1,jx

∗j

= x∗j+1 + µj+1,jx∗j .

Now we derive some consequences of this. First of all, since the x∗i are orthogonal,

‖x∗j‖2 = ‖x∗j+1‖2 + µ2j+1,j‖x∗j‖2. (4.3)


Secondly (xj , x∗j ) = (xj , x

∗j+1) + µj+1,j(xj , x

∗j ) = µj+1,j(xj , x

∗j ) = µj+1,j

∑ji=1 µi,j(x

∗i , x

∗j ) =

µj+1,j(x∗j , x

∗j ), so

(xj , x∗j ) = µj+1,j‖x∗j‖2. (4.4)

And now:

x∗j+1 = xj+1 −j∑

i=1

(xj+1, x∗i )

(x∗i , x∗i )

x∗i

= xj −j∑

i=1

(xj , x∗i )

(x∗i , x∗i )x∗i (as xj+1 = xj)

= xj −(xj, x

∗j )

(x∗j , x∗j )x∗j (as, for i < j, x∗i = x∗i , whence (xj , x

∗i ) = 0)

= xj −µj+1,j‖x∗j‖2

‖x∗j‖2(x∗j+1 + µj+1,jx

∗j) (by (4.4), and result for x∗j)

=‖x∗j+1‖2‖x∗j‖2

x∗j − µj+1,j

‖x∗j‖2‖x∗j‖2

x∗j+1 (by (4.3)).

�

Lemma 4.2.5 Let y = m1x1+ · · ·+mnxn, where mi ∈ Z. Then ‖y‖ ≥ min(‖x∗1‖, . . . , ‖x∗n‖).Proof. Let k be maximal with mk 6= 0. Then y =

∑kj=1mjxj =

∑kj=1mj

∑ji=1 µjix

∗i =

∑ki=1

∑kj=imjµjix

∗i = mkx

∗k +

∑k−1i=1 rix

∗i . So since the x∗i are orthogonal, ‖y‖2 = m2

k‖x∗k‖2 +∑k−1i=1 r

2i ‖x∗i ‖2 ≥ ‖x∗k‖2. �

4.3 Reduced lattice bases

Throughout this section we fix α ∈ R with 14 < α < 1 and set β = 4

4α−1 , so43 < β <∞.

Definition 4.3.1 Let x1, . . . , xn ∈ Rn be a basis of a lattice L, with Gram-Schmidt orthog-onalisation x∗1, . . . , x

∗n, and corresponding GS-coefficients µji. This basis is called α-reduced

if

1. |µji| ≤ 12 , for 1 ≤ i < j ≤ n,

2. ‖x∗i + µi,i−1x∗i−1‖2 ≥ α‖x∗i−1‖2 for 2 ≤ i ≤ n.

Concerning the second condition compare Lemma 4.2.4. By interchanging xi−1, xi we geta new x∗i−1, and the second condition says that the length of the new x∗i−1 is not much smallerthan the length of the old x∗i−1

The next proposition says that the first vector in an α-reduced basis is “quite short”, andit also quantifies this notion.

Proposition 4.3.2 Let x1, . . . , xn be an α-reduced basis of a lattice L ⊂ Rn. Let y be any

nonzero element of L. Then ‖x1‖ ≤ βn−12 ‖y‖.

4.3 Reduced lattice bases 81

Proof. Using first the second and then the first condition of Definition 4.3.1 we get

‖x∗i ‖2 ≥ (α− µ2i,i−1)‖x∗i−1‖2 ≥ (α− 1

4)‖x∗i−1‖2 =

1

β‖x∗i−1‖2.

But x∗1 = x1, so this yields ‖x1‖2 = ‖x∗1‖2 ≤ β‖x∗2‖2 ≤ β2‖x∗3‖2 ≤ · · · ≤ βn−1‖x∗n‖2.So ‖x∗i ‖2 ≥ β−i+1‖x1‖2. Finally, by Lemma 4.2.5 we see ‖y‖ ≥ min(‖x∗1‖, . . . , ‖x∗n‖) ≥β−n+1

2 ‖x1‖. �

Next we prove an extension of this proposition, bounding the norm of all elements of anα-reduced basis. For this we first need a lemma.

Lemma 4.3.3 Let x1, . . . , xn be an α-reduced basis of a lattice L ⊂ Rn. Then ‖xi‖2 ≤βj−1‖x∗j‖2, for 1 ≤ i ≤ j ≤ n.

Proof. As seen in the proof of Proposition 4.3.2 we have ‖x∗j−1‖2 ≤ β‖x∗j‖2. So ‖x∗i ‖2 ≤βj−i‖x∗j‖2.

From (4.1) we get xj = x∗j +∑j−1

i=1 µjix∗i . So, since the x

∗i are orthogonal: ‖xj‖2 = ‖x∗j‖2+∑j−1

i=1 µ2ji‖x∗i ‖2. Putting these things together, and using the first condition of Definition 4.3.1,

we get

‖xj‖2 ≤ ‖x∗j‖2 +j−1∑

i=1

1

4βj−i‖x∗j‖2 =

(1 +

1

4

j−1∑

i=1

βj−i

)‖x∗j‖2 =

(1 +

1

4

βj − β

β − 1

)‖x∗j‖2.

Now we claim that (1 + 14βj−ββ−1 ) ≤ βj−1. Suppose that this claim is proved. Then ‖xj‖2 ≤

βj−1‖x∗j‖2, whence ‖xi‖2 ≤ βi−1‖x∗i ‖2 ≤ βj−1‖x∗j‖2.In order to prove the claim, write u(j) = 1 + 1

4βj−ββ−1 . We proceed by induction on j. We

have u(1) = 1 ≤ 1 = β0. For the induction step, suppose that u(j) ≤ βj−1, for some j ≥ 1.Then u(j + 1) ≤ βu(j): indeed, after multiplying both sides by 4(β − 1) (which is positive),and some manipulation, we get that this is equivalent to (β − 1)(3β − 4) ≥ 0, which holds.So u(j + 1) ≤ βu(j) ≤ βj . �

Theorem 4.3.4 Let x1, . . . , xn be an α-reduced basis of a lattice L ⊂ Rn. Let m ≤ n and lety1, . . . , ym ∈ L be linearly independent. Then for 1 ≤ i ≤ m:

‖xi‖ ≤ βn−12 max{‖y1‖, . . . , ‖ym‖}.

Proof. Write yi =∑n

j=1 rijxj, rij ∈ Z. For 1 ≤ i ≤ m let ki denote the largest index j forwhich rij 6= 0. Then

yi =

ki∑

j=1

rijxj =

ki∑

j=1

rij

j∑

l=1

µjlx∗l =

ki∑

j=1

j∑

l=1

rijµjlx∗l .

This is equal to ri,kix∗ki+ νi,ki−1x

∗ki−1 + · · · + νi,1x

∗1, with νi,l ∈ Q. So since ri,ki is a nonzero

integer we see that ‖yi‖2 ≥ ‖x∗ki‖2.


After possibly reordering the yi we may assume that k1 ≤ k2 ≤ · · · ≤ km. Suppose thatki < i for some i. Then y1, . . . , yi all lie in the span of x1, . . . , xi−1. But that means thatthey cannot be linearly independent. Hence ki ≥ i for all i. So we can take j = ki in Lemma4.3.3, and get

‖xi‖2 ≤ βki−1‖x∗ki‖2 ≤ βn−1‖x∗ki‖

2 ≤ βn−1‖yi‖2.

So since ‖yi‖2 ≤ max{‖y1‖2, . . . , ‖ym‖2}, this completes the proof. �

4.4 The LLL algorithm

Now we turn to an algorithm for computing an α-reduced basis of a lattice L ⊂ Rn. Thealgorithm works with several related objects, which together we call the state of the algorithm.In detail, a state of the algorithm is a quadruple S = (X,X∗,M, γ∗), where

• X is an n× n-matrix whose rows, denoted x1, . . . , xn, form a basis of L,

• the rows of X∗ are the elements of the Gram-Schmidt orthogonalisation, x∗1, . . . , x∗n,

• the matrix M contains the GS-coefficients, so M(j, i) = µji,

• the vector γ∗ = (γ∗1 , . . . , γ∗n) contains the squared norms of the x∗i , i.e., γ

∗i = (x∗i , x

∗i ).

It is clear that the first component, X, determines all other components. If in the algorithmwe write, for example, x∗i then this is meant relative to the current state.

We recall the definition of the k-th Gram determinant, dk = det(Gk), where Gk = XkXTk .

In the algorithm the state is changed by means of two basic operations: Reduce(k, l) andExchange(k). First we briefly describe them.

4.4.1 Reduce(k, l)

Here we have k > l, and

• if |µk,l| ≤ 12 then this procedure does nothing;

• otherwise we let ν be the integer closest to µk,l (this is defined as ν = ⌈µk,l − 12⌉, so if

µk,l = m+ ε, with 0 ≤ ε < 1 then ν = m if 0 ≤ ε ≤ 12 and ν = m+ 1 otherwise), and

replace xk by xk − νxl, and all other xi are left unchanged.

Lemma 4.4.1 Let (X,X∗,M, γ∗) be a state and apply Reduce(k, l), where k > l. Let(Y, Y ∗, N, δ∗) be the state afterwards. Write νi,j = N(i, j). Define the n × n-matrix E byE(i, i) = 1, 1 ≤ i ≤ n, E(k, l) = −ν, and all other entries are 0. Then

1. Y = EX, N = EM , Y ∗ = X∗ and δ∗ = γ∗,

2. νi,j = µi,j if i 6= k, or i = k and j > l, and |νk,l| ≤ 12 ,

3. write di = det(XiXTi ), d

′i = det(YiY

Ti ), then di = d′i for all i.

4.4 The LLL algorithm 83

Proof. Let A be the n×n-matrix with rows a1, . . . , an. Then the k-th row of EA is ak−νal,and the i-th row (i 6= k) of EA is ai. This implies Y = EX.

Since l < k we have that 〈x1, . . . , xi〉L = 〈y1, . . . , yi〉L for all i. So, as x∗i is the projectionof xi onto the orthogonal complement of 〈x1, . . . , xi−1〉L we get y∗i = x∗i for all i. In otherwords, Y ∗ = X∗. This also implies (EM)X∗ = E(MX∗) = EX = Y = NY ∗ = NX∗, andsince X∗ is invertible, N = EM .

For the second statement, note that, if i 6= k, then the i-th row of N is equal to the i-throw of M , whereas the k-th row of N is equal to the k-th row of M minus ν times the l-throw of M , i.e., νk,j = µk,j−νµl,j. But if j > l then µl,j = 0, whence νk,j = µk,j. Furthermore,νk,l = µk,l − νµl,l = µk,l − ν, as µl,l = 1. By the definition of ν it now follows that |νk,l| ≤ 1

2 .

By Lemma 4.2.3, di = ‖x∗1‖2 · · · ‖x∗i ‖2 = ‖y∗1‖2 · · · ‖y∗i ‖2 = d′i. �

We conclude that updating the state after a call to Reduce(k, l) is straightforward. More-over, given a lattice L with basis x1, . . . , xn, it is straightforward to obtain a new basis of Lsatisfying the first condition of Definition 4.3.1. Indeed, we do the following

1. Let X be the matrix with rows x1, . . . , xn, and compute the corresponding state.

2. For k = 2, . . . , n and l = k − 1, k − 2, . . . , 1 do Reduce(k, l).

However, the resulting basis does not necessarily satisfy the second condition of Definition4.3.1.

4.4.2 Exchange(k)

Here we assume k > 1; this just swaps xk−1 and xk.

Lemma 4.4.2 Let (X,X∗,M, γ∗) be a state such that γ∗k < (α − µ2k,k−1)γ∗k−1, where k > 1,

and apply Exchange(k). Let (Y, Y ∗, N, δ∗) be the state afterwards. Then

1. y∗i = x∗i for i 6= k − 1, k,

2. ‖y∗k−1‖2 < α‖x∗k−1‖2,

3. ‖y∗k‖ < ‖x∗k−1‖,

4. write di = det(XiXTi ), d

′i = det(YiY

Ti ), then di = d′i for all i, except i = k − 1 and

d′k−1 ≤ αdk−1.

Proof. The first statement is contained in Lemma 4.2.4. By the same lemma, y∗k−1 =x∗k+µk,k−1x

∗k−1. So ‖y∗k−1‖2 = ‖x∗k‖2+µ2k,k−1‖x∗k−1‖2 = γ∗k+µ

2k,k−1γ

∗k−1 < αγ∗k−1 = α‖x∗k−1‖2.

Write U = 〈x1, . . . , xk−2〉L, and V = 〈x1, . . . , xk−2, xk〉L. Now, xk−1 = x∗k−1 + u, where

u =∑k−2

j=1 µk−1,jx∗j , and hence u ∈ U by Proposition 4.2.1. By the same proposition, y∗k is

the projection of xk−1 on V ⊥. But since U ⊂ V , it follows that y∗k is the projection of x∗k−1

on V ⊥. This implies the third statement.

If i < k − 1 then Xi = Yi, so di = d′i. Let i > k − 1. Then Yi is obtained from Xi byexchanging the rows k− 1 and k. Let π be the permutation (k− 1, k). Write XiX

Ti = A and


YiYTi = B. Then B(s, t) = A(π(s), π(t)). Now using the Leibniz formula for determinants we

get

detB =∑

σ∈Si

ε(σ)i∏

s=1

B(s, σ(s))

=∑

σ∈Si

ε(σ)

i∏

s=1

A(π(s), πσ(s))

=∑

σ∈Si

ε(π−1σπ)

i∏

s=1

A(π(s), σπ(s))

=∑

σ∈Si

ε(σ)i∏

s=1

A(s, σ(s)) = det(A).

The statement for d′k−1 follows from 1. and 2. together with Lemma 4.2.3. �

We also see that updating the state after an application of Exchange(k) is not so straight-forward. Of course, it can be done by simply recomputing all the data from Y . But it is alsoobvious that many things can be filled in directly. See Exercise 1 for the details.

The idea for the algorithm for computing an α-reduced basis is now as follows. We saythat a basis x1, . . . , xn has property P (k) if

|µji| ≤ 12 , for 1 ≤ i < j ≤ k, and ‖x∗i + µi,i−1x

∗i−1‖2 ≥ α‖x∗i−1‖2 for 2 ≤ i ≤ k.

Note that any basis has P (1). Suppose we have a basis with P (k − 1). Then we couldcheck whether ‖x∗k + µk,k−1x

∗k−1‖2 ≥ α‖x∗k−1‖2, and if that holds we do Reduce(k, l) for

l = k− 1, k− 2, . . . , 1. (As seen in Lemma 4.4.1, this ensures that |µk,l| ≤ 12 .) If the condition

does not hold then we perform Exchange(k): that does not necessarily fix a condition, butit decreases the product of the Gram determinants, so we cannot run into this case infinitelyoften. There is only one problem with that: Reduce(k, k − 1) may destroy the condition‖x∗k + µk,k−1x

∗k−1‖2 ≥ α‖x∗k−1‖2. The trick now is to first do Reduce(k, k − 1), and then

check the condition.The algorithm for computing an α-reduced basis reads as follows.

Algorithm 4.4.3Given: a basis x1, . . . , xn ∈ Rn of the lattice L.We compute an α-reduced basis of L.

1. Let X be the matrix with rows x1, . . . , xn, and compute the corresponding state.

2. k := 2.

3. while k ≤ n do:

(a) Reduce(k, k − 1).

(b) If γ∗k ≥ (α − µ2k,k−1)γ∗k−1 then

i. for l = k − 2, k − 3, . . . , 1 do Reduce(k, l),

4.5 The knapsack cryptosystem 85

ii. k := k + 1.

else

i. Exchange(k),

ii. if k > 2 then k := k − 1.

Theorem 4.4.4 Suppose that the input basis vectors x1, . . . , xn have integer coordinates.Then Algorithm 4.4.3 terminates, and upon termination the state contains an α-reduced basis.

Proof. Let D = d1 · · · dn−1 be the product of the first n−1 Gram determinants. By Lemma4.2.3 this is a positive integer. However, after every call to Exchange(k) it decreases. Itfollows that Exchange(k) is called a finite number of times. This implies that the algorithmterminates, because every time the other part of the loop is entered, k is increased.

We claim that at the beginning of the loop in Step 3, when k = k0 is considered, P (k0−1)holds. This is certainly true initially as then k = 2. A call to Reduce(k0, l), does not changeanything with respect to P (k0 − 1). So if the first clause of the if statement is entered, thenafterwards P (k0 − 1) still holds, but also γ∗k0 ≥ (α − µ2k0,k0−1)γ

∗k0−1, (which is the same as

‖x∗k0 + µk0,k0−1x∗k0−1‖2 ≥ α‖x∗k0−1‖2 as the x∗i are orthogonal), and µk0,l ≤ 1

2 for 1 ≤ l < k0.We conclude that in that case, P (k0) holds.

If the second clause of the if statement is entered, then xk0 and xk0−1 are interchanged,and k gets the value k0 − 1. Since nothing has happened with x1, . . . , xk0−2, it follows thatP (k0 − 2) holds, which is the same as P (k − 1).

The conclusion is that upon termination P (n) holds, so the basis is α-reduced. �

4.5 The knapsack cryptosystem

In 1978 Merkle and Hellman proposed the use of the so-called knapsack problem as the basisof a public key cryptosystem (Hiding information and signatures in trapdoor knapsacks, IEEETrans. Inf. Th., 525-530). However in 1985, Lagarias and Odlyzko showed how to break thissystem using the LLL algorithm.

The knapsack problem amounts to the following. Let A = {a1, . . . , an} be a set of ndistinct positive integers, and s > 0 also an integer. The problem is to decide whether thereis an I ⊂ {1, . . . , n} such that ∑

i∈Iai = s.

(We can think of the ai as the sizes of different objects to be put in a knapsack of size s;the question is whether we can exactly fill our knapsack.) An equivalent way of formulatingthe problem is to ask whether there is a vector (x1, . . . , xn), with xi ∈ {0, 1}, such that∑n

i=1 xiai = s.It is known that knapsack problems are very hard to solve in general. However, in a

special case this is easy. The sequence a1, . . . , an is said to be superincreasing if aj >∑j−1

i=1 ai,i.e., if the j-th term is strictly bigger than the sum of the preceding terms. If our sequenceis superincreasing then solving the knapsack problem is easy. First of all, xn = 1 if and onlyif s > an. Secondly, once having determined xn, we continue with the knapsack problemcorresponding to the sequence a1, . . . , an−1 and s − xnan. If we terminate in 0 then there isa solution (and we found it); otherwise there is no solution.


Example 4.5.1 Let n = 4 and b1 = 15, b2 = 37, b3 = 119, b4 = 253, s = 387. Then x4 = 1and we continue with b1, b2, b3 and 134. We get x3 = 1 and continue with b1, b2 and 15. Thenx2 = 0 and we finish with b1 and 15, so that x1 = 1, and we found a solution.

The idea of the knapsack cryptosystem is to work with a superincreasing sequence as theprivate key, so that decrypting is easy, and to give a messed-up form of this key as the publickey. More specifically, one chooses a superincreasing sequence b1, . . . , bn such that b1 is closeto 2n and bn is close to 22n. Example 4.5.1 has an instance of this, with n = 4. Next positiveintegers m (the modulus) and w (the multiplier) are chosen such that

m >n∑

i=1

bi, 0 < w < m, gcd(m,w) = 1,

the last condition implying that w is invertible modulom. Finally a permutation π of 1, . . . , nis chosen. Then the private key, kept by the receiver of the messages, is formed by thesequence b1, . . . , bn, together with m, w, and π. The public key, published by the receiver ofthe messages, is the sequence a1, . . . , an, where

ai = wbπ(i) mod m

(where the ai are chosen, modulo m, in the interval (0,m); note that no ai is 0, as otherwisebi = 0 as well, since w is invertible modulo m).

In order to send a string x1 · · · xn, with xi ∈ {0, 1} to the receiver, the sender computesthe number s =

∑ni=1 xiai, and sends s. The reciever, in order to decrypt, first computes the

number t = w−1s mod m. Now modulo m we have the following

t = w−1s =

n∑

i=1

xiw−1ai =

n∑

i=1

xibπ(i) =

n∑

i=1

xπ−1(i)bi,

so the receiver has to solve a knapsack problem with a superincreasing sequence.

Example 4.5.2 Consider the bi from Example 4.5.1 and choose m = 451. Furthermore, letw = 63. Then the wbi mod m are 43, 76, 281, 154. But that still is superincreasing! Sothis w is not good. Let’s try with w = 409, then we get 272, 250, 414, 198, and that is notsuperincreasing. We also select π = (1, 3, 2, 4), so that

a1 = 414, a2 = 198, a3 = 250, a4 = 272.

Now suppose that the sender wants to send 1101. This is encrypted as a1 + a2 + a4 = 884,which is sent to the receiver. We have w−1 = 204 mod m, so the receiver computes

t = 204 · s mod m = 387.

Now the receiver has to solve the knapsack problem

x4b1 + x3b2 + x1b3 + x2b4 = 387.

(Note that π−1 = (1, 4, 2, 3).) It is easily seen that the solution is x1 · · · x4 = 1101 (seeExample 4.5.1).

4.6 Exercises 87

However, in order to arrive at the message that was sent one can also try the following.Consider the matrix

Y =

1 0 0 · · · 0 −a10 1 0 · · · 0 −a20 0 1 · · · 0 −a3...

......

......

...0 0 0 · · · 1 −an0 0 0 · · · 0 s

.

Denote its rows by y1, . . . , yn+1 and let L be the lattice in Rn+1 spanned by them. Note thatthe ‖yi‖ are big, but also that L contains the vector (x1, . . . , xn, 0) which has a much smallerlength than the yi. Now the point is that an LLL-reduced basis of L has a good chance tocontain this vector, thus making the system unsafe to use.

Example 4.5.3 We continue with Example 4.5.2. Here we have

Y =

1 0 0 0 −4140 1 0 0 −1980 0 1 0 −2500 0 0 1 −2720 0 0 0 884

.

In this case an LLL-reduced basis (with α = 34 ) is

1 1 0 1 0−2 1 −1 0 −43 −1 −2 −2 0−1 3 −1 −3 22 2 3 −4 −2

.

We see that we get the decrypted form from the first row.

4.6 Exercises

1. Let (X,X∗,M, γ∗) be a state and apply Exchange(k). Let (Y, Y ∗, N, δ∗) be the stateafterwards. Write νi,j = N(i, j). The purpose of this exercise is to find formulae for theνi,j.

(a) Find a, b, c, d such that

(y∗k−1

y∗k

)=

(a bc d

)(x∗k−1

x∗k

).

(b) Show that ad− bc = −1, and by inverting the matrix, that

x∗k−1 = µk,k−1

‖x∗k−1‖2‖y∗k−1‖2

y∗k−1 + y∗k

x∗k =‖x∗k‖2‖y∗k−1‖2

y∗k−1 − µk,k−1y∗k.


(c) By writing yi as linear combination of the y∗j show that:

i. νj,i = µj,i, for 1 ≤ i < j ≤ k − 2,

ii. νk−1,i = µk,i, for 1 ≤ i ≤ k − 2,

iii. νk,i = µk−1,i, for 1 ≤ i ≤ k − 2, and νk,k−1 = µk,k−1‖x∗

k−1‖2

‖y∗k−1

‖2 ,

iv. νm,i = µm,i for 1 ≤ i ≤ m− 1, i 6= k − 1, k and m ≥ k + 1,

v.

νm,k−1 = µm,k−1µk,k−1

‖x∗k−1‖2‖y∗k−1‖2

+ µm,k‖x∗k‖2‖y∗k−1‖2

vi. νm,k = µm,k−1 − µm,kµk,k−1, m ≥ k + 1.

2. In this exercise we derive a bound for the number of times the LLL algorithm (withparameter α) executes the body of the loop in Step 3. For this, consider a state(X,X∗,M, γ∗); and let B be the maximum of the norms ‖xi‖, 1 ≤ i ≤ n, and Dthe product d1 · · · dn−1 (see Section 4.2 for the definition of di). Write B0, D0 for theirvalues at the start of the algorithm.

(a) Show that d0k ≤ B2k0 , where d0k is the k-th Gram determinant at the start of the

algorithm.

(b) Show that D0 ≤ Bn(n−1)0 .

(c) Let N2 be the number of times the algorithm executes the second clause of theif-statement in Step 3. Show that αN2D0 ≥ 1, and

N2 ≤ − logB0

log αn(n− 1).

(Note that a ratio of logarithms does not depend on the base of the logarithm.)

(d) Let M1(r), M2(r) be the number of times the algorithm has executed the first andthe second clause, respectively, of the if-statement, after r rounds of the iterationin Step 3. (So, if r0 denotes the total number of rounds of the iteration, thenN2 =M2(r0).) Show that k+M2(r)−M1(r) is a constant C, not depending on r.

(e) By considering r = 0 show that C = 2.

(f) Let N1 be the number of times the algorithm executes the first clause of the if-statement in Step 3. Note that when r = r0 we have k = n + 1. Prove thatN1 −N2 = n− 1.

(g) Note that N1 +N2 = 2N2 + n− 1 and prove that

r0 = N1 +N2 ≤ −2 logB0

log αn(n− 1) + n− 1.

WillemdeGraaf - Strutture | UniTrentodegraaf/compalg/compalg.pdf · 2 Gro¨bner Bases A more...

Documents

Transcript of WillemdeGraaf - Strutture | UniTrentodegraaf/compalg/compalg.pdf · 2 Gro¨bner Bases A more...