Cryptography Reference
In-Depth Information
Example 2.3.4
The first few terms of Euclid's algorithm on
a
=
513 and
b
=
311 give
i
r
i
q
i
s
i
t
i
|
r
i
s
i
| |
r
i
t
i
|
−
1
513
-
1
0
513
0
0
311
-
0
1
0
311
1
202
1
1
−
1
202
202
2
109
1
−
1
2
109
218
3 31
2
−
3
186
279
4 61
−
3
5
48
80
5 35 7
−
28
221
364
One can verify that
|
r
i
s
i
|≤|
b
|
and
|
r
i
t
i
|≤|
a
|
. Indeed,
|
r
i
s
i
+
1
|≤|
b
|
and
|
r
i
t
i
+
1
|≤|
a
|
as stated in part 6 of Lemma
2.3.3
.
Diophantine approximation is the study of approximating real numbers by rationals.
Statement 7 in Lemma
2.3.3
is a special case of one of the famous results; namely,
that the “best” rational approximations to real numbers are given by the convergents in
their continued fraction expansion. Lemma
2.3.5
shows how the result can be relaxed
slightly, giving “less good” rational approximations in terms of convergents to continued
fractions.
<c/s
2
. Then
Lemma 2.3.5
Let α
∈ R
, c
∈ R
>
0
and let s,t
∈ N
be such that
|
α
−
t/s
|
=
(
uh
n
+
1
±
vh
n
,uk
n
+
1
±
∈ Z
≥
0
such that uv <
2
c.
(
t,s
)
vk
n
)
for some n,u,v
Proof
See Theorem 1 and Remark 2 of Dujella [
170
].
2.4 Computing Legendre and Jacobi symbols
The Legendre symbol tells us when an integer is a square modulo
p
. It is a non-trivial group
homomorphism from (
)
∗
to the multiplicative group
Z
/p
Z
{−
1
,
1
}
.
.The
Legendre symbol
(
p
)is
Definition 2.4.1
Let
p
be an odd prime and
a
∈ Z
a
p
if
x
2
1
≡
a
(mod
p
) has a solution
=
0
if
p
|
a
−
1
otherwise
.
satisfies (
p
)
1 then
a
is a
quadratic residue
, while if (
p
)
If
p
is prime and
a
∈ Z
=
=−
1
then
a
is a
quadratic non-residue
.
