Cryptography Reference
In-Depth Information
> phi := (1+sqrt(5))*(1/2):
> evalb(evalf(phi) < F(3));
true
> evalb(evalf(phiˆ2) < F(4));
true
is the positive root of the quadratic equation
x
2
Now
ϕ
−
x
−
1
=
0, so that
2
n
−
4
gives the identity
n
−
2
it satisfies
ϕ
=
ϕ
+
1 which, multiplying by
ϕ
ϕ
=
n
−
3
n
−
4
. Our induction hypothesis is then that both
n
−
4
ϕ
+
ϕ
ϕ
<
F
n
−
2
and
n
−
3
n
−
3
n
−
4
n
−
2
ϕ
<
F
n
−
1
hold. Adding these inequalities we obtain
ϕ
+
ϕ
=
ϕ
<
F
n
, completing the inductive proof. If applying the Euclidean
algorithm to
a
and
b
takes
n
steps, we see from Theorem 2.5 that
b
F
n
−
2
+
F
n
−
1
=
≥
F
n
+
1
n
−
1
. Taking logarithms we
and, by the preceding inequality, we have that
b
>ϕ
obtain log
b
>
n
−
1.
ϕ
1
(use the same induction as
in the proof of the preceding theorem, where the first of these two inequalities has
already been proved).
n
−
2
n
−
Exercise 2.8
Show that, for
n
≥
3,
ϕ
<
F
n
<ϕ
Lamé's theorem is also sometimes stated as follows:
the number of division oper-
ations needed by the Euclidean algorithm to find the
gcd
of two positive integers is no
more than five times the number of decimal digits of the smaller of the two numbers
[194]. This follows from Theorem 2.6 which tells us that if the number of steps is
n
then
n
−
1
<
log
b
(where
b
is the smaller of the two numbers). We also have
ϕ
that log
b
=
log
10
b
/
log
10
ϕ
and, since log
10
ϕ>
0
.
2 we obtain
n
−
1
<
5log
10
b
.
ϕ
Then, if
b
has
k
decimal digits, we have that log
10
b
<
k
and so we get
n
−
1
<
5
k
fromwhich it follows, taking into account that both
n
and
k
are integers, that
n
5
k
.
Now, the complexity of the Euclidean algorithm is an easy consequence of Lamé's
theorem:
≤
Theorem 2.7
The complexity of the Euclidean algorithm applied to integers a, b is
O
(
len
(
a
)
len
(
b
))
.
Proof
We can assume that
a
0 (if this is not the case, then it will be after just
one iteration). With the notation previously used, let
>
b
>
(
r
i
)
2
≤
i
≤
n
+
1
be the remainder
sequence and
q
i
)
2
≤
i
≤
n
the corresponding quotient sequence. The computation of
r
i
+
1
by means of an integer division such that
r
i
−
1
=
(
r
i
q
i
+
r
i
+
1
(with 1
≤
i
≤
n
)
requires time
O
(
len
(
r
i
)
len
(
q
i
))
as we have already remarked. Since
r
i
≤
b
we have
that len
(
r
i
)
≤
len
(
b
)
for 1
≤
i
≤
n
+
1 and, on the other hand, len
(
q
i
)
≤
1
+
log
2
q
i
.
Thus the time taken by the Euclidean algorithm on input
(
a
,
b
)
can be estimated as
O
n
O
len
n
n
1
(
len
(
b
)(
1
+
log
2
q
i
))
=
(
b
)
+
log
2
q
i
.
i
=
i
=
1
Now, it follows from Theorem 2.6 that
n
=
O
(
len
(
b
))
and, on the other hand,
a
=
r
0
=
r
1
q
1
+
r
2
≥
r
1
q
1
=
(
r
2
q
2
+
r
3
)
q
1
≥
r
2
q
2
q
1
≥ ··· ≥
q
n
q
n
−
1
...
q
1
, which
