Let us first consider the class of principal divisors. There is no other divisor in this class: suppose that D + div(f) = div(h) for polynomials f, h ∈ k[x, y]. Then, ordP(f) ≤ ordP(h) for all P ∈ E (k) and, by Theorem 5.4, there exists a polynomial g with fg = h. Thus, D = div(g) is a principal divisor. In particular, the zero class does not contain any divisor of degree 1. For P ∈ E(k), it then follows that [P] ≠ 0 in Pic0(E(k)) and therefore the Picard group is not trivial.

If we consider two points P, Q ∈ E(k), then [P] ≠ [Q] is equivalent to If the x-coordinates of P and are different and there is a unique line through P and This line intersects the elliptic curve in a third point R. Then, is a principal divisor for a linear polynomial and therefore This shows that [P] ≠ [Q]. If then P ≠ (ai , 0) and for the third point R in the intersection of the tangent at P with the curve E (k). Thus, for two different points P, Q ∈ E (k), we always have [P] ≠ [Q]. It remains to consider the point at infinity and we define [] = 0.

Theorem 5.5. The mapping

defines an isomorphism of Abelian groups.

Proof: As we have just seen, the mapping is injective. It is surjective, too. To see this, we give an equivalence preserving reduction process on the set of divisors. A divisor of the form can be replaced by 0. For each divisor P + Q with we find a line and thus another point R on the curve with the property that P + Q + R is a principal divisor. Thus, P + Q can be replaced by Each step reduces the degree of a divisor. The algorithm ends at 0 and therefore at the point at infinity or at a divisor of degree 1, that is, a point on the curve. The homomorphism property P + Q ↦ [P] + [Q] directly follows from the construction.

Since the Picard group is an Abelian group, the points of the elliptic curve E ̃(k) also form an Abelian group. Furthermore, if K is a subfield of k, the formulas in Section 5.1.1 show that Ẽ(K) = { (a, b) ∈ K × K | b2 = s(a) } is a subgroup. Addition, as introduced in Section 5.1.1, coincides with addition in the Picard group. The associative law, thus, is a consequence of the interpretation of the points on the curve as divisors and the interpretation of lines as principal divisors. This completes the proof of Theorem 5.1.

□

5.2 Applications of elliptic curves

This section is mostly self-contained. We therefore repeat the most important properties of elliptic curves. Let K be a field with a characteristic different from 2 and let A, B ∈ K with 4A3 + 27B2 ≠ 0. The set of points defined by the equation Y2 = X3 + AX2 + B is

If we add a new point , called the point at infinity, then we obtain the elliptic curve E ̃(K) defined by the parameters A and B.

There is an addition + on E ̃(K) such that (Ẽ(K), +, ) forms an Abelian group with neutral element O. For points P = (x1, y1) and Q = (x2, y2) in E(K), the sum P + Q is given by the following formulas.

Case (c) gives a simple formula for computing the inverse. For P = (x1, y1)∈ E (K), we have −P = (x1, −y1). Case (a) occurs if and only if P ≠ Q and P ≠ −Q. We presented a complete proof of the group laws in Section 5.1. In particular, we have P + Q ∈ Ẽ(K) for all P, Q ∈ E ̃(K). The addition on E ̃(K) might look mysterious at first sight but it has a geometric motivation, which is given in Section 5.1.1.

Many cryptographic protocols are based on arithmetic in cyclic groups. A typical example is the subgroup 〈g〉 of (ℤ/pℤ)∗ generated by g ∈ (ℤ/pℤ)∗. The analogon for elliptic curves is 〈P〉 where P is a point on an elliptic curve over a finite field. The general idea is to replace the operation gk in (ℤ/pℤ)∗ by

