Re: [中學] 求餘數
※ 引述《dreamroyc ()》之銘言：
: N = 11329 , a=2
: 11329 -1 = 11328 = 2^6 * 177
: 2^177 mod 11329
: 是看到答案會是10043，但是這個miller-rabin演算法會需要一直取mod
: 數字都很大，所以想請教如何算？
177 = 2^7 + 2^5 + 2^4 + 2^0
2^1 ≡ 2 mod 11329
2^2 ≡ (2^1)^2 ≡ 4 mod 11329
2^5 ≡ (2^2)^2 * 2 ≡ 32 mod 11329
2^11 ≡ (2^5)^2 * 2 ≡ 2048 mod 11329
2^22 ≡ (2^11)^2 ≡ 4194304 ≡ 2574 mod 11329
2^44 ≡ (2^22)^2 ≡ 6625476 ≡ 9340 mod 11329
2^88 ≡ (2^44)^2 ≡ 87235600 ≡ 2300 mod 11329
2^177 ≡ (2^88)^2 * 2 ≡ 5290000 * 2 ≡ 10686 * 2 ≡ 10043 mod 11329
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.250.129.52
※ 編輯: mgtsai 來自: 60.250.129.52 (06/14 13:06)
推
06/14 18:52, , 1F
06/14 18:52, 1F
→
06/14 18:53, , 2F
06/14 18:53, 2F
→
06/14 18:53, , 3F
06/14 18:53, 3F
推
06/14 18:55, , 4F
06/14 18:55, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
中學
完整討論串 (本文為第 5 之 10 篇)：
中學
1
1
中學
4
6
中學
中學
1
1
中學
1
1
中學
2
4
中學
中學
1
3
中學
1
1
中學
1
1