Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Complexity and Cryptography
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
https://www-alg.ist.hokudai.ac.jp/∼thomas/COCRB/

Lecture 1: Addition, Multiplication

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Motivation I

This course mainly deals with sequential computations. That is,within our underlying model, one and only one bit operation
can be performed in one time step. So, we identify the timecomplexity with the number of bit operations to be performed.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Motivation I

This course mainly deals with sequential computations. That is,within our underlying model, one and only one bit operation
can be performed in one time step. So, we identify the timecomplexity with the number of bit operations to be performed.
For many problems often quite different algorithms are known
that solve them. Thus, one has to compare these algorithms inorder to make a qualified choice which algorithm to use.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Motivation II
We distinguish between the best-case, worst-case and average-caseanalysis of algorithms.
The best-case deals with those inputs on which the algorithm
achieves its fastest running time. The worst-case analysis
provides an upper bound which is never exceeded
independently of the inputs the algorithm is run with. So aworst-case analysis is of particular importance for all
applications that are safety critical.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Motivation II
We distinguish between the best-case, worst-case and average-caseanalysis of algorithms.
The best-case deals with those inputs on which the algorithm
achieves its fastest running time. The worst-case analysis
provides an upper bound which is never exceeded
independently of the inputs the algorithm is run with. So aworst-case analysis is of particular importance for all
applications that are safety critical.
On the other hand, it may well be that those inputs, on which
the considered algorithm achieves its worst-case, occur very
seldom in practice. Provided the application is not safety
critical, one should prefer the algorithm achieving the better
average-case behavior.
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Motivation III

Last but not least, for several applications one also needs
guarantees that there is no algorithm solving a problem quickly
on any input. We shall study such applications in the second
part of our course when dealing with cryptography. But even
without going into any detail here, it should be clear that
deciphering a password must be as difficult on average as in theworst-case.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Motivation IV

We aim to express the complexity as a functions of the size ofthe input. This assumes that inputs are made by using any
reasonable representation for the data on hand. For doing this,
it is advantageous to neglect constant factors. Intuitively, thismeans that we are aiming at results saying that the running
time of an algorithm is proportional to some function.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Motivation IV

We aim to express the complexity as a functions of the size ofthe input. This assumes that inputs are made by using any
reasonable representation for the data on hand. For doing this,
it is advantageous to neglect constant factors. Intuitively, thismeans that we are aiming at results saying that the running
time of an algorithm is proportional to some function.
To formalize this approach, we need the following:N = {0, 1, 2, . . .} is the set of all natural numbers.
We set N+ = N \ {0}.
Z is the set of all integers.
We use Q and R for the set of all rational numbers and real
numbers, respectively.
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Definitions I

The non-negative real numbers are denoted by R>0 .
For all real numbers y we define byc, the floor function, to be thegreatest integer less than or equal to y.
Similarly, dye denotes the smallest integer greater than or equal
to y, i.e., the ceiling function.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Definitions I

The non-negative real numbers are denoted by R>0 .
For all real numbers y we define byc, the floor function, to be thegreatest integer less than or equal to y.
Similarly, dye denotes the smallest integer greater than or equal
to y, i.e., the ceiling function.
Furthermore, for all numbers y ∈ R we write |y| to denote theabsolute value of y.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Order Notations I
Definition 1
Let g : N → R>0 be any function. We define the following sets:(1) O(g(n)) =df {f | f : N → R>0 there are constants c, n0 > 0such that 0 6 f(n) 6 cg(n) for all n > n0 },Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Order Notations I
Definition 1
Let g : N → R>0 be any function. We define the following sets:(1) O(g(n)) =df {f | f : N → R>0 there are constants c, n0 > 0such that 0 6 f(n) 6 cg(n) for all n > n0 },(2) Ω(g(n)) =df {f | f : N → R>0 , there are constants c, n0 > 0such that 0 6 cg(n) 6 f(n) for all n > n0 },Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Order Notations I
Definition 1
Let g : N → R>0 be any function. We define the following sets:(1) O(g(n)) =df {f | f : N → R>0 there are constants c, n0 > 0such that 0 6 f(n) 6 cg(n) for all n > n0 },(2) Ω(g(n)) =df {f | f : N → R>0 , there are constants c, n0 > 0such that 0 6 cg(n) 6 f(n) for all n > n0 },(3) o(g(n)) =df {f | f : N → R>0 , for every constant c > 0
there exists a constant n0 > 0 such that 0 6 f(n) 6 cg(n)for all n > n0 },Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Order Notations I
Definition 1
Let g : N → R>0 be any function. We define the following sets:(1) O(g(n)) =df {f | f : N → R>0 there are constants c, n0 > 0such that 0 6 f(n) 6 cg(n) for all n > n0 },(2) Ω(g(n)) =df {f | f : N → R>0 , there are constants c, n0 > 0such that 0 6 cg(n) 6 f(n) for all n > n0 },(3) o(g(n)) =df {f | f : N → R>0 , for every constant c > 0
there exists a constant n0 > 0 such that 0 6 f(n) 6 cg(n)for all n > n0 },(4) Θ(g(n)) =df {f | f : N → R>0 , there exist constants c1 , c2 ,and n0 > 0 such that 0 6 c1 g(n) 6 f(n) 6 c2 g(n)for all n > n0 }.
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Order Notations II