on the elliptic curve. For the efficient computation of k ⋅ P, you can use fast exponentiation with the only difference that multiplication is replaced by addition. For the sake of security, certain requirements have to be met by the subgroup 〈P〉 generated by P: for example, this group should be large, and its order should have a large prime divisor. The advantage of elliptic curves is that the same level of security as in (ℤ/pℤ)∗ can already be achieved with smaller key lengths. This is mainly because algorithmic techniques that rely on linear algebra seem not to work over elliptic curves: for instance, to date there has been no efficient adaptation of the quadratic sieve or the index calculus algorithm.

5.2.1 Diffie–Hellman key exchange with elliptic curves

We use Diffie and Hellman’s key exchange protocol as an example of how to apply elliptic curves in cryptography; see Section 2.9 for the classical version. Alice and Bob wish to agree upon a common key which is not known to anybody else. The common key could then be used for a symmetric encryption method such as AES. The problem is that all communication between Alice and Bob can be intercepted.

First, Alice chooses an elliptic curve Ẽ(ℤ/pℤ) together with a point P = (x, y) on this curve. The naive approach for this is to choose the parameters A, B, and p of the curve as well as a random element x such that x3 + Ax + B is a square in ℤ/pℤ; and then Alice computes y as a square root of x3 + Ax + B modulo p. This could be done using Tonelli’s or Cipolla’s algorithm or, as in the Rabin cryptosystem, she could rely on special prime numbers p for which the extraction of roots is easy. The following procedure is much simpler: Alice first chooses a large prime number p and elements A, x, y ∈ ℤ/pℤat random, and then she computes B = y2 −x3−Ax mod p. The elliptic curve Ẽ(ℤ/pℤ) is fully defined by the parameters A, B, and p. By construction, the point P = (x, y) lies on the curve.

Alice sends the public key (p, A, B, x, y) to Bob. As a secret key, Alice chooses a ∈ ℕ. Then, she sends the coordinates of the point a ⋅ P to Bob. Bob proceeds analogously. He chooses a secret number b ∈ ℕ and sends b ⋅ P to Alice. They are now both able to compute the point

Neither of them needs to know the other’s secret key. The point Q can be used as their common secret key (for example by taking the first n bits of the binary representation). The computation of a, when given P and a⋅P, is exactly the discrete logarithm to base Pin the group E ̃(ℤ/pℤ). One can therefore assume that intercepting the communication does not help in retrieving the secret key. The computation of Q, when given the points P, a ⋅ P and b ⋅ P, is known as the Diffie–Hellman problem, and it is believed not to be efficiently solvable.

We note that the ElGamal cryptosystem can also be adapted to elliptic curves in the very same way as the Diffie–Hellman key exchange protocol.

5.2.2 Pseudocurves

The proof of the group laws for E ̃(K) in Section 5.1 relies on the fact that K is a field. Now, we consider elliptic curves over quotient rings ℤ/nℤ. If n is composite, then such rings are not fields. Thus, we cannot rely on validity of the group laws anymore. Even the sum of two points is not necessarily defined in all cases since the denominators in the above computations need not be invertible.

Let n ∈ ℕ be an odd number greater than 1 and let A, B ∈ ℤ such that gcd(4A3 + 27B2, n) = 1. The pseudocurve defined by the parameters A and B is

The name pseudocurve shall indicate that ℤ/nℤ does not need be a field. As usual, we identify ℤ/nℤ with {0, . . . , n − 1}. We transfer the addition operation from elliptic curves to pseudocurves, but with the restriction that the sum is only partially defined. The point at infinity is neutral and for P = (x1, y1) and Q = (x2, y2) in Ẽ(ℤ/nℤ){O}, we define P + Q as follows.

In both cases, we define the addition P + Q = (x3, y3) by x3 = μ2 − x2 − x1 and y3 = μ(x1 − x3)− y1. All computations are modulo n.

There are three possibilities for P + Q to be undefined. First, we could have x1 ≢ x2 mod n, but x2 − x1 is not in (ℤ/nℤ)∗. Second, we could have P = Q, but y1 is not in (ℤ/nℤ)∗. And the third possibility for composite numbers n is x1 ≡ x2 mod n but y1 ≢ ±y2 mod n.

