目前为止，我们使用的整数表示体系被称为十进制体系(decimal positional system)。在此体系中，我们将任何整数表示为由十进制数字集合 \(\{0,1,2,3,4,5,6,7,8,9\} \) 中的元素构成的序列。需要强调的是，计算机科学和密码学中存在其他整数表示方法：
所谓二进制体系(binary positional system)指任何整数都是由二进制数字(或称为位)集合 \(\{0,1\}\) 构成的元素序列表示。更加准确的说，设 \(n \in \Bbb{N}_{0} \) 是一个使用十进制表示的非负整数， \(b=b_{k-1}b_{k-2}\ldots b_{0} \) 是由位 \(b_j \in \{0,1\} \subset \Bbb{N}_0 \) 构成的序列，其长度为正整数 \(k \in \Bbb{N}\) 。如果下式成立，则 \(b\) 是 \(n\) 的二进制表示：
\[ n = \sum_{j=0}^{k-1} b_j\cdot 2^j \]
在这种情况下，我们将 \(n\) 的二进制表示记为 \(Bits(n):= b_{k-1}b_{k-2}\ldots b_{0}\) ，并称 \(n\) 是一个 \(k\) 位数(k-bit number)， \(k:= |n|_2\) 是 \(n\) 的位长(bit length)。
可以证明，如任何非负数的二进制表示都是唯一的。我们称 \(b_0\) 是最低有效位(least significant bit)，\(b_{k-1}\) 是最高有效位(most significant bit)，同时定义整数的汉明权重(Hamming weight)是其二进制表示中 \(1\) 的数量。
另一种常用的表示方法被称为十六进制系统(hexadecimal positional system)。该标识系统将每个整数表示为一组 16 个字符构成的序列。通常情况下，我们选择的字符为 \(\{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f\} \)。
如无特殊说明，在本书中，我们将使用十进制表示数字。值得注意的是，在现实世界的密码学系统中，我们经常需要处理大整数。在这种情况下，我们一般选择十六进制系统，因为十六进制相比于十进制表示一个整数的长度更短。
sage: NN(27713).str(2) # 二进制表示
'110110001000001'
sage: NN(27713).str(16) # 十六进制表示
'6c41'
如果某个进制系统选择了 \(k\) 进制，使用以下字符集 \(\{d_0,d_1,\ldots, d_{k-1}\}\) 表示一个整数的结果为 \(d_{j_h}\cdots d_{j_1} d_{j_0}\)。我们可以通过以下公式将其转化为由十进制表示的整数 \(n\) ：
\[ n = \sum_{i=0}^h j_i\cdot k^{i} \]
通过类似公式，我们可以将一个整数从当前的进制系统转化到任何其他进制系统。因此，十进制并不是特殊的，只是最常见的。为了处理进制产生的歧义，许多计算机系统使用在数字前增加前缀的方法标识当前整数所处的进制体系。常见的前缀有：
\[ \begin{array}{cc} 0x & hexadecimal \\ 0b & binary \end{array} \]
示例 6
为理解整数表达式和整数本身的不同，请将表达式 \(11\) 视为整数表达。请注意，在不声明进制的情况下，此表达式是有歧义的。它有可能表示十进制系统的整数 \(11\)，也有可能是二进制中的\(11\)，该值等同于十进制中的\(3\)。当然，\(11\) 也可能指十六进制系统内的数字，其等同于十进制中的 \(17\)。为澄清歧义，我们有必要在整数前增加前缀：
\[ \begin{array}{cc} 0x11 &= 17 \\ 0b11 &= 3 \end{array} \]
示例 7
使用上述公式将十六进制数字 \(\{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f\} \) 转化为十进制：
\[\{0_0,1_1,2_2,3_3,4_4,5_5,6_6,7_7,8_8,9_9,a_{10},b_{11},c_{12},d_{13},e_{14},f_{15}\}\]
如果你想转化 \(y=0x3f7a\) 为十进制进制，你需要将其写为 \(0x3_3f_{15}7_7a_{10}\) ，然后使用对应公式进行转化，如下：
$$ \begin{align*} n&=\sum_{i=0}^4 j_i\cdot 16^{i} \\ &=10\cdot 16^0+7\cdot 16^1+15\cdot 16^2+3\cdot 16^3 \\ &= 16250 \end{align*} $$
练习 13. 已知八进制系统，通常使用 \(\{0,1,2,3,4,5,6,7\}\) 作为表示集合。使用八进制的数字通常带有前缀 \(0o\) 。请写出 \(0o1354\) 和 \(0o777\) 的十进制表示。