# 技术分享平台

0%

## 目的

• 通过分解问题, 使无法着手解决的大问题变成容易解决的小问题
• 通过减小问题的规模, 降低解决问题的复杂度 (或计算量)

## 基本思想

1. 分解: 将问题分解为若干个规模较小, 相互独立且与原问题形式相同的子问题, 确保各个子问题的解具有相同的子结构
2. 解决: 如果上一步分解得到的子问题可以解决, 则解决这些子问题, 否则, 对每个子问题使用和上一步相同的方法再次分解, 然后求解分解后的子问题, 这个过程可能是一个递归的过程
3. 合并: 将上一步解决的各个子问题的解通过某种规则合并起来, 得到原问题的解

## 例子

### 快速傅里叶变换

• 分解思想: 计算 N 个采样点的离散傅里叶变换, 需要做 $N^2$ 次复数乘法, 按照奇偶关系分成两个 $\frac{N}{2}$ 个采样点的离散傅里叶变换, 只需要做 $(\frac{N}{2})^2 +(\frac{N}{2})^2 = \frac{N^2}{2}$ 次复数乘法, 做一次分解就使得计算量减少了一半
• 合并思想: 将两个 $\frac{N}{2}$ 点离散傅里叶变换的结果按照蝶形运算的位置关系重新排列成一个 N 点序列

### 快速排序算法

• 分解思想: 选择一个标兵数, 将待排序的序列分成两个子序列, 其中一个子序列中的数都小于标兵数, 另一个子序列中的数都大于标兵数, 然后分别对这两个子序列排序
• 合并思想: 将两个已经排序的子序列一前一后拼接在标兵数前后, 组成一个完整的有序序列

### Karatsuba 乘法算法

• 分解思想: 将 n 位大数分成两部分：$a + b$ , 其中 a 是整数幂, 然后利用乘法的分解公式：$( a + b )( c + d )= ac + ad + bc + bd$ , 将其分解为四次小规模大数的乘法计算, 然后利用一个小技巧将其化解成三次乘法和少量移位操作
• 合并思想: 用几次加法对小规模乘法的结果进行求和, 得到原始问题的解

#### 推导

$$x = x_1 M^k + x_0 \\ y = y_1 M^k + y_0$$

$$xy = (x_1 M^k + x_0)(y_1 M^k + y_0) = x_1 y_1 M^2k + (x_1 y_0 + x_0 y_1) M^k + x_1 y_0$$

$$xy = z_2 M^2k + z_1 M^k + z_0$$

$$z_1 = (x_1 + x_0)(y_1 + y_0) - x_1 y_1 - x_0 y_0 = (x_1 + x_0)(y_1 + y_0) - z_2 - z_0$$

#### 根据推导计算

$$12345=12·1000+345 \\ 6789=6·1000+789$$

$$z_2 = a \times c = 12 × 6 = 72 \\ z_0 = b \times d = 345 × 789 = 272205 \\ z_1 = ((a+b) \times (c+d) - a \times c - b \times d) \\ = (12 + 345) × (6 + 789) − z_2 − z_0 \\ = 283815 − 72 − 272205 = 11538$$

$$result = z_2 · 10^{2*3} + z_1 · 10^3 + z_0 \\ result = 72 · 10^6 + 11538 · 10^3 + 272205 = 83810205$$

#### 简单代码

Karatsuba 算法是比较简单的递归乘法, 把输入拆分成 2 部分, 不过对于更大的数, 可以把输入拆分成 3 部分甚至 4 部分, 拆分为 3 部分时, 可以使用 Toom-Cook 3-way 乘法, 复杂度降低到 $O(n^1.465)$, 拆分为 4 部分时, 使用 Toom-Cook 4-way 乘法, 复杂度进一步下降到 $O(n^1.404)$, 对于更大的数字, 可以拆成 100 段, 使用快速傅里叶变换 FFT, 复杂度接近线性, 大约是 $O(n^1.149)$, 可以看出, 分割越大, 时间复杂度就越低, 但是所要计算的中间项以及合并最终结果的过程就会越复杂, 开销会增加, 因此分割点上升, 对于公钥加密, 暂时用不到太大的整数, 所以使用 Karatsuba 就合适

#### BigInteger 的乘法实现

• 普通算法: $O(n^2)$
• Karatsuba 乘法: $O(n^{log_2 3})$
• Toom-3 乘法: $O(n^{log_3 5})$
• 复数域上的 FFT:
• $O(n {\log^* n})$
• $log^* n = log n(log log n)(log log log n) ···$
• 有限域上的 FFT: $O(n(log n)(log log n))$, 时间复杂度已经相当接近线性

• Java 7 中直接用二重循环直接相乘, 见源码第 1165 行
• Java 8 中, 根据两个因数的大小区分, 见源码第 1464 行
• 当两个因数均小于 $2^{32\times 80}$ 时, 用二重循环直接相乘, 复杂度为 $O(n^2)$, n 为因数位数
• 当两个因数均小于 $2^{32\times 240}$ 时, 采用 Karatsuba algorithm, 其复杂度为 $O(n^{\log_2 3}) \approx O(n^{1.585})$, n 为因数位数
• 否则, 采用 Toom-Cook multiplication, 其复杂度为 $O(n^{\log_3 5}) \approx O(n^{1.465})$, n 为因数位数