Theorem 5.6. Let P, Q ∈ Ẽ(ℤ/nℤ) such that P + Q is defined. Then, P + Q ∈ Ẽ(ℤ/nℤ).

Proof: We may assume that P ≠ and Q ≠ O. Let P = (x1, y1) and Q = (x2, y2). First, suppose that x2 − x1 is invertible modulo n. In this case, the claim essentially follows from the derivation (see Section 5.1.1) of the earlier given formulas. However, a few minor adjustments are necessary. Let μ ≡ (y2 − y1)⋅ (x2 − x1)−1 mod n. Then, P + Q = (x3, y3) with x3 = μ2 − x2 − x1 mod n and y3 = μ(x1 − x3)− y1 mod n. For ν ≡ y1 − μx1 mod n, we have

Therefore, P and Q are points on the line Y = μX + ν over ℤ/nℤ. Let s(X) = X3 + AX + B and g(X) = μX + ν. Both x1 and x2 are roots of the polynomial t(X) = s(X) − g2(X) of degree 3 over ℤ/nℤ. From Corollary 1.47, we obtain t(X) = (X − x1)r(X) for a polynomial r of degree 2. Since x2 − x1 is invertible, x2 is a root of r. Together with the degree formula from Theorem 1.42 this yields

for x̂̂3 ∈ ℤ/nℤ. By comparing the coefficients at X2, we see that x̂3 ≡ x3 mod n. For ŷ3 = g(x3),we have mod n and thus (x3, ŷ̂3) ∈ Ẽ(ℤ/nℤ). Moreover, ŷ3 = μx3 + ν ≡ −μ(x1 − x3) + y1 ≡ −y3 mod n shows P + Q = (x3, y3) ∈ Ẽ(ℤ/nℤ).

The second case is x1 ≡ x2 mod n. We can exclude the case that y1 ≡ −y2 mod n because the point at infinity belongs to Ẽ(ℤ/nℤ). Since P + Q is defined, we can conclude that y1 ≡ y2 mod n and that 2y1 is invertible modulo n; remember that n is odd. In particular, P = Q. Let P+Q = 2P = (x3, y3) in Ẽ(ℤ/nℤ).We use closure of the operation on elliptic curves over ℚ. We interpret x1, y1 ∈ {0, . . . , n −1} ⊆ℚ. Let B' = B + kn with

Let E' be the curve defined by A and B. Then, Ẽ(ℤ/nℤ) = Ẽ(ℤ/nℤ) and P = (x1, y1)∈ Ẽ(ℚ). Due to the addition rules, there exist with

and mod n as well as mod n. Here, (2y1)−2 denotes the inverse of (2y1)2 modulo n. Now, 2P ∈ Ẽ(ℚ) yields (x3, y3) ∈ Ẽ(ℤ/nℤ).

□

Let m > 1 be a divisor of n. Then, E ̃(ℤ/mℤ) inherits the property of being a pseudocurve from Ẽ(ℤ/nℤ). By the homomorphism theorem for rings, we know that mod m: ℤ/nℤ → ℤ/mℤ: x ↦ x mod m is a ring homomorphism. We extend this mapping to points P = (x, y) ∈ Ẽ(ℤ/nℤ) by

and define mod m = O. If P is a point on the pseudocurve Ẽ(ℤ/nℤ), then P mod m is a point on the pseudocurve Ẽ(ℤ/mℤ). An important special case of this modulo operation on curve points occurs if m is prime. Then, E ̃(ℤ/mℤ) is an elliptic curve since m > 2 and 4A3 + 27B2 ≠ 0 in ℤ/mℤ. The following theorem connects the operations on the two pseudocurves. The main problem is that P + Q in E ̃(ℤ/nℤ) might a priori be obtained by different formulas than (P mod m)+(Q mod m) in Ẽ(ℤ/mℤ). We show that this cannot happen.

