Square Multiply 演算法

此演算法主要是針對a^{b} \, mod \, nb很大而計算機通常算不太出來的時候使用的方法,一開始z設為1,並且把指數部分拆成二進位,從左至右運算,遇到b=1時計算z的平方乘上底數再mod \, n,而b=0時計算z的平方再mod \, n即可。

舉例:a^{b} \, mod\, n = (325)^{20} \, mod \, 963 = (325)^{10100_{b}} \, mod \, 963

b’s bitsoperationz
  1
1z^{2} \cdot a \, mod \, n325
0z^{2} \, mod \, n658
1z^{2} \cdot a \, mod \, n703
0z^{2} \, mod \, n190
0z^{2} \, mod \, n469

n = (325)^{20} \, mod \, 963 = 469 \, (mod \, 963)

執行時間大概是1.5 \cdot len(b)模運算。

Scientia

我是Scientia,研究興趣包含Cryptology, Cryptographic Engineering, Security and Privacy, Computational Complexity, Quantum Cryptography, Cybersecurity, Anomaly Detection以及Hardware Security.

Related Posts

高斯消去法

    \[\begin{cases}2x + 4y - 2z = 2 \\ 4x + 9y - 3z = 8 \\ -2x - 3y + 7z = 10\end{cases}\]

為了解決上述的聯立方程系統,使用高斯消去法減少不同variable的係數來求出我們需要的結果.

Vectors

在整個線性代數中,最基本的單位就是一個向量,假設一個擁有兩個值的向量像是

    \[V = \begin{bmatrix}v_{1} \\ v_{2} \end{bmatrix}\]

向量加法假設另一組向量w一樣包含於兩個值$w = \begin{bmatr…

One thought on “Square Multiply 演算法

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You Missed

NP-Completeness

NP-Completeness

異常檢測 問題分類

異常檢測 問題分類

異常檢測 方法評估

異常檢測 方法評估

異常檢測簡介 Anomaly Detection

異常檢測簡介 Anomaly Detection

高斯消去法

高斯消去法

Vectors

Vectors