Cryptography Reference
In-Depth Information
invariant j 2 . It is easy to see from the construction of Φ ( x ) that its degree is
+ 1, corresponding to the + 1 subgroups in E [ ]oforder +1. Since Φ has
integer coe cients, we can regard it as a polynomial mod p . The following
analogue of Theorem 12.5 holds.
THEOREM 12.19
Let = p be prime, et j 1 ,j 2 F p ,and et E 1 ,E 2 be elliptic curves w ith
invariants j 1 ,j 2 .Then Φ ( j 1 ,j 2 )=0 ifand onlyifthere isanisogeny fro m
E 1 to E 2 of degree .
PROPOSITION 12.20
Let E be an elliptic curve defined over F p . A ssu m e that E is n ot su persingular
and that its j -invariant j is not 0 or 1728. Let = p be prime.
1. Let j 1 F p be a root of the polynom ial Φ ( j, T ) ,let E 1 be an elliptic
curve ofinvariant j 1 ,and let C be the kernelofthe corresponding isogeny
E → E 1 ofdegree .Let r ≥ 1 .Thereexists ν ∈ Z su ch that φ r P = νP
for all P ∈ C ifand onlyif j 1 F p r .
2. T he polynom ial Φ ( j, T ) factors into inear factors over F p r ifand only
ifthere exists ν ∈ Z su ch that φ r P = νP for all P ∈ E [ ] .
If φ r P = νP for all P
C , then, as discussed previously, the
j -invariant j 1 oftheisogenouscurveisin F p r . Similarly, if φ r P = νP for all
P
PROOF
E [ ], then all -isogenous curves have j -invariants in F p r , so all roots of
Φ ( j, T )arein F p r .
For proofs of the converse statements, see [99].
REMARK 12.21
The restriction to j
=0 , 1728 is necessary. See Exercise
12.11.
By computing gcd ( T p
− T, Φ ( j, T )) as a polynomial in F ,weobtaina
polynomial whose roots are the roots of Φ ( j, T )in F . Finding a root j 1
of this polynomial allows us to construct a curve with j -invariant j 1 (using
the formula on page 47) that is -isogenous to E . As mentioned previously,
a rather complicated procedure, described in [12] and [99], yields the desired
factor F ( x ) of the division polynomial ψ ( x ).
Example 12.5
Consider the elliptic curve E : y 2 = x 3 + x +7 over F 23 . The group E [3] is
generated by P 1 =(1 , 3) and P 2 =(14 , 5), where 5 F 23 2 .Let φ be the
23rd power Frobenius endomorphism. Then φ ( P 1 )= P 1 and φ ( P 2 )= −P 2 .
 
Search WWH ::




Custom Search