To indicate that a function f is a member of O(g(n)), we writef(n) = O(g(n)).
We adopt this convention to Ω(g(n)), o(g(n)) and Θ(g(n)).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Order Notations II

To indicate that a function f is a member of O(g(n)), we writef(n) = O(g(n)).
We adopt this convention to Ω(g(n)), o(g(n)) and Θ(g(n)).
Note that the O-notation expresses an asymptotic upper boundwhile the Ω-notation expresses an asymptotic lower bound.
Looking at the definition above, we see that the Θ-notation
establishes an asymptotic tight bound.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

More Notations

Throughout this course, we write log n to denote the logarithm
to the base 2,
ln n to denote the logarithm to the base e (where e is the Euler
number),and logc n to denote the logarithm to the base c.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

More Notations

Throughout this course, we write log n to denote the logarithm
to the base 2,
ln n to denote the logarithm to the base e (where e is the Euler
number),and logc n to denote the logarithm to the base c.
Now, we are ready to study the first algorithms. The basicarithmetic operations, i.e., addition, subtraction, multiplicationand division are of fundamental importance. Therefore, we startwith them.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Addition I
For measuring the complexity of addition, we use the length of
the numbers to be added as the basic complexity parameter.
Thus, in the following we assume as input two n-bit numbers
a = an−1 · · · a0 and b = bn−1 · · · b0 ,where ai , bi ∈ {0, 1} for all i = 0, . . . , n − 1.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Addition I
For measuring the complexity of addition, we use the length of
the numbers to be added as the basic complexity parameter.
Thus, in the following we assume as input two n-bit numbers
a = an−1 · · · a0 and b = bn−1 · · · b0 ,where ai , bi ∈ {0, 1} for all i = 0, . . . , n − 1.
The semantics of these numbers a and b is thenn−1Pa=ai 2i and
i=0

b=

n−1
P

bi 2i .

i=0

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Addition II
We have to compute the sum
s=a+b=nX

si 2i ,si ∈ {0, 1} for all i = 0, . . . , n .

i=0Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Addition II
We have to compute the sum
s=a+b=nX

si 2i ,si ∈ {0, 1} for all i = 0, . . . , n .

i=0Note that s is a number having at most n + 1 bits.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Addition II
We have to compute the sum
s=a+b=nXsi ∈ {0, 1} for all i = 0, . . . , n .

si 2i ,

i=0

Note that s is a number having at most n + 1 bits.
We use ∧ and ∨ to denote the logical AND and OR operation,
respectively. By ⊕ we denote the Boolean EX − OR function,
i.e.,
⊕
0
1
Complexity and Cryptography

0
0
1

1
1
0
c Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Addition III
Using essentially the well-known school method for addition,
we can express the si and the carry bits c0 and ci+1 ,i = 0, . . . , n − 1 as follows:
sn = cn ,si = ai ⊕ bi ⊕ ci ,where

c0 = 0 ,ci+1 = (ai ∧ bi ) ∨ (ai ∧ ci ) ∨ (bi ∧ ci ) .

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Addition III
Using essentially the well-known school method for addition,
we can express the si and the carry bits c0 and ci+1 ,i = 0, . . . , n − 1 as follows:
sn = cn ,si = ai ⊕ bi ⊕ ci ,where

