Transcript Slides Week 4 Complexity

Computational Complexity
Size Matters!
1
Suppose there are several algorithms which
can all be used to perform the same task.
We need some way to judge the efficiency
of the algorithms against each other.
We can break the algorithms down into the
basic steps, and then count how many steps
there are in each.
This is the computational complexity of
the algorithm.
2
The computation complexity is given in
terms of the size of the problem.
For example, XORing two 5 bit binary
numbers will take 5 basic steps, but
XORing two 100 bit binary number will
take 100 basic steps. The algorithm used to
XOR is the same in each case and its
complexity is given in terms of the size of
the binary numbers.
3
• The size of a number n is defined to be the
number of binary bits needed to write n in
base 2.
• We use b(n) to denote the size of n.
Examples
b(5) = b(1012) = 3
b(20) = b(101002) = 5
b(212) = b(4096) = b(10000000000002) = 13
What is b(0) ?
4
• If we XOR two binary numbers each of size
b then we take b steps.
• We say XORing has computational
complexity of “order b” which is written
O(b)
• If we double the size of the problem – here
the size of the numbers to be XORed, then
we double the number of steps required and
thus the time needed.
5
• Computational complexity is measured
independently of the implementation.
• The amount of time that is required to
perform b basic steps will vary from
computer to computer.
• The important thing to note is that for an
algorithm with complexity O(b),
multiplying the size of the problem by X
will have the effect of multiplying the time
required by X as well.
6
• The computational complexity of adding
two binary numbers is also O(b).
• However, the computational complexity of
multiplying two numbers is O(b2).
If you double the number of bits in the
numbers to be multiplied, then the time
required quadruples because
(2b)2 = 4b2
7
Exponentiation
(Raising to the Power)
Suppose we want to compute x8
Method 1
Multiply x by itself 8 times
x8 = x*x*x*x*x*x*x*x
The total number of multiplications used is 8
8
Method 2
Another approach would be to realise that
x8 = (x4)2 = (x2)2)2
So we need to compute x2 (one mult.), then
square that answer to get x4 (another mult.),
finally square that answer to get x8 (one more
mult.) .
We have used only 3 multiplications instead
of 8.
9
Suppose we need to compute x9.
We can compute x8 and then multiply the
answer by x (x9 = x8+1 = x8*x). A total of 4
multiplications.
How about x13 ?
13=8+4+1
We can compute x8, multiply that answer by
x4 (which we have already computed on the
way to x8) and finally multiply that answer
by x – a total of 5 multiplications.
10
What is going on here?
• Represent the power in binary
(eg 13=8+4+1 = 11012)
• Calculate x2 , x4, x8 using successive
squaring
• Multiply together the answers which have a
one in the binary power i.e., 13 = 8 + 4 +1
so we multiply x8 * x4 * x1
11
Complexity of Method 2
• If the size of the power is b, then the number of
multiplications will be at least b because that is the
number of successive squaring multiplications
required.
• We also need to do up to b-1 other multiplications
depending on how many 1’s there are in the binary
representation of the power.
• So the number of multiplications is between b and
2b.
12
• We have already seen that the order of
complexity of multiplying two numbers
together is O(b2).
• We need to do between b and 2b
multiplications, so the number of steps we
do in total will be between b3 and 2b3.
• We ignore constant values when talking
about complexity and so say that our
algorithm has order O(b3).
13
Algorithm for exponentiation
To Compute xn
Initialise y=1, u=x
Repeat
if n mod 2=1 then y=y*u
n=n div 2
u=u*u
Until n=0
Output y
14
Why is complexity important
with regards to cryptography?
• The numbers we are working with are very big.
Suppose b(n)=1000. Then the difference between
an O(b) algorithm and an O(b2) algorithm is
approx. 10002 = 106 steps.
• Functions such as exponentiation are used a lot in
cryptographic protocols and the protocol would be
too inefficient to use if there were not an efficient
method for exponentiation.
• On the other hand, some cryptographic protocols
rely on the fact that there is no efficient algorithm
which could be used to break them.
15