蒙哥馬利算法
我試圖了解它是如何工作的以及如何實現 本文中描述的算法。該論文展示了一種計算模乘的方法，其中使用了解析度小於輸出解析度的乘法器。例如，如果我想對 2 個 1024 位數字進行模乘，我可以使用 16 位加法器。
為了簡單起見，我提取了算法：
$ S = 0\ for\ i=0\ to\ (m-1)\ loop\ \ \ \ \ (C,S^{(0)}) := x_i\cdot Y^{(0)}+S^{(0)}\ \ \ \ \ if\ S^{(0)}{0} = 1\ then\ \ \ \ \ \ \ \ \ (C,S^{(0)}) := (C,S^{(0)}) + M^{(0)}\ \ \ \ \ \ \ \ \ for\ j = 1\ to\ e-1\ loop\ \ \ \ \ \ \ \ \ \ \ \ \ (C,S^{(j)}) := C+ x_i \cdot Y^{(j)} + M^{(j)} + S^{(j)}\ \ \ \ \ \ \ \ \ \ \ \ \ S^{(j-1)} := (S_0^{(j)},S^{(j-1)}{w-1..1}) \ \ \ \ \ \ \ \ \ end\ loop\ \ \ \ \ \ \ \ \ S^{(e-1)} := (C,S^{(e-1)}{w-1..1})\ \ \ \ \ else\ \ \ \ \ \ \ \ \ for\ j = 1\ to\ e-1\ loop\ \ \ \ \ \ \ \ \ \ \ \ \ (C,S^{(j)}) := C+ x_i \cdot Y^{(j)} + S^{(j)}\ \ \ \ \ \ \ \ \ \ \ \ \ S^{(j-1)} := (S_0^{(j)},S^{(j-1)}{w-1..1}) \ \ \ \ \ \ \ \ \ end\ loop\ \ \ \ \ \ \ \ \ S^{(e-1)} := (C,S^{(e-1)}_{w-1..1})\ \ \ \ \ end\ if\ end\ loop\ $
我在哪裡：
- $ \S $ 是結果
- $ M $ 是模組
- $ Y $ 是被乘數
- $ X $ 是乘數和 $ x_i $ 是單個位（例如 $ X = (x_n,…,x_1,x_0) $ .
- 上標是詞向量（例如 $ M = (0,M^{e-1},…,M^1,M^0) $
- $ (A,B) $ 是兩個位向量的串聯。
- $ m $ 是操作數寬度
- $ w $ 是所選單詞的寬度
- $ e $ 是數量 $ w $ 完成向量所需的位 ( $ e = \lceil(m+1)/w\rceil $
我不明白作者對變數的意思 $ C $ . 應該是carry，但問題是我不明白他們用的是什麼carry，難道是之前上癮的carry？
PS在論文中寫道 $ C $ 在範圍內 $ [0,2] $ . 因此， $ C $ 用 2 位表示。問題是在算法中有這一步：
$ S^{e-1} := (C,S^{e-1}_{w-1..1}) $
它表示 的串聯：
- $ C $ : $ 2 $ 位。
- $ S^{e-1}_{w-1..1} $ : $ w - 1 $ 位。
所以串聯是 $ w + 1 $ 位，這應該是不可能的。我的錯誤在哪裡？
混亂來自於代表的選擇。我會快速查看參考論文，其中作者使用 2 基數表示。然後你應該初始化 $ e=\frac{m+15}{w} $ 代替 $ e=\frac{m+1}{w} $ 當您使用 16 位加法器時！最好再讀一遍 PL Montgomery 的開創性論文：http ://web.itu.edu.tr/~orssi/dersler/cryptography/Montgomery.pdf
並且這個 remak 解釋了在模數中設置為零的附加詞。
蒙哥馬利介紹的方法很聰明，需要進行更改或表示，如論文中所述。該方法還允許重疊 mul 和 ReduC 過程。我還確認 C 代表需要保持 2 位的進位。與經典方法相比，有趣的是進位傳播是從右到左移動的，恰好是掃描操作數的方向。這就是 Mult-ReduC 可以重疊的原因，在硬體設計中非常重要。