TA貢獻(xiàn)1998條經(jīng)驗(yàn) 獲得超6個(gè)贊
好的，所以你要計(jì)算a^b mod m。首先，我們將采取一種天真的方法，然后看看我們?nèi)绾胃倪M(jìn)它。
首先，減少a mod m。這意味著，找到一個(gè)數(shù)字，a1以便0 <= a1 < m和a = a1 mod m。然后在一個(gè)循環(huán)中重復(fù)乘以a1并再次減少mod m。因此，在偽代碼中：
a1 = a reduced mod m
p = 1
for(int i = 1; i <= b; i++) {
p *= a1
p = p reduced mod m
}
通過(guò)這樣做，我們避免大于的數(shù)字m^2。這是關(guān)鍵。我們避免數(shù)字大于的原因m^2是因?yàn)樵诿恳徊? <= p < m和0 <= a1 < m。
舉個(gè)例子，讓我們來(lái)計(jì)算吧5^55 mod 221。首先，5已經(jīng)減少了mod 221。
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
112 * 5 = 118 mod 221
118 * 5 = 148 mod 221
148 * 5 = 77 mod 221
77 * 5 = 164 mod 221
164 * 5 = 157 mod 221
157 * 5 = 122 mod 221
122 * 5 = 168 mod 221
168 * 5 = 177 mod 221
177 * 5 = 1 mod 221
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
112 * 5 = 118 mod 221
118 * 5 = 148 mod 221
148 * 5 = 77 mod 221
77 * 5 = 164 mod 221
164 * 5 = 157 mod 221
157 * 5 = 122 mod 221
122 * 5 = 168 mod 221
168 * 5 = 177 mod 221
177 * 5 = 1 mod 221
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
112 * 5 = 118 mod 221
118 * 5 = 148 mod 221
148 * 5 = 77 mod 221
77 * 5 = 164 mod 221
164 * 5 = 157 mod 221
157 * 5 = 122 mod 221
122 * 5 = 168 mod 221
168 * 5 = 177 mod 221
177 * 5 = 1 mod 221
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
因此，5^55 = 112 mod 221。
現(xiàn)在，我們可以通過(guò)使用取冪進(jìn)行平方來(lái)改善這一點(diǎn); 這是著名的技巧，其中我們將求冪減少到只需要log b乘法而不是b。請(qǐng)注意，使用上面描述的算法，通過(guò)平方改進(jìn)進(jìn)行求冪，最終得到了從右到左的二進(jìn)制方法。
a1 = a reduced mod m
p = 1
while (b > 0) {
if (b is odd) {
p *= a1
p = p reduced mod m
}
b /= 2
a1 = (a1 * a1) reduced mod m
}
因此，因?yàn)?5 = 110111二進(jìn)制
1 * (5^1 mod 221) = 5 mod 221
5 * (5^2 mod 221) = 125 mod 221
125 * (5^4 mod 221) = 112 mod 221
112 * (5^16 mod 221) = 112 mod 221
112 * (5^32 mod 221) = 112 mod 221
所以答案是5^55 = 112 mod 221。這有效的原因是因?yàn)?/p>
55 = 1 + 2 + 4 + 16 + 32
以便
5^55 = 5^(1 + 2 + 4 + 16 + 32) mod 221
= 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221
= 5 * 25 * 183 * 1 * 1 mod 221
= 22875 mod 221
= 112 mod 221
在我們計(jì)算步驟5^1 mod 221，5^2 mod 221等我們注意到5^(2^k)= 5^(2^(k-1)) * 5^(2^(k-1))因?yàn)?^k = 2^(k-1) + 2^(k-1)這樣我們就可以首先計(jì)算5^1和減少mod 221，那么這個(gè)平方和降低mod 221以獲得5^2 mod 221等
上述算法形式化了這個(gè)想法。
TA貢獻(xiàn)2065條經(jīng)驗(yàn) 獲得超14個(gè)贊
您可以使用指數(shù)的二進(jìn)制擴(kuò)展來(lái)加快進(jìn)程（這可能對(duì)非常大的指數(shù)有用）。首先計(jì)算5,5 ^ 2,5 ^ 4,5 ^ 8 mod 221 - 你通過(guò)重復(fù)平方來(lái)做到這一點(diǎn)：
?5^1 = 5(mod 221)
?5^2 = 5^2 (mod 221) = 25(mod 221)
?5^4 = (5^2)^2 = 25^2(mod 221) = 625 (mod 221) = 183(mod221)
?5^8 = (5^4)^2 = 183^2(mod 221) = 33489 (mod 221) = 118(mod 221)
5^16 = (5^8)^2 = 118^2(mod 221) = 13924 (mod 221) = 1(mod 221)
5^32 = (5^16)^2 = 1^2(mod 221) = 1(mod 221)
現(xiàn)在我們可以寫(xiě)了
55 = 1 + 2 + 4 + 16 + 32
so 5^55 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32?
? ? ? ? = 5? ?* 25? * 625 * 1? ? * 1 (mod 221)
? ? ? ? = 125 * 625 (mod 221)
? ? ? ? = 125 * 183 (mod 183) - because 625 = 183 (mod 221)
? ? ? ? = 22875 ( mod 221)
? ? ? ? = 112 (mod 221)
你可以看到非常大的指數(shù)如何更快（我相信它是log而不是b中的線(xiàn)性，但不確定。）
TA貢獻(xiàn)1833條經(jīng)驗(yàn) 獲得超4個(gè)贊
/* The algorithm is from the book "Discrete Mathematics and Its
Applications 5th Edition" by Kenneth H. Rosen.
(base^exp)%mod
*/
int modular(int base, unsigned int exp, unsigned int mod)
{
int x = 1;
int power = base % mod;
for (int i = 0; i < sizeof(int) * 8; i++) {
int least_sig_bit = 0x00000001 & (exp >> i);
if (least_sig_bit)
x = (x * power) % mod;
power = (power * power) % mod;
}
return x;
}
舉報(bào)