Elliptic Curves over Q - Elliptic Curves: Number Theory and Cryptography - page 206

multiple nP is not on the list and P is not torsion. Alternatively, we can use
Mazur's theorem (Theorem 8.11 below), which says that the order of a torsion
point in E ( Q ) is at most 12. Therefore, if nP 12, then P is

not torsion. Consequently, it is usually not hard to check each possibility in
the Lutz-Nagell theorem and see which ones yield torsion points. However,
sometimes the discriminant is hard to factor, and sometimes it contains many
factors. In this case, another algorithm can be used. See Section 9.6.
Another technique that helps us determine the torsion subgroup involves
reduction mod primes. The main result needed is the following.

= ∞ for all n ≤

THEOREM 8.9
Let E be an elliptic curve given by y 2 = x 3 + Ax + B with A, B ∈ Z .Let p
be an odd primeandassume p 4 A 3 +27 B 2 .Let

ρ p : E ( Q ) → E ( F p )

be the reduction mod p m ap. If P

∈ E ( Q ) has finiteorderand ρ p ( P )= ∞ ,

then P =

∞ .

REMARK 8.10 In general, reduction mod a prime ideal containing p is
injective on the prime-to- p torsion in E ( Q ). This is similar to the situation
in algebraic number theory, where reduction mod a prime ideal containing p
is injective on roots of unity of order prime to p (see [129]).

)have
integral coordinates, so they reduce to well-defined finite points mod p .In
particular,

PROOF By Theorem 8.7, all of the torsion points (other than ∞

∞ is the only point that reduces to ∞ .

Example 8.3
Let's use Theorem 8.9 to find the torsion on y 2 = x 3 +8. We have 4 A 3 +

27 B 2 3 3 ,sowecannotusetheprimes2 , 3. The reduction

mod 5 has 6 points, so Theorem 8.9 implies that the torsion in E ( Q )has
order dividing 6. The reduction mod 7 has 12 points, so the torsion has order
dividing 12, which gives no new information. The reduction mod 11 has 12
points, so we again get no new information. However, the reduction mod 13
has 16 points, so the torsion in E ( Q ) has order dividing 16. It follows that
the torsion group has order dividing 2. Since ( − 2 , 0) is a point of order 2, the
torsion has order exactly 2. This is of course the same result that we obtained
earlier using the Lutz-Nagell theorem.

= 1728 = 2 6 ·

Example 8.4
In the preceding example, the Lutz-Nagell theorem was perhaps at least as
fast as Theorem 8.9 in determining the order of the torsion subgroup. This is