作者jeff94lee (陶德)
看板Prob_Solve
标题[问题] 大质数寻找
时间Mon Jul 6 14:10:47 2009
如果要做到大质数的检验
例如:512bit的质数
除了要用大数运算为基础之外
那在检验 质数 有没有一个比较有效率的演算法?
我有在wiki看到一个叫做Miller–Rabin primality test
http://tinyurl.com/ql8l99
可是实做的时候 我发现程式执行会卡在
a^d mod n
因为a我虽然用2 但是d的大小 几乎是500bit
相当於十进位的 150位
虽然说mod 可以用 a^0 mod n
再用(a^0 mod n * a)mod n做
不过那还是得执行上 十进位150位 次数
才能把d的次数给跑完
请问我对这个演算法的理解有错误吗?
还是说有其他的演算法可以找 这类的大质数???
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.204.203.93
1F：推 suhorng:ACM 374, Big Mode 可以做到 O(logd) 07/06 19:13
2F：→ suhorng:举例来说， a^4 = (a^2)^2, a^5 = (a^2)^2 * a 07/06 19:14
3F：→ suhorng:所以可以递回下去，用 Divide and Conquer 的作法 07/06 19:14
4F：→ netsphere:印度阿三在2004年有发表在O(N)时间内质数的检验 07/06 22:26
5F：→ ledia:AKS ? 听说真正实作起来效率不是很好 ? XD 07/07 01:53
6F：→ suhorng:咦 ? 可是 AKS 不是 O(lg^6 n) 吗 ? 07/07 08:37
7F：→ netsphere:因为O(lg^6 n) < O(N) 所以没错阿 XD 07/10 10:01
8F：推 ledia:我所听说的是, AKS 的确是 O(lg^6 n) 但实作复杂, 常数很大 07/12 21:32