Cryptography Reference
In-Depth Information
(one can think of this as equality of complex numbers where
π
is a root of
x
2
−
x
+
2,
or as congruence of polynomials modulo
π
2
−
π
+
2). It is convenient to change the sign
(the method works in both cases). The norm of 171
+
457
π
is #
E
(
F
2
19
)
=
2
r
=
525086.
and so
n
n
(171
457
π
)
525086
+
1
=
≈
147
.
653
−
107
.
448
π.
−
π
19
+
(since
π
=
1
−
π
). Rounding gives 148
−
107
π
and
440
π
(mod
π
2
n
−
(148
−
107
π
)(171
+
457
π
)
≡
350
−
−
π
+
2)
.
This is a short representative for
n
, but its norm is larger than 8
r/
7, which is not optimal.
Section 5.1 of Solinas [
517
] shows how to choose a related element of smaller norm. In
this case, the correct choice of rounding is 147
−
107
π
giving
17
π
(mod
π
2
n
−
(147
−
107
π
)(171
+
457
π
)
≡
521
+
−
π
+
2)
,
which has norm less than 8
r/
7.
Now for the Gallant-Lambert-Vanstone method. We compute gcd(
x
19
1
,x
2
−
−
x
+
2)
=
(
x
−
λ
)in
F
r
[
x
], where
λ
=
84450. The lattice with (row) basis
r
0
−
λ
1
has LLL (or Gauss) reduced basis
171
.
457
B
=
−
457
314
Writing
b
1
,
b
2
for the rows of the reduced matrix one finds (
n,
0)
≈
147
.
65
b
1
+
214
.
90
b
2
.
One computes
(
n,
0)
−
(148
,
215)
B
=
(
−
107
,
−
126)
.
One can verify that
−
107
−
126
λ
≡
n
(mod
r
). (Exercise
11.3.16
shows how to get this
element using remainders in
[
π
].) The corresponding Frobenius expansion can be obtained
from the solution to Exercise
11.3.10
.
Z
Exercise 11.3.15
Prove that both the above methods yield an element
n
0
+
n
1
π
∈ Z
[
π
]
that is equivalent to
n
.
Exercise 11.3.16
Show that if
P
∈
E
(
F
q
m
)but
P
∈
E
(
F
q
) then instead of computing the
[
π
] modulo the polynomial (
π
m
1) one can use (
π
m
remainder in
Z
−
−
1)
/
(
π
−
1). Repeat
Example
11.3.14
using this polynomial.
In practice, it is unnecessary to determine the minimal solution (
n
0
,n
1
) as long as
n
0
and
n
1
have bit-length roughly
1
2
log
2
(
r
) (where the point
P
has order
r
). We also stress
that computing the
q
-power Frobenius map
π
is assumed to be very fast, so the main task
is to minimise the
weight
of the representation, not its length.
