Cryptography Reference
In-Depth Information
most of your work involves memory management and keeping track of carries
and borrows.
Implementing Large-Number Multiplication
Multiplication and division aren't quite so easy, unfortunately. If you tried to
multiply “backward” one
char
at a time as you did with addition, you'd never
even come close to getting the right result. Of course, multiplication is just
successive adding — multiplying fi ve by three involves adding fi ve to itself
three times — 5
15. This suggests an easy implementation of
a multiplication algorithm. Remember, though, that you're going to be dealing
with astronomical numbers. Adding fi ve to itself three times is not a terribly
big deal — it wouldn't even be a big deal if you did it in the reverse and added
three to itself fi ve times. But adding a 512-bit number to itself 2
512
times would
take ages, even on the fastest desktop computer. As a result, you have to look
for a way to speed this up.
When you were in elementary school, you were probably taught how to do
multi-digit multiplication like this:
5
5
3 * 5
123
456
738
6150
49200
56088
You may have never given much thought to what you were doing, or why
this works, but notice that you've shortened what might otherwise have been
123 addition operations down to 3. A more algebraic way to represent this same
multiplication is
(400
50
6) * 123
(4 * 10^2
5 * 10^1
6 * 10^0) * 123
(4 * 10^2) * 123
(5 * 10^1) * 123
(6 * 10^0) * 123
(distributivity of multiplication)
4 * 123 * 10^2
5 * 123 * 10^1
6 * 123 * 10^0
492 * 10^2
615 * 10^1
123 * 10^0
Because multiplying by 10
n
just involves concatenating
n
zeros onto the result,
this is simply
56088
What you actually did at each step was to first multiply 123 by one of
the digits of 456, and then shift it left — that is, concatenate a zero. Can you do the
same thing with binary multiplication? Yes, you can. In fact, it's signifi cantly
49200
6150
738
Search WWH ::
Custom Search