Theorem 5.7. Let m > 1 be a divisor of n and let P, Q ∈ Ẽ(ℤ/nℤ) be points such that P + Q is defined. Then, (P mod m) + (Q mod m) in Ẽ(ℤ/mℤ) is defined and

Proof: We may assume that P = (x1, y1) ≠ and Q = (x2, y2) ≠ O. The ring homomorphism mod m: ℤ/nℤ → ℤ/mℤ is compatible with forming inverses, that is, for gcd(x, n) = 1 we have

On the left-hand side of the equation, (x mod n)−1 denotes the inverse of x modulo n while, on the right-hand side, the element x mod m is inverted in ℤ/mℤ. If we apply the same formulas for the addition of the points in Ẽ(ℤ/nℤ) and Ẽ(ℤ/mℤ), then the homomorphism property yields the desired result. In particular, the sum (P mod m)+ (Q mod m) is defined in this situation. The remaining cases are

In case (a), the sum P + Q is not defined because x2 − x1 is divisible by m and therefore not invertible modulo n. Thus, the requirements of the theorem are not satisfied. In case (b), the sum P + Q is not defined either because 2y1 ≡ y1 + y2 mod n and m | y1 + y2. Thus, 2y1 is not invertible modulo n. If case (c) occurs, then again P + Q is not defined.

□

5.2.3 Factorization using elliptic curves

In order to factorize an integer n > 1, you try to find m ∈ {2, . . . , n − 1} with m | n. Although still unproven, the factorization of binary numbers is considered to be not solvable in polynomial time. Therefore, a factorization algorithm is only taken into account after you have checked that the number in question is composite. We already discussed several primality tests. A second typical preparatory step is to exclude small divisors by trial divisions. The idea of using elliptic curves for factorization was derived by Hendrik Willem Lenstra Jr. (born 1949). In the following, we present a probabilistic variant of this approach. The basic idea is Pollard’s p − 1 algorithm, which we repeat briefly. Let n be a composite number, p a prime factor of n and let a ∈ ℕ with gcd(a, n) = 1.We assume that k ∈ ℕ is a multiple of p − 1. By Fermat’s little theorem, we have ap−1 ≡ 1 mod p, and thus also

Now p | ak −1 and p | n. If ak ≢ 1 mod n then gcd(ak −1, n) yields a nontrivial divisor of n. In this method, we have some freedom in the choice of a and k. Apossible strategy for choosing k is motivated by the hope that p − 1 can be factorized into small prime divisors. Since we do not know p at this point, you could choose k as

Here, C is an expected upper bound for the prime divisor of p − 1. In order to keep k within a reasonable size, C must not be too large. For a, an arbitrary value from (ℤ/nℤ)∗ can be chosen. The disadvantage of the method is that the structure of ℤ/nℤ cannot be changed. If, for example, no prime factor p of n has the property that p − 1 has only small prime divisors, then Pollard’s p − 1 algorithm is not successful. This is where pseudocurves come into play because, for every n, there are numerous pseudocurves Ẽ(ℤ/nℤ).

Lenstra’s method also starts by choosing a bound C and constructing a number k as before. The greater the number C, the better the chance of finding a divisor. However, the time for the computation also grows with C. The idea is to randomly select a pseudocurve Ẽ(ℤ/nℤ) and a point P ∈ Ẽ(ℤ/nℤ). Then, you try to compute k ⋅ P with the hope that, at some point in this computation, the sum of two points is undefined. This will then yield a nontrivial divisor of n. If the computation of k ⋅ P is successful, then we repeat this step with another pseudocurve. This is not possible with Pollard’s p − 1 algorithm.

We now discuss the details of the method. The algorithm first chooses A, x, y ∈ {0, . . . , n − 1} at random. Then, B is computed by

