分解质因数 - 科创

文号

t34068

阅读

16536

分解质因数

ltl

2011/06/06

软件综合

IP:福建

看到刚才那个关于质数表的提问之后大概能猜得到你的因式分解也快不到哪里去吧……我就贴个刚刚写的时间复杂度O(n^0.5)的程序吧

来自：

15年7个月前IP:未同步

298662

1楼

说到因式分解就想到RSA..

引用

celeron533 千古风流

15年7个月前IP:未同步

298770

2楼

引用第1楼qqq1243于2011-06-06 22:04发表的 :
说到因式分解就想到RSA..

可以下一个GPG的源码自己研究一下。
RSA核心就是生成大质数，在判断是否是质数的时候用到快速除法、1-9999内嵌质数表，以及LZ提到的用算出来的质数继续验证
最后做N次费马测试，能通过的基本上是个质数了

引用

作者

15年7个月前IP:未同步

298790

3楼

费马测试的反例不是遍地都是么……

引用

caoyuan9642 千古风流

15年7个月前IP:未同步

298794

4楼

M-R算法成功率可以任意高。。而且木有反例。
或者直接Java..

引用

作者

15年7个月前IP:未同步

298838

5楼

我说的是费马小定理判定质数的反例遍地都是………………

引用