Cryptography Reference
In-Depth Information
a
b
+
p
k
z
a
To prove it, simply rewrite the difference
b
.(
Technical point:
This
actually should say that
a/
(
b
+
O
(
p
k
)) can be changed to (
a/b
)+
O
(
p
k
). The
problem with “=” is that the right side sometimes cannot be changed back
to the left side; for example, let the right side be 0 with
a
=
−
p
k
.)
−
P
2
=(
p −
1)
P
=(
u, v
), with
u, v ∈
Q
(this is not yet mod
p
2
). Then
Write
u
=
x
+
O
(
p
2
)
,
v
=
y
+
O
(
p
2
)
.
Let
(
x, y
)=
P
1
=
p P
=
P
+
P
2
=(
x
1
,y
1
)+(
u, v
)
.
Then
x
=
v
2
− u − x
1
=
y
−
2
y
1
+
O
(
p
2
)
−
y
1
− u − x
1
.
u
−
x
1
x
−
x
1
+
O
(
p
2
)
P
1
∈
E
1
and usually we have
P
1
E
2
. This means that
x
− x
1
We have
∈
is a multiple of
p
, but not of
p
2
(note:
y
≡
y
1
(mod
p
) since otherwise
(
p
−
1)
P
=
P
, which is not the case). We'll assume this is the case. Then
y
−
y
1
+
O
(
p
2
)
x
−
y
−
y
1
+
O
(
p
2
)
x
− x
1
+
O
(
p
2
)
1
p
=
x
1
+
O
(
p
)
p
y
−
+
O
(
p
)
1
p
y
1
=
x
−
x
1
p
1
p
m
1
+
O
(
p
0
)
.
=
Note that
v
p
(
m
1
) = 0. Since
v
p
(
u
)
≥
0and
v
p
(
x
1
)
≥
0, we obtain
x
=
1
p
m
1
+
O
(
p
0
)
2
− u − x
1
=
m
1
+
O
(
p
−
1
)
.
p
2
P
1
satisfies
Similarly, the
y
-coordinate of
m
1
p
3
+
O
(
p
−
2
)
.
y
=
−
Therefore,
1
=
λ
1
(
P
1
)=
λ
1
(
x, y
)=
p
−
1
x
1
m
1
+
O
(
p
)
1
m
1
=
−
≡−
(mod
p
)
.
y
Similarly,
1
m
2
2
=
λ
1
(
Q
1
)
≡−
(mod
p
)
.
Search WWH ::
Custom Search