Cryptography Reference
In-Depth Information
>
≤
≤
−
1
and d
k
−
1
=
where k
0
,thed
i
are integers such that
0
d
i
b
0
. Moreover,
=
+
k
log
b
n
1
.
Proof
We use the division algorithm (Theorem 2.1) to build the representation. We
successively divide:
n
=
bq
0
+
d
0
,
q
0
=
bq
1
+
d
1
,
q
1
=
bq
2
+
d
2
,
...
q
i
−
1
=
bq
i
+
d
i
,
and note that 0
0. This strictly decreasing sequence
of non-negative integers must reach the value 0, so let
k
be the first index such that
q
k
−
1
≤
d
i
<
b
and
n
>
q
0
>
q
1
··· ≥
d
k
−
1
which is a
positive integer. Now, starting at the first identity and replacing each
q
i
by its value
given by the next identity we obtain the required expression for
n
. The uniqueness
of this expression is left as an exercise. Finally, note that
b
k
−
1
=
0. Then the above sequence of identities ends in
q
k
−
2
=
b
k
and, taking
≤
n
<
base-
b
logarithms, we obtain the chain of inequalities
k
−
1
≤
log
b
n
<
k
which is
clearly equivalent to
k
=
log
b
n
+
1.
From this theorem it follows that each positive integer has a representation of the
form
n
=
(
d
k
−
1
,
d
k
−
2
,...,
d
1
,
d
0
)
b
which, if there is no ambiguity, is also written
as
d
k
−
1
d
k
−
2
...
d
1
d
0
. It is called the
b
-
adic expansion
of
n
and its terms are called
digits
while its
length
is
k
. Notable special cases are the bases
b
=
10 (decimal),
b
=
2 (binary),
b
=
8 (octal) and
b
=
16 (hexadecimal or, simply, hex). If
b
≤
10,
then the base-
b
digits are represented by the usual decimal digits which are
b
.
In particular, the binary digits, or bits, are 0, 1, and we have the binary expansion
d
k
−
1
d
k
−
2
...
<
k
}
∗
, where
k
denotes the set of binary strings
d
1
d
0
∈{
0
,
1
}
⊂{
0
,
1
{
0
,
1
}
}
∗
the set of all (finite-length) binary strings. For other bases,
additional symbols (usually letters) are used and, for example, hexadecimal digits
are given, in increasing order, by 0
of length
k
and
{
0
,
1
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
a
,
b
,
c
,
d
,
e
,
f
(sometimes
upper-case letters are used instead of lower-case ones).
The proof of the preceding theorem provides an algorithm to compute the
b
-adic
expansion of an integer
n
by means of successive integer divisions by
b
and this
algorithm is used whenever we want to do a “base change”, for example, for passing
from the decimal expansion to the binary one. In some cases this is particularly easy.
If
a
b
k
then conversion from base
a
to base
b
is just a matter of replacing each
base-
a
digit by its
k
-digit representation in base
b
, and conversely to pass from base
b
to base
a
. For example, to convert between hexadecimal and binary we only have to
replace each hex digit by a corresponding 4-bit block (sometimes called a
half
-
byte
or a
nibble
), where 0 goes to 0000, 1 to 0001, and so on, until
f
which goes to
1111. For the inverse conversion one should group the bits in blocks of 4 and do the
replacement, bearing in mind that if the first group from the left has fewer than 4 bits
then it should be completed with zeros added to the left. So, for example, the binary
=