If gcd(4A3 + 27B2, n) ≠ 1, then we either found a nontrivial divisor of n or we repeat the process. The pseudocurve Ẽ(ℤ/nℤ) is now given by the equation Y2 = X3 + AX + B with gcd(4A3 + 27B2, n) = 1 and the point on Ẽ(ℤ/nℤ) is P = (x, y).

Remark 5.8. If we determined A and B first, then it would be harder to find a nonzero point on the curve. Note that neither Tonelli’s nor Cipolla’s algorithm can be used for the extraction of roots since ℤ/nℤ is not a field.

◊

The operation on pseudocurves need not be defined for all possible arrangements of parentheses. For example, in the computation of 5 ⋅ P, it is possible that ((P + P) + (P + P)) + P is defined whereas (P + P) + ((P + P) + P) is undefined. The difference here is that, in the second case, 3 ⋅ P = (P + P) + P occurs as an intermediate result. Moreover, for two different parentheses, where all intermediate results are defined, we cannot expect that both of them yield the same result. This problem is circumvented by using a fixed algorithm for the computation of k ⋅ P. Thus, the parenthesis is uniquely determined by k. We can view k ⋅ P as the result produced by this particular algorithm. This result can also be undefined. To compute k ⋅ P as efficiently as possible, you use fast exponentiation with addition rather than multiplication as operation.

Proposition 5.9. If the operation Q + R for two points Q, R ∈ Ẽ(ℤ/nℤ) is not defined, this yields a nontrivial divisor of n.

Proof: Let Q = (x1, y1) and R = (x2, y2). If Q + R is undefined, then there are three possible reasons. The first one is that x1 ≢ x2 mod n, but x2 − x1 is not invertible modulo n. In this case, x2 − x1 is not a multiple of n and not coprime to n. Thus, gcd(x2 − x1, n) is a nontrivial divisor of n. The second possibility is x1 ≡ x2 mod n and y1 ≡ y2 ≢ 0 mod n, but y1 is not invertible modulo n. Now, gcd(y1, n) yields a nontrivial divisor of n. The third case is x1 ≡ x2 mod n, but y1 ≢ ±y2 mod n. We have

Therefore, is a multiple of n, but neither y2 + y1 nor y2 −y1 is a multiple of n. But then both gcd(y2 + y1, n) and gcd(y2 −y1, n) are nontrivial divisors of n.

□

If the operation Q + R for two points Q and R during an intermediate step in the computation of k ⋅ P is not defined, then we obtain a nontrivial divisor of n. It remains to explain why we can hope for some addition during the computation to be undefined. Let p ≥ 3 be a prime factor of n. Then, Ẽ(ℤ/pℤ) is an elliptic curve. The hope is that the order of Ẽ(ℤ/pℤ) has only small prime divisors because then k ⋅ (P mod p) = in Ẽ(ℤ/pℤ). It is very unlikely that, for all other prime divisors q of n, we also have k ⋅ (P mod q) = in Ẽ(ℤ/qℤ). From Theorem 5.7, it follows that k ⋅ P is not defined in Ẽ(ℤ/nℤ); otherwise k ⋅ P = would follow because only the point at infinity is mapped to the point at infinity mod p. This in turn would imply k ⋅ (P mod q) = in Ẽ(ℤ/qℤ), contradicting our assumption.

5.2.4 Goldwasser–Kilian primality certificates

The idea behind a primality certificate is to provide an efficiently verifiable proof. If a number n has a primality certificate, then the proof should show that n is prime with absolute certainty. One such approach goes back to Henry Cabourn Pocklington (1870–1952).

Theorem 5.10 (Pocklington). Let a, k, n, q ∈ ℕ with n − 1 = q ⋅ k and q > k. Suppose that the following properties are satisfied:

