江苏龙网

  1. 主页 > 生活百科 > >

合数和素数的定义 素数的定义( 二 )


当a = 2时，满足费马小定理逆定理表达式的非素数n称为伪素数，如341 。同时我们可以停止扩展这个定义，即满足公式的非素数称为有底数的伪素数，比如63就是底数为8的伪素数 。
对于伪素数，它们满足乘法和可逆基，我们可以证明伪素数是无穷的 。
由于伪素数的存在，为了找到最大的素数，我们的第一个想法是在过程中通过改变A的值来重复验证，这就产生了费马素数检验 。然而，这种方法是有缺陷的 。由于费马素数检验无法检测到的卡迈克尔数的存在，卡迈克尔数的个数是无限的 。
接下来可以加强伪素数的定义，即基于雅可比法的伪素数，我们称之为基数为A的欧拉伪素数，其个数是无穷的 。
类似于费马素数检验的思路，我们随机选取A来验证二次剩余是否与雅可比公式相同，从而防止出现A为底的欧拉伪素数在A为实之后无法检测的结果，我们把这种检测方法称为Solovay-Stassen素数检验 。但算法复杂度略高 。
然后，我们加强了伪素数的定义，根据中国留数定理(其中s满足2∧s || n-1)算出了s个公式的方程组 。一个球面的分解称为底数为A的强伪素数，强伪素数的个数仍然是无限的 。在这种情况下，奇数N成为以A为底的强伪素数的概率≤ 25% 。
类似于前两种素数检验方法，我们随机选择一种停止递归计算，失去米勒-拉宾素数检验方法 。特别地，因为米勒-拉宾素数检测方法可以应用模平方算法，所以可以降低其复杂度 。
目前测试素数最快的算法是APRCL算法，最贵的是ECPP算法，但都不能在多项式时间内实现 。2002年印度多少数学家出了AKS素数测试，但是因为常数太大，现在申请成本不算太高 。
从密码学的角度来说，素数检验的重要目标是具有自然素数的RSA公钥体制，也是数字分析数学问题中不可缺少的一部分 。
以上是质数测试的大致线索，此人错误已破 。P.S .以上为集团整改，请勿转载！
以上内容就是为各人分享的素数的界说（合数跟素数的界说）相干常识，愿望对你有所帮忙 ，假如还想搜寻其余成绩，请珍藏本网站或点击搜寻更多成绩 。


推荐阅读


上一篇：孙红雷|孙红雷罕见携小15岁娇妻亮相，身材高挑状态好，气质优雅力压那英

下一篇：纸老虎打一成语谜底 纸老虎打一成语