Cryptography Reference
In-Depth Information
We have (
a/b
)
2
+1
(
c/d
)
2
+1 (mod
p
), so
a/b
PROOF
≡
0
≡
≡±
(
c/d
). By
changing the sign of
c
if necessary, we may assume that
a/b
≡
c/d
(mod
p
),
hence
ad
−
bc
≡
0(mod
p
). A quick calculation shows that
p
2
=(
ac
+
bd
)
2
+(
bc − ad
)
2
.
(4.2)
Suppose
ad
=
bc
. Then (4.2) implies that
ac
+
bd
=
±p
,so
ap
=
a
2
c
+
abd
=
a
2
c
+
b
2
c
=
pc.
±
Hence,
±a
=
c
. It follows that
b
=
±d
.
Now suppose
ad
=
bc
.Since
ad − bc ≡
0(mod
p
), we have (
ad − bc
)
2
≥ p
2
.
Since (
ac
+
bd
)
2
≥
0, it follows from (4.2) that
ad − bc
=
±p
and
ac
+
bd
=0.
Therefore,
±cp
=
acd − bc
2
=
−bd
2
− bc
2
=
−bp,
so
c
=
±b
.Thisimpliesthat
d
=
±a
.
If we require that
a
is odd and
b
is even, then
a
and
b
are uniquely deter-
mined up to sign. Suppose
b
≡
2(mod4). Then
a
+
b
≡
1(mod4)fora
unique choice of the sign of
a
. Similarly, if
b
≡
0 (mod 4), there is a unique
choice of the sign of
a
that makes
a
+
b
1 (mod 4). Therefore, the integer
a
in the lemma is uniquely determined by
p
if we require that
a
is odd and
a
+
b ≡
1(mod4).
The main part of the proof of Theorem 4.23 involves the case
p ≡
1(mod4),
so let's treat the case
p ≡
3 (mod 4) first.
≡
The main point is that
−
1is
not a square mod
p
(
Proof:
if
x
2
≡−
1, then 1
≡ x
p−
1
≡
(
x
2
)
(
p−
1)
/
2
≡
1)
odd
1)
(
p−
1)
/
2
(
1, contradiction). Moreover, a nonsquare times
anonsquareisasquaremod
p
. Therefore
x
3
−
≡
(
−
=
−
− kx
isanonzerosquaremod
p
ifandonlyif(
−x
)
3
− k
(
−x
)=
−
(
x
3
− kx
) is not a square mod
p
.Let's
count points on
E
. Whenever
x
3
− kx
= 0, we obtain one point (
x,
0). For
the remaining values of
x
,wepairup
x
and
−x
.
One of these gives two
points (the one that makes
x
3
− kx
a square) and the other gives no points.
Therefore, each pair
x, −x
gives two points. Therefore, we obtain a total of
p
points. The point
∞
gives one more, so we have
p
+1points.
1 (mod 4). The proof, which takes the rest of this sec-
tion, involves several steps and counts the points in terms of Jacobi sums.
Rather than count the points on
E
directly, we make the transformation (see
Theorem 2.17)
Now assume
p
≡
x
=
2(
v
+1)
u
2
y
=
4(
v
+1)
u
3
,
,
which changes
E
into the curve
C
given by
v
2
=(
k/
4)
u
4
+1
.
The inverse transformation is
u
=
2
x
y
1+
2
x
3
y
2
,
v
=
−
.
Search WWH ::
Custom Search