Ale*_*lex 4 primes cryptography
我是大学生,有一项任务,需要找到大的素数.教授给了我以下"简单"算法,找到2个可能的素数.
第3步的示例.
假设p = 5
1 ^ 4%5 = 1
2 ^ 4%5 = 1
3 ^ 4%5 = 1
4 ^ 4%5 = 1
这表明5是素数.
我通过这个任务意识到计算素数不是开玩笑.我用上述算法看到的问题是,如果我猜测大数并用模幂运算测试它们,我可能会尝试将大数字增加到一个大数.这让我怀疑.我已经研究了确定性有限自动机和Eratosthenes的筛子.有没有人有任何建议要么改进给定的算法或提供任何形式的帮助？谢谢你的时间.
您所遵循的算法称为费马素性测试.但是,您的解释有几个问题:
你说"确认gcd(a,p)<1".这没有意义,因为gcd永远不会少于一个.你可以检查的是gcd(a,p)== 1.如果它不是1,则p不是素数.这可以检测出卡迈克尔的数字,但可能只有很小的机会这样做.
测试的方式是,对于p的某个值,你选择a的几个随机值并检查是否^(p-1)%p == 1.如果其中一个不是1,那么p isn素数.您选择的值越多,您的准确度就越高.
你肯定无法检查x的所有值 - 因为有太多要检查的东西.
有一种快速的方法可以执行模幂运算,即使对于大的基数和指数也是如此.请参阅Wikipedia文章.您仍然需要一个方法来对大整数执行乘法和模运算.
Eratosthenes的筛子仅用于寻找小素数.
该测试可能错误地确定Carmichael数字是素数.其他算法如Rabin-Miller没有这个问题.
| 归档时间： |
|
| 查看次数： |
325 次 |
| 最近记录： |