c0 = 0 ,ci+1 = (ai ∧ bi ) ∨ (ai ∧ ci ) ∨ (bi ∧ ci ) .
Since we want to count the number of binary operations to be
performed, we have to make a decision here. Either we canconsider ⊕ also as a basic binary operation or we restrict
ourselves to allow exclusively the logical AND, OR and thelogical negation as basic binary operations.
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Addition IV
In the latter case, we have to express ⊕ asx ⊕ y = (x ∧ ȳ) ∨ (x̄ ∧ y) ,where x, y ∈ {0, 1} ,i.e., it takes 5 bit basic operations (2 negations, 2 times AND and
one time OR) to express ⊕. So, the choice we make will only
affect the constant and can thus be neglected here.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Addition IV
In the latter case, we have to express ⊕ asx ⊕ y = (x ∧ ȳ) ∨ (x̄ ∧ y) ,where x, y ∈ {0, 1} ,i.e., it takes 5 bit basic operations (2 negations, 2 times AND and
one time OR) to express ⊕. So, the choice we make will only
affect the constant and can thus be neglected here.
We thus obtain the following theorem:
Theorem 1
The addition of two numbers a and b each having at most n bits canbe performed in time O(n).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Subtraction I

Subtraction can be handled within the scope of integer addition.
For representing integers, we need an extra bit for representing
the sign. We shall call such representations AS-numbers, where
A stands for “absolute value” and S for “sign.”
Definition 2
The value of an AS-number x = (xn−1 , . . . , x0 ) ∈ {0, 1}n isdefined as
VAS (x) =df (−1)xn−1 (xn−2 2n−2 + · · · + x1 2 + x0 ) .

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Subtraction II
When dealing with addition of two AS-numbers x, y having at
most n bits each, we distinguish the following cases:
Case 1. xn−1 = yn−1 .
That means x and y have the same sign. Hence, the sign of thesum is the same as the common sign of x and y. Moreover, theabsolute value of the sum equals the sum of the absolute valuesof x and y. Thus, we can directly use addition algorithm
presented above.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Subtraction II
When dealing with addition of two AS-numbers x, y having at
most n bits each, we distinguish the following cases:
Case 1. xn−1 = yn−1 .
That means x and y have the same sign. Hence, the sign of thesum is the same as the common sign of x and y. Moreover, theabsolute value of the sum equals the sum of the absolute valuesof x and y. Thus, we can directly use addition algorithm
presented above.
Case 2. xn−1 , yn−1 .
Now, we have to compare the absolute values of x and y. The
sign of the sum is equal to sign of the number having the bigger
absolute value. Without loss of generality, let x 0 be the bigger
absolute value and y 0 the smaller one. Hence, the absolutevalue of the sum is x 0 − y 0 .
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Subtraction III
Consequently, we have to deal with two additional problems.
First, we have to show that subtraction of two n-bit numbers
can be performed in time O(n).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Subtraction III
Consequently, we have to deal with two additional problems.
First, we have to show that subtraction of two n-bit numbers
can be performed in time O(n).
Second, we have to prove that comparison of absolute values of
two n-bit numbers can be done in time O(n), too. We leave it as
an exercise to show these two results, since we should havealready some familiarity with these subjects (from technicalcomputer science and/or electrical engineering).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Subtraction III
Consequently, we have to deal with two additional problems.
First, we have to show that subtraction of two n-bit numbers
can be performed in time O(n).
Second, we have to prove that comparison of absolute values of
two n-bit numbers can be done in time O(n), too. We leave it as
an exercise to show these two results, since we should havealready some familiarity with these subjects (from technicalcomputer science and/or electrical engineering).
Thus, we leave it as an exercise to prove the following theorem:
Theorem 2
The subtraction of two AS-numbers a and b each having at most n
bits can be performed in time O(n).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication I

We deal here only with the multiplication of natural numbers.
Given are two n-bit numbers a = an−1 · · · a0 andb = bn−1 · · · b0 , where ai , bi ∈ {0, 1} for all i = 0, . . . , n − 1.
Again, the semantics of these numbers a and b is then
n−1
n−1
P
P
bi 2i .
a=ai 2i and b =
i=0

i=0

