Cryptography Reference
In-Depth Information
1. Choose a se
t
of primes
S
=
{
2
,
3
,
5
,...,L
}
(with
p
∈
S
) such that
∈S
>
4
√
q
.
2. If
=2,wehave
a ≡
0 (mod 2) if and only if gcd(
x
3
+
Ax
+
B, x
q
−x
)
=
1.
3. For each odd prime
∈
S
, do the following.
(a) Let
q
≡ q
(mod
)with
|q
| </
2.
(b) Compute the
x
-coordinate
x
of
(
x
,y
)=
x
q
2
,y
q
2
+
q
(
x, y
)mod
ψ
.
(c) For
j
=1
,
2
,...,
(
−
1)
/
2, do the following.
i. Compute the
x
-coordinate
x
j
of (
x
j
,y
j
)=
j
(
x, y
).
ii. If
x
− x
j
≡
0(mod
ψ
), go to step (iii). If not, try the next
value of
j
(in step (c)). If all values 1
≤ j ≤
(
−
1)
/
2have
been tried, go to step (d).
iii. Compute
y
and
y
j
.If(
y
− y
j
)
/y ≡
0(mod
ψ
), then
a ≡ j
(mod
). If not, then
a ≡−j
(mod
).
(d) If all values 1
≤ j ≤
(
−
1)
/
2 have been tried without success, let
w
2
≡ q
(mod
). If
w
does not exist, then
a ≡
0(mod
).
(e) If gcd(numerator(
x
q
− x
w
)
,ψ
)=1,then
a ≡
0(mod
). Other-
wise, compute
gcd(numerator((
y
q
− y
w
)
/y
)
,ψ
)
.
If this gcd is not 1, then
a
≡
2
w
(mod
). Otherwise,
a
≡−
2
w
(mod
).
4. Use the knowledge of
a
(mod
)foreach
∈ S
to compute
a
(mod
).
Ch
o
ose the value of
a
that satisfies this congruence and such that
|a|≤
2
√
q
. The number of points in
E
(
F
q
)is
q
+1
−
a
.
Example 4.13
Let
E
be the elliptic curve
y
2
=
x
3
+2
x
+ 1 mod 19. Then
#
E
(
F
19
)=19+1
−
a.
We want to determine
a
. We'll show that
⎧
⎨
1(mod )
2(mod )
3(mod
.
a ≡
⎩
Search WWH ::
Custom Search