Proof: Suppose that n is composite. Then there exists a prime divisor p of n with Let d be the order of a in (ℤ/pℤ)∗. From (b), we obtain an−1 ≡ 1 mod p. Therefore, d is a divisor of n − 1. From (c), we obtain that d does not divide k. Then, (a)yields that q is a divisor of d. Altogether, we have But q > k yields a contradiction. Consequently, n is prime.

□

Example 5.11. We present a proof for the primality of 2 922 259 that (with the help of a computer) can easily be checked. We have 2922259 − 1 = 1721 ⋅ 1698 and

Both facts can be checked efficiently using fast modular exponentiation and the Euclidean algorithm. If we knew that 1721 is prime, then Pocklington’s theorem would show that 2 922 259 is prime. We use the same approach to give a proof for the primality of 1721. We have 1721 − 1 = 43 ⋅ 40 and

Finally, we “prove” that 43 is prime since 43 − 1 = 7 ⋅ 6 and

Since we know that 7 is prime, the number 43 is prime, too. This in turn implies that 1721 is prime and finally that 2 922 259 is prime. The primality certificate consists of all numbers involved in the proof given earlier:

The process (in reverse order) can also be used to produce “provable” primes.

◊

The problem with Pocklington’s primality certificates is that they only work for numbers n where n − 1 has a large prime factor. Shafrira Goldwasser (born 1958) and Joseph John Kilian’s algorithm carries Pocklington’s idea over to elliptic curves. Here, by choosing different curves, numerous groups are available. Similar to the situation with integer factorization, one would apply this method only if n has passed a probabilistic primality test such as the Miller–Rabin test.

Theorem 5.12 (Goldwasser and Kilian 1986). Let n ∈ ℕ and let Ẽ(ℤ/nℤ) be a pseudocurve. Let ≠ P ∈ Ẽ(ℤ/nℤ) and a prime number. If q ⋅ P = in Ẽ(ℤ/nℤ), then n is prime.

Proof: Let q ⋅ P = in E ̃(ℤ/nℤ) and suppose that n is composite. Then there exists a prime factor p of n with Let d be the order of P mod p in the elliptic curve Ẽ(ℤ/pℤ). From Theorem5.7, we have q ⋅ (P mod p) = in Ẽ(ℤ/pℤ). This implies d | q. Since q is prime and d ≠ 1, we obtain d = q. Thus, q ≤ |Ẽ(ℤ/pℤ)|. According to the Hasse bound in equation (5.1), however, and we have a contradiction.

□

Remark 5.13. If you require the stronger assumption in Theorem 5.12, then the statement can be shown without using the Hasse bound. Instead, the weaker (and easy to prove) estimate |Ẽ(ℤ/pℤ)| ≤ 2p + 1 in the earlier proof is sufficient. The assumption is not a limitation for applications.

◊

Let us now describe Goldwasser and Kilian’s algorithm. An important step in this algorithm is to efficiently determine the number of points on an elliptic curve over a finite field. The first deterministic polynomial time algorithm for this task was derived by René Schoof (born 1955). If m = log(p) is the number of bits of the prime p, it takes (m9) operations to compute |Ẽ(ℤ/pℤ)|, and thus in its original form it was not practicable. With some improvements, especially by Arthur Oliver Lonsdale Atkin (1925–2008) and Noam Elkies (born 1966), the computation essentially takes (m4) operations. Another ingredient is a probabilistic algorithm for computing square roots in finite fields. This can be done with either Tonelli’s or Cipolla’s algorithm; see Section 3.5.