We have to compute the product ab. Taking into account thata, b < 2n , one easily estimates ab < 2n · 2n = 2n+n = 22n . So,
the product ab has at most 2n bits.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication II
First, we apply the usual school method for multiplication.
Multiplication of two bits can be realized by the AND function.
Thus, first we need n2 many applications of AND to form the nsummands and n costless shifts. Next, we have to add these nnumbers. Using the same ideas as above, one easily verifies
that this iterated sum takes another O(n2 ) many bit operations.
Thus we have the following theorem:

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication II
First, we apply the usual school method for multiplication.
Multiplication of two bits can be realized by the AND function.
Thus, first we need n2 many applications of AND to form the nsummands and n costless shifts. Next, we have to add these nnumbers. Using the same ideas as above, one easily verifies
that this iterated sum takes another O(n2 ) many bit operations.
Thus we have the following theorem:
Theorem 3
The usual school algorithm for multiplying two numbers a and beach having at most n bits can be performed in time O(n2 ).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication III
Question
Can we do any better?

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication III
Question
Can we do any better?
The affirmative answer will be provided by our next theorem
which goes back to Anatoly Karatsuba.
We apply the method of divide et impera (divide and conquer inEnglish) for sequential computations.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication III
Question
Can we do any better?
The affirmative answer will be provided by our next theorem
which goes back to Anatoly Karatsuba.
We apply the method of divide et impera (divide and conquer inEnglish) for sequential computations.
The general idea of the method divide et impera is as follows:
The problem of size n is divided into a certain number of
independent subproblems having the same type but having
lower size. The solution of the original problem is obtained by
combining the solutions of the subproblems in an appropriatemanner. If this technique is applied recursively to thesubproblems until problems of sufficiently small size arise, thenthe best effect will result.
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication IV
Theorem 4
There is an algorithm for multiplying two numbers a and b eachhaving at most n bits that can be performed in time O(nlog 3 ).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication IV
Theorem 4
There is an algorithm for multiplying two numbers a and b eachhaving at most n bits that can be performed in time O(nlog 3 ).
Proof. Without loss of generality, we let n = 2k . Then there exist
numbers a0 , a1 and b0 , b1 such thata = a0 2n/2 + a1

and b = b0 2n/2 + b1 .

Then, it holds
ab = (a0 2n/2 + a1 )(b0 2n/2 + b1 )= a0 b0 2n + (a0 b1 + a1 b0 )2n/2 + a1 b1 .

Complexity and Cryptography(1)c Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication V
Equation (1) reduces the problem of multiplying two n-bit
numbers to four multiplications of numbers having at most n/2
bits and three additions as well as two shift operations. So, it
does not help.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication V
Equation (1) reduces the problem of multiplying two n-bit
numbers to four multiplications of numbers having at most n/2
bits and three additions as well as two shift operations. So, it
does not help.
Karatsuba found a way to reduce the number of multiplicationsof numbers having at most n/2 bits from four to three byobserving that(a0 b1 + a1 b0 ) = (a0 + a1 )(b0 + b1 ) − (a0 b0 + a1 b1 ) .

(2)

Using Equation (2), it is immediately clear that we only have tocompute the three products a0 b0 , a1 b1 , and (a0 + a1 )(b0 + b1 ).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication VI
Therefore, we directly arrive at the following algorithm: Foreach of the Steps (1) through (6) perform the computation
sequentially.
Karatsuba Multiplication(1) s0 = a0 + a1 , s1 = b0 + b1 ;(2) p0 = a0 b0 , p1 = a1 b1 , p2 = s0 s1 ;(3) t = p0 + p1 ;(4) u = p2 − t, û = u2n/2 ;(5) v = a0 b0 2n + a1 b1 ;(6) p = v + û.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication VII

The correctness of the algorithm above is obvious by thearguments provided before displaying it.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication VII

The correctness of the algorithm above is obvious by thearguments provided before displaying it.
We have to estimate the complexity of the Karatsuba
multiplication.
Let A(n) be the time for adding two n-bit numbers, andlet M(n) be the time for multiplying two n-bit numbers.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication VIII

Then, we can estimate the time complexity as follows:(1) 2A(n/2);(2) 2M(n/2) + M(n/2 + 1);(3) A(n);(4) A(n + 2) and a costless shift.
(5) This step is costless, since it is only a concatenation of bits.
(6) A 32 n , since the n/2 lower bits of û are all 0.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication IX
Now, the main idea is to apply the Karatsuba multiplication
algorithm recursively to itself. The only disturbing point here isthat we have a subproblem (computing s0 s1 ) which is themultiplication of two numbers having n/2 + 1 bits (and not
only n/2 as desired). We resolve it as follows:

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication IX
Now, the main idea is to apply the Karatsuba multiplication
algorithm recursively to itself. The only disturbing point here isthat we have a subproblem (computing s0 s1 ) which is themultiplication of two numbers having n/2 + 1 bits (and not
only n/2 as desired). We resolve it as follows:
Let s0 = x0 2 + x1 and s1 = y0 2 + y1 , where x1 , y1 ∈ {0, 1} andx0 , y0 are n/2-bit numbers. Thens0 s1 = (x0 2 + x1 )(y0 2 + y1 )= 4x0 y0 + 2(x0 y1 + x1 y0 ) + x1 y1 .

