Cryptography Reference
In-Depth Information
until there is a match
Q
+
k
(2
mP
)=
±
jP
with a point (or its negative)
on the stored list.
4. Conclude that (
q
+1+2
mk
∓
j
)
P
=
∞
.Let
M
=
q
+1+2
mk
∓
j
.
5. Factor
M
.Let
p
1
,...,p
r
be the distinct prime factors of
M
.
6. Compute (
M/p
i
)
P
for
i
=1
,...,r
.If(
M/p
i
)
P
=
∞
for some
i
, replace
M
with
M/p
i
and go back to step (5). If (
M/p
i
)
P
=
∞
for all
i
then
M
is the order of the point
P
.
7. If we are looking for the #
E
(
F
q
), then repeat steps (1)-(6) with ran-
domly chosen points in
E
(
F
q
) until the least co
m
mon multiple of t
he
orders divides only one integer
N
with
q
+1
2
√
q
q
+1+2
√
q
.
−
≤
N
≤
Then
N
=#
E
(
F
q
).
There are two points that must be addressed.
I. Assuming that there is a match, this method clearly produces an integer
that annihilates
P
. But why is there a match?
LEMMA 4.20
Let
a
be an integer w ith
|a|≤
2
m
2
.The eex st integers
a
0
and
a
1
with
−m<a
0
≤ m
and
−m ≤ a
1
≤ m
su ch that
a
=
a
0
+2
ma
1
.
PROOF
Let
a
0
≡
a
(mod 2
m
), with
−
m<a
0
≤
m
and
a
1
=(
a
−
a
0
)
/
2
m
.
Then
(2
m
2
+
m
)
/
2
m<m
+1
.
|
a
1
|≤
Let
a
=
a
0
+2
ma
1
be as in the lemma and let
k
=
−
a
1
.Then
Q
+
k
(2
mP
)=(
q
+1
−
2
ma
1
)
P
=(
q
+1
− a
+
a
0
)
P
=
NP
+
a
0
P
=
a
0
P
=
±jP,
where
j
=
|
a
0
|
. Therefore, there is a match.
II. Why does step (6) yield the order of
P
?
LEMMA 4.21
Let
G
be an additive group (w ithidentitye em ent 0) and let
g ∈ G
.Suppose
Mg
=0
for som e positive integer
M
.Let
p
1
,...,p
r
be the distinct primes
dividing
M
.If
(
M/p
i
)
g
=0
for all
i
,then
M
isthe order of
g
.
Search WWH ::
Custom Search