Cryptography Reference
In-Depth Information
an elliptic curve addition). However, the idea is to represent an integer by a polynomial in
π . For example, one can verify that
T 5
T 3
9(mod T 2
+
+
1
+
T
+
2)
π 5 ( P )
and so one can compute [9] P (normally taking 3 doublings and an addition) as
+
π 3 ( P )
+
P using only two elliptic curve additions.
This idea can be extended to any algebraic group G (in particular, elliptic curves, divisor
class groups of hyperelliptic curves and algebraic tori) that is defined over a field
F q but
for which one works in the group G (
F q m ).
= l i = 0 a i π i ( P )isa
Exercise 11.3.4
Give an algorithm to compute [ a ] P when a
Frobenius expansion. What is the cost of the algorithm?
= l i = 0 a i π i
Definition 11.3.5 Let S
⊆ Z
such that 0
S and if a
S then
a
S .Let a
be a Frobenius expansion with a i
S . Then a is in non-adjacent form if a i a i + 1 =
0for
all 0
i<l . Such an expansion is also called a π -NAF .
An important task is to convert an integer n into a Frobenius expansion in non-adjacent
form. In fact, to get short expansions we will need to convert a general element n 0 +
n 1 π
to a π -NAF, so we study the more general problem. The crucial result is the following.
Lemma 11.3.6 Let π satisfy π 2
+
=
0 . An element n 0 +
Z
q
n 1 π in
[ π ] is divisible
by π if and only if q
|
n 0 . In this case
( n 0 +
n 1 π )
=
( n 1 +
tn 0 /q )
+
π (
n 0 /q ) .
(11.1)
Similarly, it is divisible by π 2
tn 0 (mod q 2 ) .
if and only if q
|
n 0 and qn 1 ≡−
Proof Note that π 2
=
q . Since
π ( m 0 +
m 1 π )
=−
qm 1 +
π ( m 0 +
tm 1 )
it follows that n 0 +
n 1 π
=
π ( m 0 +
m 1 π ) if and only if
n 0 =−
qm 1 , and n 1 =
m 0 +
tm 1 .
Writing m 1 =−
tm 1 yields equation ( 11.1 ).
Repeating the argument, one can divide the element in equation ( 11.1 )by π if and only
if q
n 0 /q and m 0 =
n 1
|
( n 1 +
tn 0 /q ). The result follows.
The idea of the algorithm for computing a π -NAF, given n 0 +
n 1 π , is to add a suitable
integer so that the result is divisible by π 2 ,divideby π 2
and then repeat. This approach is
only really practical when q
=
2, so we restrict to this case.
Lemma 11.3.7 Let π 2
+
2
=
0 where t
1 . Then n 0 +
n 1 π is either divisible by
π or else there is some
1 such that
0(mod π 2 ) .
( n 0 +
)
+
n 1 π
Indeed,
=
( n 0 +
2 n 1 (mod 4))
2 if one defines n 0 +
2 n 1 (mod 4)
∈{
1 , 3
}
.
Search WWH ::




Custom Search