Complexity and Cryptography(3)c Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication IX
Now, the main idea is to apply the Karatsuba multiplication
algorithm recursively to itself. The only disturbing point here isthat we have a subproblem (computing s0 s1 ) which is themultiplication of two numbers having n/2 + 1 bits (and not
only n/2 as desired). We resolve it as follows:
Let s0 = x0 2 + x1 and s1 = y0 2 + y1 , where x1 , y1 ∈ {0, 1} andx0 , y0 are n/2-bit numbers. Thens0 s1 = (x0 2 + x1 )(y0 2 + y1 )(3)

= 4x0 y0 + 2(x0 y1 + x1 y0 ) + x1 y1 .
Now, the multiplication of x0 y0 is a multiplication of n/2-bit
numbers, i.e., it has costs M(n/2).
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication X
The remaining multiplications, i.e., x0 y1 , x1 y0 and x1 y1 can bedirectly realized by using n + 1 AND gates, since x1 , y1 ∈ {0, 1}.
Additionally, we have to include the costs for addition, i.e.,A(n) + A(n/2) + 1 .

(4)

Therefore, by using (3) and (4), we arrive at
M(n/2 + 1) 6 M(n/2) + A(n) + A(n/2) + 1 .

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication X
The remaining multiplications, i.e., x0 y1 , x1 y0 and x1 y1 can bedirectly realized by using n + 1 AND gates, since x1 , y1 ∈ {0, 1}.
Additionally, we have to include the costs for addition, i.e.,A(n) + A(n/2) + 1 .

(4)

Therefore, by using (3) and (4), we arrive at
M(n/2 + 1) 6 M(n/2) + A(n) + A(n/2) + 1 .
Since addition can be realized by a sequential algorithm taking
time O(n), we conclude that there is a constant ĉ > 0 such thatM(n/2 + 1) 6 M(n/2) + ĉn .
Consequently, there is a constant c > 0 such that
M(n) =
Complexity and Cryptographyc,3M(n/2) + cn,

if n = 1 ;if n > 1 .

(5)c Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication XI
Now, it suffices to show that M(n) = 3cnlog 3 − 2cn is a solutionof the recursive Equation (5).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication XI
Now, it suffices to show that M(n) = 3cnlog 3 − 2cn is a solutionof the recursive Equation (5).
This is shown inductively. For the induction base, we get
M(1) = 3c1log 3 − 2c = c .

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Multiplication XI
Now, it suffices to show that M(n) = 3cnlog 3 − 2cn is a solutionof the recursive Equation (5).
This is shown inductively. For the induction base, we get
M(1) = 3c1log 3 − 2c = c .
Assume the induction hypothesis for m. The induction step isfrom m to 2m. Recall that n = 2k , thus this induction step isjustified. We have to show that M(2m) = 3c(2m)log 3 − 2c(2m).
M(2m) = 3M(m) + 2cm
= 3 3cmlog 3 − 2cm + 2cm= 9cmlog 3 − 4cm = 9cmlog 3 − 2c(2m)= 3c2log 3 mlog 3 − 2c(2m) = 3c(2m)log 3 − 2c(2m) .
Consequently, M(n) = O(nlog 3 ). This proves the theorem.
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Discussion
Recall that log 3 ≈ 1.59. Thus, the Karatsuba multiplication isindeed much faster than the usual school method. Intuitively,
the improvement is due to the fact that multiplication is more
complex than addition. Hence, performing three instead offour multiplications results in roughly 25% saving of time.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Discussion
Recall that log 3 ≈ 1.59. Thus, the Karatsuba multiplication isindeed much faster than the usual school method. Intuitively,
the improvement is due to the fact that multiplication is more
complex than addition. Hence, performing three instead offour multiplications results in roughly 25% saving of time.
One can do even better. Schönhage and Strassen (1971) found amultiplication algorithm that takes time O(n log n log log n) forcomputing the product of two n-bit numbers. Very roughly
speaking, their algorithm works via the fast Fouriertransformation. However, their algorithm is only
asymptotically faster, and n must be very large for achieving an
improvement in practice. We thus omit this algorithm here.
And 2007 Fürer presented an even faster algorithm for integer
multiplication.

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Discussion
Recall that log 3 ≈ 1.59. Thus, the Karatsuba multiplication isindeed much faster than the usual school method. Intuitively,
the improvement is due to the fact that multiplication is more
complex than addition. Hence, performing three instead offour multiplications results in roughly 25% saving of time.
One can do even better. Schönhage and Strassen (1971) found amultiplication algorithm that takes time O(n log n log log n) forcomputing the product of two n-bit numbers. Very roughly
speaking, their algorithm works via the fast Fouriertransformation. However, their algorithm is only
asymptotically faster, and n must be very large for achieving an
improvement in practice. We thus omit this algorithm here.
And 2007 Fürer presented an even faster algorithm for integer
multiplication.
Try to implement Karatsuba’s multiplication.
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Solutions of Recursive Equations
The technique of divide et impera yields recursive equations.
Can we say something about the general solvability of them?

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Solutions of Recursive Equations
The technique of divide et impera yields recursive equations.
Can we say something about the general solvability of them?
Theorem 5
Let a, b, c ∈ N+ . Then the recursive equation
T (n) =

