Other Applications - Elliptic Curves: Number Theory and Cryptography - page 197

relation t m +2 = t 1 t m +1 − t m for m ≥ 0. Let β, γ be the two roots of

f ( X )= X 2 t 1 X +1 in F p 2 . Assume that t 1 − − 4isnotasquarein F p ,

F p .Let s m = β m + γ m for m so β, γ ∈ ≥ 0.

(a) Show that β m +2 = t 1 β m +1 β m for m − ≥ 0, and similarly for γ .

(b) Show that s m +2 = t 1 s m +1 − s m for all m ≥ 0.

0.
(d) Show that β p is a root of f ( X )(mod p ), and that β p

(c) Show that t m ≡ s m (mod p ) for all m ≥

= β .There-

fore, γ = β p .
(e) Show that β p +1 =1and γ p +1 =1.
(f) Show that t p +1 − 2 ≡ 0(mod p ).
(g) Show that if p +1 |B ! for some bound B (so p +1 is B -smooth) then
gcd( t B ! − 2 ,n ) is a multiple of p . Since there are ways to compute

t B ! mod n quickly, this gives a factorization method.

We now show the relation with the elliptic curve factorization method.
Consider a curve E given by y 2 = x 2 ( x + a )mod n ,where a is not a
square mod p . Choose a random point P on E .Tofactor n by the
elliptic curve method, we compute B ! P . By Theorem 2.31, P mod p

corresponds to an element β = u + v √ a ∈ F p 2 with u 2 − v 2 a =1.

(h) Show that β is a root of X 2

− 2 uX +1.

mod p if and only if β B ! =1in F p 2 .
(j) Let t 1 =2 u and define the sequence t m as above.

(i) Show that B ! P = ∞

Show that

B ! P = 2 ,n ). Therefore,

the elliptic curve method factors n exactly when the p +1 method
factors n .

∞ mod p if and only if p divides gcd( t B ! −

(a) Show that if n is prime and g is a primitive root mod n ,then a = g
satisfies the hypotheses of Proposition 7.1 for all .
(b) Suppose we take r = n − 1and s = 1 in Proposition 7.1, and
suppose that there is some number g such that a = g satisfies the
conditions on a for each . Show that g is a primitive root mod
n .( Hint: What power of divides the order of g mod n ?)

7.3

7.4 The proof of Theorem 7.3 works for singular curves given by a Weier-
strass equation where the cubic has a double root, as in Theorem 2.31.
This yields a theorem that uses Z n , rather than E ( Z n ), to prove that n
is prime. State Theorem 7.3 in this case in terms of Z n .( Remark: The
analogue of Theorem 7.3 for Z n is rather trivial. The condition that
P i is a finite point becomes the condition that P i is a number mod n
such that gcd( P i ,n ) = 1 (that is, it is not the identity for the group law
mod any prime factor of n ). Therefore i P i = 0

(mod n ), which implies that i ≡ 0(mod n ). Since i is prime, we must
have n = i . Hence n is prime.)

∞ translates to i P i ≡