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