作者mgtsai ()
看板Math
标题Re: [中学] 求余数
时间Tue Jun 14 12:57:31 2011
※ 引述《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)
1F：推 dreamroyc :这可以透过手算？ 06/14 18:52
2F：→ dreamroyc :2^22 ≡ (2^11)^2 ≡ 4194304 ≡ 2574 mod 11329 06/14 18:53
3F：→ dreamroyc :这边数字就好大了 = = 06/14 18:53
4F：推 dreamroyc :我看懂了，谢谢，不过是否有更快的算法？ 06/14 18:55