推 dreamroyc :這可以透過手算？ 06/14 18:52
→ dreamroyc :2^22 ≡ (2^11)^2 ≡ 4194304 ≡ 2574 mod 11329 06/14 18:53
→ dreamroyc :這邊數字就好大了 = = 06/14 18:53
推 dreamroyc :我看懂了，謝謝，不過是否有更快的算法？ 06/14 18:55
※ 引述《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)