Cryptography Reference
In-Depth Information
3.
There are many ways to implement a class to perform arithmetic with arbitrarily large
integers. The method presented in this chapter is perhaps the most intuitive for us,
because it uses decimal arithmetic, and because the algorithms closely resemble what
we do as humans. However, a computer does arithmetic in a different way than us. First
of all, numbers are represented as a series of switches that are either on or off, or in
binary.
To develop a large integer class that executes more efficiently, we want to mimic as
closely as possible the way a binary computer does arithmetic. While we are at it, we
might want to make the number representation more flexible, and use linked lists to hold
the data instead of arrays. For example, suppose we use a doubly-linked list with a
head and tail pointer. It will point at a series of ints (or bytes, or shorts, or longs), where
each int represents part of the binary integer. (See the figure.)
false
negative
head
tail
0111111101101111
1010111111110101
0000101011110100
1111011101011101
To perform addition of integers with the same sign, simply add them as binary integers
the same way the computer does. If there is a carry in the high order digit of each int, carry
it over to the next int. To subtract, simply add the negative, then store all negative num-
bers in two
-
complement of a binary integer is where each bit is inverted, and then you add 1. For
example, the byte-sized two
'
-
'
s
complement form, the same way a computer normally does. The two
s
'
s complement of 9 = 00001001
base 2
is 11110111
base 2
. Thus,
if you wish to compute 5 minus 9 in binary, this is
00000101
-
00001001
'
-
To do a subtraction, form the two
s
complement of the second integer, and add them.
00000101
+ 11110111
11111100
This answer is the two
'
s
-
complement representation of
4 (you can verify this by sub-
tracting 1 then inverting the bits), and so the answer to 5 minus 9 is
4, as it should be.
Search WWH ::
Custom Search