We want to prove that n ∈ ℕ is prime. Moreover, the test shall provide a certificate for this property. For small numbers n, we can solve this by means of a table lookup. Therefore, we can assume n to be sufficiently large. First, by a probabilistic procedure, we convince ourselves that n is prime with high probability. Then, we choose a random pseudocurve Ẽ(ℤ/nℤ) and, for example by using Schoof’s algorithm, we compute the number |Ẽ(ℤ/nℤ)| under the assumption that n is prime. If this calculation is not possible, for example, due to a division by zero, then n is composite. We keep on searching for pseudocurves until |Ẽ(ℤ/nℤ)| = kq for a probable prime q which satisfies Before we certify q as prime, we choose a random point P = (x, y) on Ẽ(ℤ/nℤ). For this, we repeatedly choose x ∈ ℤ/nℤat random until y ∈ ℤ/nℤ is found such that y2 ≡ x3 +Ax+B mod n. To determine y, we use one of the randomized methods for extracting roots in finite fields. Should the process fail, then the chances of finding a proper divisor of n are good, thus proving that n is composite. In the next step, we compute P'' = k ⋅P in Ẽ(ℤ/nℤ). If k ⋅P is not defined, then n is composite. If P' = , we search for a new point P ∈ Ẽ(ℤ/nℤ). For P' ≠ , the point P' must have the order q, otherwise n is composite. If the computation of q ⋅P' = in Ẽ(ℤ/nℤ) is successful, then from Theorem 5.12, we obtain that n is prime, provided that q is prime. Therefore, we apply the method recursively on input q and thus certify q to be prime. The certificate for the primality of n consists of the parameters of Ẽ(ℤ/nℤ), the point P, and the number q together with a certificate for its primality. If this algorithm yields a result, this result is always correct. However, it cannot be guaranteed that the algorithm always terminates after finitely many steps and returns a result. Due to the diversity of elliptic curves, however, in practice it turns out that the algorithm terminates with very high probability. Moreover, its running time can compete with the AKS algorithm from Chapter 4 (and, in contrast to the AKS algorithm, it additionally yields a primality certificate, which can be verified efficiently).

5.3 Endomorphisms of elliptic curves

In the previous section, we used the Hasse bound from Equation (5.1) to improve the performance of the Goldwasser–Kilian primality test. Without the Hasse bound, we obtain a sufficiently good but slightly weaker result. On the other hand, the Hasse bound is indispensable for a deeper understanding of elliptic curves. The known proofs of this formula are based on the study of endomorphisms. This section provides an introduction to the basic concepts and theorems concerning endomorphisms of elliptic curves. The proofs of many results in this section make nice exercises.

Let k be an algebraically closed field with a characteristic different from 2, and let E(k) be the elliptic curve defined by Y2 = X3 +AX+B. In particular, s(X) = X3 +AX+B has no multiple roots. In Section 5.1.2, we defined the polynomial ring k[x, y] over E (k) as

The element x ∈ k[x, y] is the residue class of X and y is the residue class of Y. In k[x, y], we have y2 = s(x). The image of k[X] in k[x, y] is denoted by k[x]. Since y2 = s(x) in k[x, y], we have y2 ∈ k[x]. Every polynomial f ∈ k[x, y] can uniquely be written as f = υ(x) + yw(x) with υ(x), w(x) ∈ k[x]. Let Then, is the norm of f. We have N(f) = 0 if and only if f = 0. The ring k[x, y] has no zero divisors: if fg = 0 in k[x, y], then N(f)N(g) = 0 in k[x], and therefore N(f) = 0 or N (g) = 0. Thus, k[x, y] is an integral domain.

We can form the field k(x, y) consisting of all fractions for polynomials p(x, y), q(x, y) ∈ k[x, y] with q(x, y) ≠ 0. Two fractions and define the same element of k(x, y) if and only if p(x, y)υ(x, y) = u(x, y)q(x, y) in k[x, y]. Addition and multiplication are defined in the same way as for “usual” fractions. We call k(x, y) the function field of E(k); its elements are rational functions. A rational function induces a (partial) mapping E(k) → k by (a, b) ↦ r(a, b) for P = (a, b) ∈ E (k), and this mapping is defined for almost all P ∈ E(k); it is undefined if and only if q(a, b) = 0.

Lemma 5.14. If two rational functions r(x, y) and t(x, y) in k(x, y) coincide at infinitely many points P ∈ E(k), then r(x, y) = t(x, y).