Cryptography Reference
In-Depth Information
2
n
. The idea is to compute the
coefficients of the polynomial
c
using polynomial interpolation and therefore to recover
c
. The arithmetic is fast if the polynomials are evaluated at small integer values. Hence,
we compute
c
(1)
which is a polynomial of degree 2
k
in
x
evaluated at
x
=
a
(2)
b
(2) etc. The complexity
of Toom-Cook multiplication for
n
-bit integers is
O
(
n
log
k
+
1
(2
k
+
1)
) (e.g., when
k
=
a
(1)
b
(1),
c
(
−
1)
=
a
(
−
1)
b
(
−
1),
c
(2)
=
=
3the
complexity is
O
(
n
1
.
465
)). For more details see Section 9.5.1 of [
150
].
Exercise 2.2.4
Give an algorithm for Toom-Cook multiplication with
k
=
3.
Schonhage-Strassen multiplication
multiplies
n
-bit integers in nearly linear time,
namely
O
(
n
log(
n
) log(log(
n
))) bit operations, using the fast Fourier transform (FFT).
The F urer algorithm is slightly better. These algorithms are not currently used in the
implementation of RSA or discrete logarithm cryptosystems so we do not describe them
in this topic. We refer to Sections 9.5.2 to 9.5.7 of [
150
], Chapter 8 of [
220
], Chapter 2 of
[
95
], [
549
] and Chapter 4 of [
83
] for details.
Remark 2.2.5
In practice, the “school” method is fastest for small numbers. The crossover
point (i.e., when Karatsuba becomes faster than the school method) depends on the word size
of the processor and many other issues, but seems to be for numbers of around 300-1000
bits (i.e., 90-300 digits) for most computing platforms. For a popular 32 bit processor,
Zimmermann [
575
] reports reports that Karatsuba beats the school method for integers
of 20 words (640 bits) and Toom-Cook with
k
3 beats Karatsuba at 77 words (2464
bits). Bentahar [
40
] reports crossovers of 23 words (i.e., about 700 bits) and 133 words
(approximately 4200 bits) respectively. The crossover point for the FFT methods is much
larger. Hence, for elliptic curve cryptography at current security levels the “school” method
is usually used, while for RSA cryptography the Karatsuba method is usually used.
=
Definition 2.2.6
Denote by
M
(
n
) the number of bit operations to perform a multiplication
of
n
bit integers.
c
1
n
2
For the remainder of the topic we assume that
M
(
n
)
=
for some constant
c
1
when
c
2
n
1
.
585
for some constant
c
2
when
talking about elliptic curve arithmetic, and that
M
(
n
)
=
talking about RSA .
Applications of Newton's method
Recall that if
F
:
is differentiable and if
x
0
is an approximation to a zero of
F
(
x
)
then one can efficiently get a very close approximation to the zero by running Newton's
iteration
R → R
F
(
x
n
)
/F
(
x
n
)
.
x
n
+
1
=
x
n
−
Newton's method has quadratic convergence, in general, so the precision of the approxi-
mation roughly doubles at each iteration.
