数论与群论密码学-01-算术的时间复杂度

进位制计数法

首先考察自然数的表示方法。虽然通常意义上的加法与乘法在皮亚诺公理所定义的一进制系统下有很清晰的定义,然而其运算却需要相当多的操作。例如,计算一进制表达的两数 \(n\)\(m\) 之和,需要的操作数量几乎正比于 \(n\) (“几乎正比” 为不严格意义下 \(\Theta(n)\) 的表达)。而一进制下乘法的运算复杂程度则更甚,为 \(\Theta(nm)\)。之所以如此的原因为,一进制下表达(编码)数 \(n\) 需要的符号个数为 \(\Theta(n)\)

而更加优越的进位制计数法则被用于减少运算的复杂度。一般地,在进位制计数法中,给定一基底 \(b~(b \in \mathbb{N},~b \ge 2)\),我们可以表示任意自然数 \(n \in \mathbb{N}\) 为:

\[ \begin{aligned} n &= d_{k-1}b^{k-1} + d_{k_2}b^{k-2} + \cdots d_1 b + d_0 \\ &= \prod_{i=0}^{k-1} d_i b^i \end{aligned} \]

其中 \(d_{k-1} \ne 0\)\(0 \le d_i < b\), for \(0 \le i < k\).

这样,我们将 \(b\) 进制下的 \(n\) 表示为

\[ n = \left( d_{k-1}, \cdots, d_0\right)_b \]

注意:我们有

\[ \underbrace{b^{k-1}\le}_{d_{k-1} \ne 0} n \underbrace{\le b^{k}}_{d_{k-1}<b} \]

在不等式各部分上取 \(log_b\left(\cdot\right)\),我们有:

\[ k-1 \le log_b n < k\\ k-1 = \lfloor log_b n \rfloor \]

因此,\(b\) 进制计数法中表达数 \(n\) 的位数大约正比于 \(log(n)\)。其中对数的底可由换底公式任意设定,因为比例常量无关紧要。

\(b = 10\) 时,该系统表示日常生活使用的十进制。当 \(b = 2\) 时,该系统表示计算机存储及运算时使用的二进制。另外,我们称一个二进制位为一比特。

加法运算

在进位制下计算两数 \(n\)\(m\) 之和时,我们将对应位上的数以及上一位运算所得到的进位相加,产生该位的和与下一位的进位。同时,我们设进入到第 \(0\) 位的进位为 \(0\)。由于任一数位的运算结果均取决于上一位的进位,因此进位制下的加法运算复杂度为 \(\Theta(max\{log(n), log(m)\})\)。这里我们忽略计算机实际运算加法时额外需要的管理开支。

乘法运算

二进制下的乘法运算可以简单地由移位与多次相加实现。若 \(n\)\(k\) 比特, \(m\)\(l\) 比特,并且不失一般性地假设 \(l \le k\),我们一共需要 \(l-1\) 次移位,每次计算 \(k+1\) 位的和。因此计算二进制表示的 \(n\)\(m\) 之积,共需 \((l-1)(k+1) = lk - k + l - 1\) 步操作。于是可得二进制下的乘法运算复杂度为 \(\Theta(log(n)log(m))\)1 2

除法运算

给定正整数 \(n\), \(m\),下式

\[ n = qm + r,~ 0 \le r < m \]

唯一地确定 \(q\), \(r\)。我们分别称以 \(m\)\(n\)(即“\(n\) 除以 \(m\)”)的商数与余数,并记

\[ quo(n, m) := q\\ rem(n, m) := r \]

\(n\)\(k\) 比特, \(m\)\(l\) 比特,并且不失一般性地假设 \(l \le k\),计算除法共需 \(q\) 的比特数次减法,其中一次减法的复杂度为 \(\Theta(l)\)。那么计算除法需要的操作数为 \((k-l+1)l \le kl\),因此复杂度为 \(\Theta(log(n)log(m))\)


因此我们发现,使用进位制表达整数相对于一进制来说,就储存与运算效率而言要更优越。

最后我们考察将一进制数转换为 \(b\) 进制数(其中 \(b \ge 2\))。

进制展开

方法:给定一进制数 \(n\) 与进制 \(b\)\(b \ge 2\)),逐次将商数除以 \(b\),并以逆序列出余数。

形式化地,

\(q_0 := 0\),重复计算 \(q_{i+1} := quo(q_i, b),~r_{i+1} := rem(q_i, b)\)
直至 \(q_k = 0\)
那么数 \(n\)\(b\) 进制展开则为 \((r_k, \cdots, r_1)_b\)

多项式时间算法

\(P(n_1, \cdots, m_r)\) 为一关于位数分别为 \(k_1, \cdots, k_r\) 的正整数 \(n_1, \cdots, n_r\) 的函数。那么我们说 \(P(n_0, \cdots, n_r)\) 是多项式时间可算的,若计算该函数的时间正比于 \(k_1^{d_1}\cdots k_r^{d_r}\),或者等价地,正比于 \(log(n_1)^{d_1}\cdots log(n_r)^{d_r}\)

例如,根据前文所述,进位制中的加法与乘法皆为多项式时间可算。

考虑阶乘函数 \(n!=1\cdot 2\cdots n\),该函数的时间复杂度为 \(\Theta(n^2log(n))\),因此不是多项式时间可算的。


  1. 存在更高效的 Schönhage–Strassen 算法,时间复杂度为 \(\Theta(n \log(n) \log(\log(n)))\)↩︎

  2. 本文成文以后又由 Harvey 和 Hoeven 提出了 \(\Theta(n \log n)\) 的算法。若某个猜想成立,这将是理论上能做到的最佳↩︎