Cryptography Reference
In-Depth Information
Theorem A.31
(
Continued Fractions and Recursion)
Let
D
be a positive integer that is not a perfect square, and let
α
0
=(
P
0
+
√
D
)
/Q
0
be a quadratic irrational. Recursively define the following for
k
≥
0
:
α
k
=(
P
k
+
√
D
)
/Q
k
,
(A.5)
q
k
=
α
k
,
(A.6)
P
k
+1
=
q
k
Q
k
−
P
k
,
(A.7)
and
P
k
+1
)
/Q
k
.
Q
k
+1
=(
D
−
(A.8)
Then
P
k
,Q
k
∈
Z
and
Q
k
=0
for
k
≥
0
, and
α
k
=
q
k
;
q
k
+1
,...
.
Proof
. See [167, Exercise 5.3.6, page 251].
✷
Theorem A.32
(
Co
ntinued Fractions and Quadratic Irrationals
)
Let
α
=(
P
+
√
D
)
/Q
be a quadratic irrational and set
G
k
−
1
=
Q
0
A
k
−
1
−
P
0
B
k
−
1
(
k
≥−
1)
,
where
A
k
−
1
,
B
k
−
1
are given in Theorem A.28 on page 496. Then
G
k
−
1
−
B
k
−
1
D
=(
1)
k
Q
k
Q
0
−
(
k
≥
1)
.
(A.9)
Proof
. See [167, Theorem 5.3.4, page 246].
✷
Corollary A.3
If
α
=
√
D
, then Equation
(A.9)
becomes
A
k
−
1
−
B
k
−
1
D
=(
1)
k
Q
k
.
−
(A.10)
Proof
. See [167, Corollary 5.3.3, page 249].
✷
A.8 Elliptic Curves
We now summarize some basic facts needed for understanding the crypto-
graphic schemes described in this text such as the ElGamal cryptosystem on
page 190. We begin with the basic definition.
Definition A.44
(
Elliptic Curves)
Let
F
be a field with characteristics not equal to
2
or
3
.If
a,b
∈
F
are given
such that
4
a
3
+27
b
2
=0
in
F
, then an
elliptic curve
E
defined over
F
is given
by an equation
y
2
=
x
3
+
ax
+
b
∈
F
[
x
]
. The set of all solutions
(
x,y
)
∈
F
to
the equation:
y
2
=
x
3
+
ax
+
b,
(A.11)
together with a point
o
, called the
point at infinity
, is denoted by
E
(
F
)
, called
the set of
F
-rational points on
E
. The value
∆(
E
)=
16(4
a
3
+27
b
2
)
is called
−
the
discriminant of the elliptic curve
E
.
Search WWH ::
Custom Search