wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
大整数分解以及素数判定
? 数学 ?
2017-03-19 20:39:39
558
0
0
wuvin
? 数学 ?
来填一下这个坑吧 这两个随机算法还是很好懂的 ##MR算法 素数判定 首先想必大家都知道费马小定理 >如果n是质数，一定有$a^{n-1} \equiv 1 \pmod n$ 那么逆否命题正确性与原命题相同，也就是 >如果 $a^{n-1} \equiv 1 \pmod n$ , $n$一定为合数 **注意：这里没有说这个为1是n是质数，但不为1一定是合数** 所以如果要判断n是否是质数只需要选取多个a，再利用快速幂来判定n 如果多个a都说n是不是合数了，那么n基本上就是一个质数了 该测试单次正确的概率是75%所以多测试几次即可。 **接下来就是巧妙的rho因数分解了（复杂度O(n^1/4 logn)）** (原文有错，留坑待填)
上一篇:
BSGS
下一篇:
BZOJ 2090 [Poi2010] Monotonicity 2
0
赞
558 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册