Cryptography Reference
In-Depth Information
First,
√
q
1
2
4
√
qx
implies that
x>
√
q
2
/
4. Second,
−
≤
n
2
x
≤
−
≤ n
2
y ≤
√
q
+1
2
.Third,
xy
2
=(
xy
)
y ≤ n
2
y ≤
√
q
+1
2
. Finally,
y
2
n
1
|
1.
Therefore, we should look for values of
q
q
−
1 (by Corollary 3.11), so
x, y
|
q
−
≤
4612 that are primes or prime
powersandsuchthat
q
−
1 has divisors
x, y
with
1. gcd(
x, y
)=1
2.
√
q −
2
/
4
<x<y≤
√
q
+1
≤
√
q
+1
2
.
3.
xy
2
The values of
q
for which such
x, y
exist are those on the list in the statement
of the theorem, plus the five values
q
=49
,
81
,
121
,
169
,
841. Therefore, for
all other
q
,anumber
n
2
cannot have two possible values
x, y
for
n
1
,so
n
1
is
uniquely determined.
We need to eliminate the remaining five values. For example, consider
q
= 49. One solution is
x
=2
,y
=3
,n
2
= 18, which corresponds to #
E
(
F
q
)=
36 and 54. By Theorem 4.4, or by Exercise 4.14, if #
E
(
F
q
)=
√
q
1
2
,
−
then
E
(
F
q
)
Z
√
q−
1
. Therefore, if #
E
(
F
49
) = 36, we must have
n
1
=
n
2
= 6. This arises from
x
= 2 after multiplying by 3 (recall that
we removed
d
=gcd(
x, y
)from
x, y
in order to make them relatively prime).
Multiplying
y
=3by
d
= 3 yields
n
1
=9
,n
2
= 6, which does not satisfy
n
1
|
Z
√
q−
1
⊕
n
2
.
Therefore, the solution
x
=2
,y
=3for
q
= 49 is eliminated. Similarly, all
solutions for all of the five values
q
=49
,
81
,
121
,
169
,
841 can be eliminated.
This completes the proof.
.
4.3.4
Baby Step, Giant Step
E
(
F
q
). We want to find the order of
P
. First, we want to find
an integer
k
such that
kP
=
∞
.Let#
E
(
F
q
)=
N
. By Lagrange's theor
e
m,
Let
P
∈
NP
=
∞
. Of co
ur
se, we might not know
N
yet, but we know that
q
+1
−
2
√
q ≤
N ≤ q
+1+2
√
q
. We could try all values of
N
in this range and see which
ones satisfy
NP
=
∞
. This takes around 4
√
q
steps. However, it is possible
to speed this up to around 4
q
1
/
4
steps by the following algorithm.
1. Compute
Q
=(
q
+1)
P
.
2. Choose an integer
m
with
m>q
1
/
4
. Compute and store the points
jP
for
j
=0
,
1
,
2
,...,m
.
3. Compute the points
Q
+
k
(2
mP
)for
k
=
−m, −
(
m −
1)
,...,m
Search WWH ::
Custom Search