109541是质数还是合数,怎样快速判断?

linky_19822022-10-04 11:39:541条回答

109541是质数还是合数,怎样快速判断?
不要穷举法和计算机算法
你所提到的算法能给我简单介绍一下吗?

已提交,审核后显示!提交回复

共1条回复
xhjack 共回答了17个问题 | 采纳率70.6%
是质数.
我是学计算机的,目前在此行业判断质数还是要靠大量的计算的,不过利用算法,可以大大的减少计算的次数.如果有其他快速的判断方法,那密码界的某个加密算法就要面临淘汰了.
一个简单的算法就是遍历,从2开始到SQRT(要判断的数),看有没有约数.
另一个是在学网络信息安全时学的一个算法,挺复杂的,RSA加密算法的一部分,它在进行s次运算后,能判断一个数是质数的准确率达到1-1/(2^S).想想吧,当S=10,这个概率就是99.999%.
判断的依据是:
命题;如果一个数p是素数,则方程:
X^2=1 mod p只有平凡解即:X=+-1 mod p
证明:
X^2=1 mod p
->p|(X^2-1) |表示整除
->P|(X-1)(X+1)
->P|(X-1)或P|(X+1)
->X+1=KP 或 X-1=JP
->X=1 MOD P 或X= -1 MOD P
如果需要算法,可以看Miller and Rabin,WITNESS算法.
1年前

相关推荐

大家在问