Cryptography Reference
In-Depth Information
where
a
n
+
e
−
1
=
a
n
−
1
,
a
n
+
e
−
2
=
a
n
−
2
,
...,
a
e
=
a
0
,
a
e
−
1
=0
,
...,
a
0
=0
.
For
B
=2
this corresponds to multiplication of a number in binary
representation by
2
e
, while for
B
=10
it corresponds to multiplication by a
power of ten in the decimal system.
In the analogous procedure for whole-number division by powers of
B
the
digits of a number are “shifted to the right”:
B
e
=(
a
n
−
1
...a
n
−
e
a
n
−
e
−
1
a
n
−
e
−
2
...a
0
)
B
,
a
where
a
n
−
1
=
···
=
a
n
−
e
=0
,
a
n
−
e
−
1
=
a
n
−
1
,
a
n
−
e
−
2
=
a
n
−
2
,...,a
0
=
a
e
.
For
B
=2
this corresponds to integer division of a number in binary
representation by
2
e
, and the analogous result holds for other bases.
Since the digits of
CLINT
objects are represented in memory in binary form,
CLINT
objects can easily be multiplied by powers of two by shifting left, where the
next digit to the right is shifted into each place where a digit has been shifted left,
and the binary digits left over on the right are filled with zeros.
In an analogous way
CLINT
objects can be divided by powers of two by shifting
each binary digit to the right into the next lower-valued digit. Digits left free at the
end are either filled with zeros or ignored as leading zeros, and at each stage in
the process (shifting by one digit) the lowest-valued digit is lost.
The advantage of this process is clear: Multiplication and division of a
CLINT
object
a
by a power of two
2
e
are simple, and they require at most
e
log
B
a
shift operations to shift each
USHORT
value by one binary digit. Multiplication and
division of
a
byapower
B
e
log
B
a
operations for storing
USHORT
uses only
values.
In the following we shall present three functions. The function
shl_l()
executes a rapid multiplication of a
CLINT
number by
2
, while the function
shr_l()
divides a
CLINT
number by
2
and returns the integer quotient.
Lastly, the function
shift_l()
multiplies or divides a
CLINT
type
a
byapower
of two
2
e
. Which operation is executed is determined by the sign of the exponent
e
of the power of two that is passed as argument. If the exponent is positive, then
the operation is multiplication, while if it negative, then division is carried out.
If
e
has the representation
e
=
Bk
+
l
,
l<B
,then
shift_l()
carries out the
multiplication or division in
(
l
+1)
log
B
a
operations on
USHORT
values.
All three functions operate modulo
(
N
max
+1)
on objects of
CLINT
type. They
are implemented as accumulator functions, and thus they change their
CLINT
operands in that they overwrite the operand with the result of the operation.
The functions test for overflow, respectively underflow. However, in shifting,
underflow cannot really arise, since in those cases where more positions are to