b,
aT

n
c



+ bn,

if n = 1 ;for all n > 1 ,where n is a power of c, has the following solution:

if a < c ; O(n),
O(n log n), for all a = c ;T (n) =
O(nlogc a ),for all a > c .

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Proof ILet n be a power of c, i.e., n = ck . First, we show that
T (n) = bn ·logc n 

X
i=0

a i
c

is a solution of the recursive equation given in Theorem 5.
This is done inductively. For the induction basis let n = 1.
Then, logc 1 = 0 and
T (1) = b (by definition) a 0= b·(multiplying by 1)
c
0  
X
a 0
= b·
.
c
i=0

This shows the induction basis.
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Proof II
Next, assume the induction hypothesis (abbr. IH) that
T (m) = bm ·logc m 

X
i=0

a i
c

is a solution of the recursive equation for n = m. The induction
step has to be done from m to cm, i.e., we have to show thatT (cm) = bcm ·logc (cm) X
i=0

Complexity and Cryptography

a i
.
c

c Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Proof IIIT (cm) = aT (m) + bcm (by definition)= abm ·

logc m 

X
i=0

a i
+ bcm (by the IH)
clogc m= bm ·

X ai+1
+ bcm
ci
i=0

= bcm ·

logc m X
i=0(logc m)+1 a i+1+ bcm = bcm ·
c

X
i=0

a i
.
c

Finally, (logc m) + 1 = logc m + logc c = logc (cm). Thus,
T (cm) = bcm ·logc (cm) X
i=0

Complexity and Cryptography

a i
.
c
c Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Proof IV
Next, we distinguish the following cases:
Case 1. a < c∞PThen a/c < 1 and thus
i=0


a i
is a convergent series. Hence,c

we have T (n) = O(n).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Proof IV
Next, we distinguish the following cases:
Case 1. a < c∞PThen a/c < 1 and thus
i=0


a i
is a convergent series. Hence,c

we have T (n) = O(n).
Case 2. a = c
Consequently, a/c = 1, and thus
logc n 

X
i=0

a i
= 1 + logc n .
cTherefore, T (n) = O(n logc n) = O(n log n).

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Proof V
Case 3. a > clogc n X
a 1+logc n
−1
a i
c
= bn ·
T (n) = bn ·
a
c
c −1
i=0
 

a 1+logc n
6 k̂bn ·−1(note that k̂ is a constant)ca1+logc na= k̂b alogc n (recall that n = clogc n )
1+log
n
c
c
c
= k 0 alogc n , where k 0 = k̂ba/c
ln n
0 logc n ln a0 ln n ln a·(1/ ln c)=k e, since logc n =
= ke
ln c

6 k̂bn ·= k 0 eln n logc a ,( since (ln a)/ ln c = logc a)= k 0 nlogc a = O(nlogc a ) .
Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Thank you!

Complexity and Cryptographyc Thomas Zeugmann

Definitions

Addition

Subtraction

Multiplication

Solutions of Recursive Equations

End

Anatolii Alexeevich Karatsuba
Complexity and Cryptographyc Thomas Zeugmann