We want to look at algebraic number theory, elliptic curves and applications in cryptography. First some generalities on algebraic number theory.

Algebraic integers

Algebraic numbers are elements of a finite extension of Q, the field of rational numbers. In other words, they are roots of a polynomial p(x) with rational coefficients, and hence roots of a polynomial with integral coefficients. The degree of an algebraic number a is the minimal degree of a nonzero polynomial p(x) with integral coefficients having a as root. For example, the algebraic numbers of degree 1 are the elements of Q. And sqrt(2) is an algebraic number of degree 2.

Algebraic integers are roots of a polynomial with integral coefficients and leading coefficient 1. For example, the algebraic integers of degree 1 are the ordinary integers (elements of Z). And sqrt(2) is an algebraic integer.

Exercise An algebraic integer a of degree d is root of a polynomial with integral coefficients of degree d.

Exercise An irreducible monic polynomial in Z[x] is irreducible in Q[x].

Proposition An algebraic integer that is a rational number, is an ordinary integer.

Theorem Algebraic integers form a ring. Algebraic numbers form a field.

Proof The field part is trivial. For the ring part use the Lemma below on the Z-module generated by all products a^h bⁱ to conclude that ab and a+b are algebraic integers. QED

Lemma Let M be a nonzero finitely generated Z-module contained in C, the field of complex numbers. Let x be a complex number such that xM is contained in M. Then x is an algebraic integer.

Proof Let M be generated by m₁, ..., m_r. By assumption there are integers a_ij such that x m_i = sum a_ij m_j, that is, sum (a_ij - delta_ij x) m_j = 0, for all i. But a system of homogeneous equations with nonzero solution has zero determinant, and we find a monic equation for x with coefficients in Z. QED

An algebraic number field F is a finite extension of Q. The algebraic integers in F form its ring of integers D.

Diophantine equations

If it is possible to factor elements of D uniquely into prime elements, then we can solve many Diophantine equations (equations over Z).

For example, it is easy to solve the Diophantine equation x^2 + y^2 = z^2. Indeed, if x, y, z have a common factor, divide it out. We may assume that x is even. Now write the equation as x² = (z-y)/2 . (z+y)/2. Both factors on the right are coprime and by unique factorization in Z it follows that both are squares: say z-y = 2 n² and z+y = 2 m² so that our solution becomes x = 2mn, y = m² - n², z = m² + n², where m, n are coprime, not both odd. For example, m=2, n=1 yields 4² + 3² = 5², and m=3, n=2 yields 12² + 5² = 13². The general solution (before dividing out the gcd of x,y,z) is then (x,y,z) = k.(2mn,m²-n²,m²+n²).

Exercise Find all integral solutions of x⁴ + y⁴ = z⁴.

The corresponding attack on Fermat's problem: solve xⁿ + yⁿ = zⁿ, might start with xⁿ = prod_i (z - wⁱ y) where w is an n-th root of unity, but the factors on the right lie in Z[w], and we don't know whether one has unique factorization in Z[w], so cannot conclude immediately that these factors must be almost n-th powers.

Unique factorization fails

A bad example is Z[sqrt(-5)] where 6 = 2 . 3 = (1+sqrt(-5)).(1-sqrt(-5)) and 2, 3, 1+sqrt(-5), 1-sqrt(-5) are all prime.

Units and primes

A unit is an algebraic integer u such that its inverse 1/u is also an algebraic integer. For example, in Z the units are 1 and -1, and in Z[i] the units are 1,-1,i,-i. We'll meet later rings of integers with infinitely many units.

A prime is an algebraic integer p that is not the product of two algebraic integers, neither of which is a unit.

Norm and trace

In the particular case of Z[sqrt(d)] we have a norm that maps Z[sqrt(d)] into Z, and is multiplicative: N(x+ysqrt(d)) = x² - dy².

Exercise Using the norm, show that 2, 3, 1+sqrt(-5), 1-sqrt(-5) are all prime in Z[sqrt(-5)].

Unique factorization into ideals

The main theorem in algebraic number theory promises that although factorization into numbers is not unique, factorization into ideals is. We'll give a detailed proof next time.