The next thing we're going to look at is
how to compute modular large integers. So
the first question is how do we represent
large integers in a computer? So that's
actually fairly straightforward. So
imagine we're on a 64 bit machine, what we
would do is we would break the number we
want to represent, into 32 bit buckets And
then, we will basically have these n/32 bit buckets, and together they will
represent the number that we want to store
on the computer. Now, I should mention
that I'm only giving 64 bit registers as
an example. In fact, many modern
processors have 128 bit registers or more,
and you can even do multiplications on
them. So normally you would actually use
much larger blocks than just 32 bits. The
reason, by the way, you want to limit
yourself to 32 bits is so that you can
multiply two blocks together, and the
result will still be less than 64 bits,
less than the word size on the machine. So
now let's look at particular arithmetic
operations and see how long each one
takes. So addition and subtraction
basically what you would do is that
addition would carry or subtraction would
borrow and those are basically linear time
operations. In other words, if you want to
add or subtract two n bit integers the
running time is basically
linear in n. Multiplication
naively will take quadratic time. In fact,
this is what's called the high school
algorithm. This is what you kind of
learned in school, where if you think
about this for a minute you'll see that,
that algorithm basically is quadratic in
the length of the numbers that are being
multiplied. So a big surprise in the 1960s
was an algorithm due to Karatsuba that
actually achieves much better than
quadratic time in fact, it achieved a
running time of n to the 1.585. And
there's actually no point in me showing
you how the algorithm actually worked,
I'll just mention the main idea What
Karatsuba realized, is that in fact when
you want to multiply two numbers, you can
write them as, you can take the first
number x, write it as 2 to the b times
x2 plus x1. Where x2 and x1 are roughly
the size of the square root of x. Okay, so
we can kind of break the number x into the
left part of x and the right part of x.
And basically, you're writing x as if it
was written base 2 to the b. So it's got
two digits base 2 to the b. And you do
the same thing with, y. You write y base
2 to the b. Again, you would write it
as, the sum of the left half plus the
right half, And then, normally, if you try
to do this multiplication, when you open
up the parentheses. You see that, this
would require 4 multiplications, right?
It would require x2 times y2, x2 times y1,
x1 times y2, and x1 times y1. What
Karatsuba realized is there's a way to do
this multiplication of x by y using only
three multiplications of x1 x2 y1 y2. So it's just a big multiplication of x times y
only it takes three little multiplications. You can now recursively
apply exactly the same procedure to
multiplying x2 by y2, and x2 by y1, and so
on and so forth. And you would get this
recursive algorithm. And if you do the
recursive analysis, you will see that
basically, you get a running time of n to the 1.585.
This number is basically, the 1.585 is basically, log of 3 base 2.
Surprisingly, it turns out that Karatsuba
isn't even the best multiplication
algorithm out there. It turns out that, in fact, you can do multiplication in about n*log(n) time.
So you can do multiplication in almost linear time. However, this is an extremely asymptotic results.
The big O here hides very big constants. And as a
result, this algorithm only becomes
practical when the numbers are absolutely
enormous. And so this algorithm is
actually not used very often. But
Karatsuba's algorithm is very practical.
And in fact, most crypto-libraries
implement Karatsuba's algorithm for
multiplication. However, for simplicity
here, I'm just gonna ignore Karatsuba's
algorithm, and just for simplicity, I'm
gonna assume that multiplication runs in
quadratic time. But in your mind, you
should always be thinking all multiplication really is a little bit faster than quadratic.
And then the next question after multiplication is what about
division with remainder and it turns out
that's also a quadratic time algorithm.
So the main operation that remains, and one
that we've used many times so far, and
I've never, actually never, ever told you
how to actually compute it, is this
question of exponentiation. So let's solve
this exponentiation problem a bit more
abstractly. So imagine we have a finite
cyclic group G. All this means is that
this group is generated from the powers of
some generator little g. So for example
think of this group as simply ZP*, and think of little g as some generator of
big G. The reason I'm sitting in this way,
is I'm, I want you to start getting used
to this abstraction where we deal with a
generic group G and ZP* really is just
one example of such a group. But, in fact,
there are many other examples of finite
cyclic groups. And again I want to
emphasis basically that group G, all it
is, it's simply this powers of this
generator up to the order of the group.
I'll write it as G to the Q. So our goal
now is given this element g, and some
exponent x, our goal is to compute the
value of g to the x. Now normally what you
would say is, you would think well, you
know, if x is equal to 3 then I'm
gonna compute you know, g cubed. Well,
there's really nothing to do. All I do is
I just do g times g times g and I get g
cubed, which is what I wanted. So that's
actually pretty easy. But in fact, that's
not the case that we're interested in. In
our case, our exponents are gonna be
enormous. And so if you try, you know,
think of like a 500-bit number and so if
you try to compute g to the power of a
500-bit number simply by multiplying g by
g by g by g this is gonna take quite a
while. In fact it will take exponential
time which is not something that we want
to do. So the question is whether even
though x is enormous, can we still compute
g to the x relatively fast and the answer
is yes and the algorithm that does that
is called a repeated squaring algorithm.
And so let me show you how repeated
squaring works. So let's take as an
example, 53. Naively you would have to do
53 multiplications of g by g by g by g
until you get to g by the 53 but I want to
show you how you can do it very quickly.
So what we'll do is we'll write 53 in
binary. So here this is the binary
representation of 53. And all that means
is, you notice this one corresponds to 32,
this one corresponds to 16, this one
corresponds to 4, and this one
corresponds to 1. So really 53 is 32
plus 16 plus 4 plus 1. But what
that means is that g to the power of 53 is
g to the power of 32+16+4+1. And we can
break that up, using again, the rules of
exponentiation. We can break that up as g
to the 32 times g to the 16 times g to the
4 times g to the 1, Now that should start
giving you an idea for how to compute g to
the 53 very quickly. What we'll do is,
simply, we'll take g and we'll start
squaring it. So what square wants, g wants
to get g squared. We square it again to
get g to the 4, turn g to the 8.
Turn g to the 16, g to the 32. So
we've computed all these squares of g. And
now, what we're gonna do is we're simply
gonna multiply the appropriate powers to
give us the g to the 53. So this is g to
the one times g to the 4 times g to the 16 times g to the 32, is basically
gonna give us the value that we want,
which is g to the 53. So here you see that
all we had to do was just compute, let's
see, we had to do one, two, three, four,
five squaring, plus four more multiplications
so with 9 multiplications we computed g
to the 53. Okay so that's pretty
interesting. And it turns out this is a
general phenomena that allows us to raise
g to very, very high powers and do it very
quickly. So let me show you the algorithm,
as I said this is called the repeated
squaring algorithm. So the input to the
algorithm is the element g and the
exponent x. And the output is g to the x.
So what we're gonna do is we're gonna
write x in binary notation. So let's say
that x has n bits. And this is the actual
bit representation of x as a binary
number. And then what we'll do is the
following. We'll have these two registers.
y is gonna be a register that's constantly
squared. And then z is gonna be an
accumulator that multiplies in the
appropriate powers of g as needed. So all
we do is the following we loop through the
bits of x starting from the least
significant bits, And then we do the
following: in every iteration we're simply
gonna square y. Okay, so y just keeps on
squaring at every iteration. And then
whenever the corresponding bit of the
exponent x happens to be one, we simply
accumulate the current value of y into
this accumulator z and then at the end, we
simply output z. That's it. That's the
whole algorithm, and that's the repeated
squaring algorithm. So, let's see an
example with G to the 53. So,
you can see the two columns. y is one
column, as it evolves through the
iterations, and z is another column, again
as it evolves through the iterations. So,
y is not very interesting. Basically, all
that happens to y is that at every
iteration, it simply gets squared. And so
it just walks through the powers of two
and the exponents and that's it. z is the
more interesting register where what it
does is it accumulates the appropriate
powers of g whenever the corresponding bit
to the exponent is one. So for example the
first bit of the exponent is one,
therefore, the, at the end of the first
iteration the value of z is simply equal to
g. The second bit of the exponent is zero
so the value of z doesn't change after the
second iteration. And at the end of the
third iteration well the third bit of the
exponent is one so we accumulate g to the
fourth into z. The next bit of the
exponent is zero so z doesn't change. The
next bit of the exponent is one and so now
we're supposed to accumulate the previous
value of y into the accumulator z so let
me ask you so what's gonna be the value of z?
Well, we simply accumulate g to the
16 into z and so we simply compute the sum
of 16 and 5 we get g to the 21.
Finally, the last bit is also set to one
so we accumulate it into z, we do 32 plus 21 and we get the finally output g to the 53.
Okay, so this gives you an idea of how
this repeated squaring algorithm works.
It's is quite an interesting algorithm and
it allows us to compute enormous powers of
g very, very, very quickly. So the number
of iterations here, essentially, would be
log base 2 of x. Okay. You notice the
number of iterations simply depends on the
number of digits of x, which is basically
the log base 2 of x. So even if x is a
500 bit number in 500 multiplication,
well, 500 iterations, really 1,000
multiplications because we have to square
and we have to accumulate. So in 1,000
multiplications we'll be able to raise g
to the power of a 500 bit exponent.
Okay so now we can summarize kind of the running times so suppose we
have an N bit modulus capital N as we
said addition and subtraction in ZN takes
linear time. Multiplication of just, you
know, as I said, Karatsuba's actually makes this
more efficient, but for simplicity we'll
just say that it takes quadratic time. And
then exponentiation, as I said, basically
takes log of x iterations, and at each
iteration we basically do two
multiplications. So it's O(log (x))
times the time to multiply. And let's say
that the time to multiply is quadratic. So
the running time would be, really, N
squared log x. And since x is always gonna
be less than N, by Fermat's theorem
there's no point in raising g to a power
that's larger than the modulus. So x is
gonna be less than N. Let's suppose that x
is also an N-bit integer, then, really
exponentiation is a cubic-time algorithm.
Okay so that's what I wanted you to
remember, that exponentiation is actually
a relatively slow. These days, it actually
takes a few microseconds on a modern
computer. But still, microseconds for a,
for a, say a four gigahertz processor is
quite a bit of work. And so just keep in
mind that all the exponentiation
operations we talked about. For example,
for determining if a number is a quadratic
residue or not, All those, all those
exponentiations basically take cubic time.
Okay, so that completes our discussion of
arithmetic algorithms, and then in the
next segment we'll start talking about
hard problems, modulo, primes and composites.