Cryptography Reference
In-Depth Information
since all the powers of x except for x q− 1 sum to 0. Therefore,
# E ( F q )=1 − A q
in F q .
By Proposition 4.31, E is supersingular if and only if A q =0in F q .The
following lemma allows us to relate A q to A p .
LEMMA 4.36
Let f ( x )= x 3 + c 2 x 2 + c 1 x + c 0 be a cu bicpo ynom ialw ith coe cientsina
field of characteristic p .Foreach r
1 ,let A p r be the coe cient of x p r 1 in
f ( x ) ( p r 1) / 2 .Then
A p r = A 1+ p + p 2 + ··· + p r− 1
.
p
PROOF
We have
( f ( x ) ( p− 1) / 2 ) p r
=( x 3( p− 1) / 2 + ··· + A p x p− 1 + ··· ) p r
= x 3( p− 1) p r / 2 + ··· + A p p x p r ( p− 1) + ··· .
Therefore,
1) / 2 = f ( x ) ( p r 1) / 2 f ( x ) ( p− 1) / 2 p r
f ( x ) ( p r +1
=( x 3( p r 1) / 2 + ··· + A p r x p r 1 + ··· )
·
( x 3( p− 1) p r / 2 +
+ A p r
x p r ( p− 1) +
···
···
) .
p
To obtain the coe cient of x p r +1
1 , choose indices i and j with i + j =
p r +1
1, multiply the corresponding coe cients from the first and second
factors in the above product, and sum over all such pairs i, j . A term with
0 ≤ i ≤ 3( p r
1) / 2 from the first factor requires a term with
3
p r +1
( p r +1
2 ( p r
2) p r
1
j
1)
1) > ( p
from the second factor. Since all of the exponents in the second factor are
multiples of p r , the only index j in this range that has a nonzero exponent
is j =( p − 1) p r . The corresponding index i is p r
1. The product of the
coecients yields
A p r +1 = A p r A p p .
The formula of the lemma is trivially true for r = 1. It now follows by an
easy induction for all r .
From the lemma, we now see that E is supersingular if and only if A p =0.
This is significant progress, since A p depends on p but not on which power of
p is used to get q .
Search WWH ::




Custom Search