Cryptography Reference
In-Depth Information
Q
2
=(
p
1)
Q
(
x
,y
)(mod
p
2
).
3. Calculate
−
≡
4. Compute
m
1
=
p
y
−
m
2
=
p
y
−
y
1
y
2
x
− x
1
,
x
− x
2
.
E
. Otherwise,
Q
=
kP
,
5. If
v
p
(
m
2
)
<
0or
v
p
(
m
1
)
<
0, then try another
where
k ≡ m
1
/m
2
(mod
p
).
Example 5.5
Let
E
be the elliptic curve given by
y
2
=
x
3
+108
x
+4 over
F
853
.Let
P
=(0
,
2)
and
Q
= (563
,
755). It can be shown that 853
P
=
∞
. Since 853 is prime, the
order of
P
is 853, so 853
#
E
(
F
853
). Hasse's theorem implies that #
E
(
F
853
)=
853, as in Section 4.3.3. Therefore,
E
is anomalous. Proposition 5.6 yields
|
E
:
y
2
=
x
3
+ 7522715
x
+4
,
P
=(0
,
2)
,
Q
= (563
,
66436)
.
We have
P
2
= 852
P ≡
(159511
,
58855)
(mod 853
2
)
Q
2
= 852
Q ≡
(256463
,
645819)
(mod 853
2
)
.
Note that even with a prime as small as 853, writing
P
2
without reducing
mod 853
3
would require more than 100 thousand digits. We now calculate
m
1
= 853
58855
−
2
and
m
2
= 853
645819
−
66436
256463
−
563
159511
−
0
=
58853
=
58853
187
.
187
Therefore,
k ≡ m
1
/m
2
≡
234 (mod 853).
Let's prove this algorithm works (the proof consists mostly of keeping track
of powers of
p
, and can be skipped without much loss). The following notation
is useful. We write
O
(
p
k
) to represent a rational number of the form
p
k
z
with
v
p
(
z
)
≥
0. Therefore, if
a, b ∈
Z
and
k>
0, then
a
=
b
+
O
(
p
k
)simply
means that
a ≡ b
(mod
p
k
). But we are allowing rational numbers and we
are allowing negative
k
. For example,
49
=
23
1
98
+
O
(7
−
1
)
since
23
98
=
49
+
1
1
3
2
.
7
The following rule is useful:
b
+
O
(
p
k
)
=
a
a
b
+
O
(
p
k
)when
v
p
(
b
)=0
,v
p
(
a
)
≥
0
,
and
k>
0
.
Search WWH ::
Custom Search