Cryptography Reference
In-Depth Information
number 1011101 is converted to hexadecimal by replacing 0101 by 5 and 1101 by
d
,
so that its hexadecimal representation is 5
d
.
Maple has commands for converting between representations of integers in dif-
ferent bases. The generic conversion function is
convert/base
which converts
between two bases
a
and
b
by taking the list of digits in base
a
(if
a
10 then the
digits can also be given in the usual form instead of as a list) and converting it to the
list of digits of the same number in base
b
. It should be noted that these Maple lists
follow the
little
-
endian
convention in which the most significant digit is the one on
the right (the last one on the list). For example,
=
> convert([1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1], base, 2, 16);
[9, 11, 4, 11, 3]
passes from the list of binary digits to the corresponding list of hex digits. Note that
in this case the letters
a
f
are not used for the hex digits and their dec-
imal form (with two decimal digits each) is used instead. These letters are used,
however, when converting from decimal to hex by means of another variant of
the
convert
function called
convert/hex
. We use this function together with
convert/binary
to convert the binary number whose bits are given by the list
above to hex:
,
b
,
c
,
d
,
e
,
> convert(111011010010111001, decimal, binary);
242873
> convert(%,hex);
3B4B9
When using these functions in Maple, it should be taken into account that these
representations of a number are not, in general, valid replacements for the number
itself. For example, consider:
> x := convert(5, hex);
5
> whattype(x);
symbol
In this case, the result of converting the integer 5 to hex is a symbol, i.e., no
longer a number and, for example, we could not perform arithmetic operations with
it anymore. But even more caution is required with the following conversion:
> y := convert(5, binary);
101
> whattype(y), irem(y, 5);
integer, 1
Now, the result of converting 5 to binary is indeed an integer but this integer is no
longer 5 but 101, i.e., the number whose decimal representation has the same digits
as the binary representation of 5 …
2.3 Basic Computational Complexity
As we shall see later, the security of cryptosystems is often based on the assumed
hardness of certain computational (mostly number-theoretic) problems. It is therefore
important to have procedures to evaluate the hardness of computational problems
