作者Knighter (爱吃苹果的孩子)
站内Prob_Solve
标题Re: [问题] 大质数寻找
时间Sun Aug 30 15:59:15 2009
※ 引述《jeff94lee (陶德)》之铭言：
: 如果要做到大质数的检验
: 例如: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的次数给跑完
: 请问我对这个演算法的理解有错误吗?
: 还是说有其他的演算法可以找 这类的大质数???
可以用i/根号i 喔!!!!!
32767 整数可以嘛
够用吗????
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.126.151.109
1F：→ suhorng:150位开个根号也大概有75位，会跑到死... 08/30 17:18
2F：嘘 hayden0828:C版闹过换来这闹 08/30 21:45