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, Hardware Security以及Anomaly Detection.

Related Posts

群之可解性

首先讓我們定義G為一個群,我們說G是solvable/soluble(可解)的話代表存在filtration G = G_{0} \rhd G_{1} \rhd \cdots \rhd G_{n} = \{e\}使得說G_{i}/G_{i+1}

在數論當中群(Group)是其中一種重要的概念,代數最基本由三種結構組成:群 Group, 環 Ring, 體 Field,而群作為最基本的代數結構,也是我們在密碼系統中常常使用的,故需要先了解群的定義對於後續密碼系統分析會比較方便。

發佈留言

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

You Missed

群之可解性

群之可解性

威脅情報指標 Indicators of compromise (IoC)

威脅情報指標 Indicators of compromise (IoC)

Palo Alto Firewall URL過濾 以及 Application Block Page

Palo Alto Firewall URL過濾 以及 Application Block Page

群

NP-Completeness

NP-Completeness

異常檢測的問題分類

異常檢測的問題分類