Cryptography Reference
In-Depth Information
CHAPTER 7
Bitwise and
Logical Functions
And sprinkled just a bit
Over each banana split.
—Tom Lehrer, “In My Home Town”
“Contrariwise,” continued Tweedledee, “if it was so, it might be; and if it were
so, it would be: but as it isn't, it ain't. That's logic.”
—Lewis Carroll,
Through the Looking-Glass
I
N THIS CHAPTER WE SHALL
present functions that carry out bitwise operations on
CLINT
objects, and we shall also introduce functions for determining the equality
and size of
CLINT
objects, which we have already used quite a bit.
Among the bitwise functions are to be found the shift operations, which
shift a
CLINT
argument in its binary representation by individual bit positions,
and certain other functions taking two
CLINT
arguments that enable the direct
manipulation of the binary representation of
CLINT
objects. How such operations
can be applied to arithmetic purposes is most clearly seen in the shift operations
described below, but we have also seen, in Section 4.3, how the bitwise AND
operation can be used in reduction modulo a power of two.
7.1 Shift Operations
Necessity devises all manner of shifts.
—Rabelais
The simplest way to multiply a number
a
with the representation
a
=
(
a
n
−
1
a
n
−
2
...a
0
)
B
to the base
B
by a power
B
e
is to “shift
a
to the left by
e
digits.” This works with the binary representation exactly as it does in our familiar
decimal system:
aB
e
=(
a
n
+
e
−
1
a
n
+
e
−
2
...a
e
a
e
−
1
...a
0
)
B
,
