Cryptography Reference
In-Depth Information
Lemma 1 (Legendre).
Let
ξ
be a real number. If the coprime integers
X
and
Y
satisfy
X
Y
1
2
Y
2
,
ξ
−
<
then
Y
is a convergent of
ξ
.
Now we show the proof of Theorem 5, which is similar to the proof of Theorem
4in[1].
Proof.
We have (
ρq
2
√
ρN
)(
p
+
ρq
+
p
)
2
=
N
2
θ
=(
p
+
ρq
)
2
−
−
4
ρN
=(
p
+
ρq
−
2
√
ρN
), hence
2
ρN
=
N
2
θ
(
p
+
ρq
+2
√
ρN
)
<
N
2
θ
4
√
N
.
p
+
ρq
−
Rearrange the terms in (9), we have
ex
+
y
=
k
(
N
+1
−
p
−
[
ρq
])
.
√
ρN
√
ρN
Let
z
=2
−
p
−
[
ρq
], and
M
=
N
+1
−
2
. Then by the above, we
have that
ex
+
y
=
k
(
M
+
z
)
,
(10)
and
e
M
−
k
x
=
kz
y
Mx
−
.
(11)
Here we can assume gcd(
k, x
) = 1. Since if gcd(
k, x
)=
t
,wehavethat
t
divides
y
, which gives us an equation
ex
+
y
=0(mod
M
+
z
) with even smaller
parameters
x
and
y
. Hence we can assume that
k
x
is a fraction in its lowest
terms.
By Lemma 1, the fraction
x
is among the convergents of the continued fraction
expansion of
e
M
e
k
1
2
x
2
if
|
M
−
x
|
<
is satisfied. Thus it remains to show that
kz
−
y
1
2
x
2
.
<
Mx
1
We have
|
y
|≤
4
ex
and
ex
φ
(
N
)
,
where the last inequality holds for
N>
288. Wlog we assume
N>
288 during
the proof of the theorem. We have
3
4
ex
φ
(
N
)
≤
ex
+
y
M
≤
6
4
k
=
4
N
2
θ−
2
1
|
z
|≤
and
6
4
ex
φ
(
N
)
1
ex
4
N
2
θ−
2
+
N
θ−
4
x
φ
(
N
)
N
2
θ−
2
.
|
kz
−
y
|≤|
kz
|
|
y
|≤
≤
+
Therefore we have to satisfy
ex
φ
(
N
)
N
2
θ−
2
1
Mx
<
1
2
x
2
.
φ
(
N
)
e
N
4
|ρq−p|
1
3
This holds by our upper bound
x
≤
and
N>
288.
Search WWH ::
Custom Search