Cryptography Reference
In-Depth Information
Division with remainder in
[
π
].
This method was proposed by Meier and Staffelbach and is also used by Solinas (Section
5.1 of [
517
]). Since (
π
m
Z
−
1)(
P
)
=
O
E
when
P
∈
E
(
F
q
m
) one wants to determine the
remainder of dividing
n
by (
π
m
n/
(
π
m
−
1). The method is to consider the element
γ
=
−
[
π
]
/
(
π
2
1)
∈ R
−
tπ
+
q
) and find a close vector to it (using Babai rounding) in the lattice
Z
[
π
]. In other words, write
γ
=
γ
0
+
γ
1
π
with
γ
0
,γ
1
∈ R
and round them to the nearest
integers
g
0
,g
1
(in the special case of
π
2
0, there is an exact description of
a fundamental domain for the lattice that can be used to “correct” the Babai rounding
method if it does not reach the closest lattice element). Lemma 3 of [
373
] and Proposition
57 of [
517
] state that N(
γ
±
π
+
2
=
−
(
g
0
+
≤
g
1
π
))
4
/
7. One can then define
g
1
π
)(
π
m
1) (mod
π
2
n
0
+
n
1
π
=
n
−
(
g
0
+
−
−
tπ
+
q
)
.
The Gallant-Lambert-Vanstone method [
216
].
This method appears in a different context (see Section
11.3.3
), but it is also suitable for
the present application. We assume that
P
∈
F
q
m
) has prime order
r
where
r
F
q
m
).
E
(
#
E
(
Since
π
(
P
)
∈
E
(
F
q
m
) has order
r
it follows that
π
(
P
)
=
[
λ
]
P
for some
λ
∈ Z
/r
Z
.The
problem is therefore to find small integers
n
0
and
n
1
such that
n
0
+
n
1
λ
≡
n
(mod
r
)
.
One defines the
GLV lattice
2
L
={
(
x
0
,x
1
)
∈ Z
:
x
0
+
x
1
λ
≡
0(mod
r
)
}
.
A basis for
L
is given in Exercise
11.3.22
. The idea is to find a lattice vector (
n
0
,n
1
)
∈
L
n
1
|
n
0
|
n
0
close to (
n,
0). Then
|
is “small” and
|
n
−
is “small”. Define
n
0
=
n
−
and
n
1
n
1
=−
so that
n
0
+
n
1
λ
≡
n
(mod
r
)
as required.
We can compute a reduced basis for the lattice and then use Babai rounding to solve the
closest vector problem (CVP). Note that the reduced basis can be precomputed. Since the
dimension is two, one can use the Gauss lattice reduction algorithm (see Section
17.1
).
Alternatively, one can use Euclid's algorithm to compute (
n
0
,n
1
) directly (as discussed
in Section
17.1.1
, Euclid's algorithm is closely related to the Gauss algorithm).
Example 11.3.14
The elliptic curve
E
:
y
2
x
3
x
2
+
xy
=
+
+
1 over
F
2
19
has 2
r
points
(
x
2
,y
2
). Then
π
2
where
r
=
262543 is prime. Let
π
(
x,y
)
=
−
π
+
2
=
0. Let
n
=
123456. We want to write
n
as
n
0
+
n
1
π
on the subgroup of
E
(
F
2
19
) of order
r
.
For the “division with remainder in
Z
[
π
]” method we first use Lucas sequences (as in
Exercise
9.10.9
) to determine that
π
19
−
1
=−
(171
+
457
π
)
