The Basic Theory - Elliptic Curves: Number Theory and Cryptography - page 65

Example 2.9
Let E be given by

y 2 = x 3 +3 x − 3

over Q . Suppose we want to compute

(1 , 1) + ( 571

16379
6859 ) .

361 ,

Since the points are distinct, we compute the slope of the line through them
in the usual way. This allows us to find the sum. Now consider E mod 7.
The two points are seen to be congruent mod 7, so the line through them
mod 7 is the tangent line. Therefore, the formula we use to add the points
mod 7 is different from the one used in Q . Suppose we want to show that the
reduction map from E ( Q )to E ( F 7 ) is a homomorphism. At first, it would
seem that this is obvious, since we just take the formulas for the group law
over Q and reduce them mod 7. But the present example says that sometimes
we are using different formulas over Q and mod 7. A careful analysis shows
that this does not cause problems, but it should be clear that the reduction
map is more subtle than one might guess.

The remedy for the above problems is to develop a theory of elliptic curves
over rings. We follow [74]. The reader willing to believe Corollaries 2.32, 2.33,
and 2.34 can safely skip the details in this section.
Let R be a ring (always assumed to be commutative with 1). A tuple of
elements ( x 1 ,x 2 ,... )from R is said to be primitive if there exist elements
r 1 ,r 2 , ···∈R such that

r 1 x 1 + r 2 x 2 + ··· =1 .

When R = Z , this means that gcd( x 1 ,x 2 ,... )=1. When R = Z n , primitivity
meansthatgcd( n, x 1 ,x 2 ,... )=1. When R is a field, primitivity means that
at least one of the x i is nonzero. In general, primitivity means that the ideal
generated by x 1 ,x 2 ,... is R . We say that two primitive triples ( x, y, z )and
( x ,y ,z ) are equivalent if there exists a unit u ∈ R × such that

( x ,y ,z )=( ux, uy, uz )

(in fact, it follows easily from the existence of r, s, t with rx + sy + tz =1
that any u satisfying this equation must be a unit). Define 2-dimensional
projective space over R to be

P 2 ( R )= { ( x, y, z ) ∈ R 3 | ( x, y, z )isprimitive } mod equivalence .

The equivalence class of ( x, y, z ) is denoted by ( x : y : z ).
If R is a field, P 2 ( R ) is the same as that defined in Section 2.3. If ( x :
y : z ) ∈ P 2 ( Q ), we can multiply by a suitable rational number to clear