大整數乘法演算法深度解析：基線乘法 vs Comba 乘法原理與效能差異

大整數乘法演算法深度解析：基線乘法 vs Comba 乘法

在公開金鑰密碼體系（RSA、ECC、DH）中，模冪運算的核心是大整數乘法，其效能直接決定加密解密速度。雖然基線乘法與 Comba 乘法時間複雜度同為 O(n²)，但實際效能差異顯著。本文從原理層面深度剖析兩者差異，為後續實作優化奠基。

基線乘法：直觀的筆算模擬

模擬人工豎式乘法：被乘數每位與乘數每位相乘，**即時處理進位**。

    1 2 3
  × 4 5 6
  -------
    7 3 8   ← 3×6=18, 進位1 → 2×6+1=13, 進位1 → 1×6+1=7
  6 1 5     ← 3×5=15, 進位1 → 2×5+1=11, 進位1 → 1×5+1=6
4 9 2       ← 3×4=12, 進位1 → 2×4+1=9, 進位0 → 1×4=4
-------
5 6 0 8 8

雙重迴圈中每次單精度乘法後立即做進位傳遞，導致強資料相依，難以指令級並行（ILP）與向量化。

Comba 乘法：列向累加，延遲進位

核心思想：**按「列」累加所有部分積，最後統一處理進位**。

    1 2 3
  × 4 5 6
  -------
列 0: 3×6 = 18
列 1: 2×6 + 3×5 = 12+15 = 27
列 2: 1×6 + 2×5 + 3×4 = 6+10+12 = 28
列 3: 1×5 + 2×4 = 5+8 = 13
列 4: 1×4 = 4
統一進位傳遞 → 5 6 0 8 8

優勢：

• 減少進位操作：從 n² 次降至 ~2n 次
• 內層迴圈無進位邏輯，易於編譯器優化（循環展開、SIMD、暫存器分配）
• 適合並行化：各列獨立累加，最後歸約

溢位風險與三精度變數

列累加時部分積總和可能超過雙精度範圍。設單精度 w 位元（通常 32 或 64），最大單精度值 B-1 = 2^w-1。最長列有 min(n,m) 項，最大累加值：

max_sum = min(n,m) × (B-1)²

需 k 精度滿足 B^k > max_sum。對 w=32, n≤25600，三精度（96 位）足夠（可容納 ~4.3×10⁹ 項）；w=64 時三精度更是綽綽有餘（~1.8×10¹⁹ 項）。實作常用三個單精度變數 c0, c1, c2 模擬三精度。

Comba 乘法演算法步驟

1. 結果陣列 c 清零，長度 a.used + b.used
2. 初始化三精度累加器 c2=c1=c0=0
3. 對結果每位 i = 0 .. c.used-1：
   1. 決定參與累加的部分積範圍：
      ty = min(i, b.used-1)
tx = i - ty
k = min(a.used - tx, ty + 1)
   2. 三精度右移一位（相當於除以 B，保留進位）
   3. 累加 k 個部分積：(c2||c1||c0) += a[tx+j] * b[ty-j], j=0..k-1
   4. 當前位 c[i] = c0（低精度部分）
4. 壓縮前導零，返回結果

範例追蹤：12345 × 678

a.used=5, b.used=3, c.used=7

最終經進位傳遞得 8369910 ✓

總結與展望

Comba 乘法透過「列向累加 + 延遲進位」大幅減少進位操作與資料相依，是大整數庫（如 OpenSSL BN、LibTomMath、MPIR）的標準實作基礎。下一篇將探討：

• 無雙精度型別環境下的實作技巧（如 64 位平台無 128 位整數）
• x86/x64 內聯組合語言優化（MUL/ADC 指令、暫存器分配）
• Karatsuba、Toom-Cook、FFT 乘法等次二次方演算法的切換閾值策略