求闻百科
搜索
切换搜索
切换菜单
切换个人菜单
查看“素性测试”的源代码
求闻百科,共笔求闻
更多语言
阅读
查看源代码
查看历史
页面
讨论
更多操作
←
素性测试
因为下列原因,您没有权限编辑该页面。请逐条确认下列问题是否解决后再试。
您所请求的操作,仅限具有
注册用户
权限的
用户
执行。
若您尚未登录求闻百科账号,请您
登录
求闻百科账号后操作。
您尚未完成实名制验证,因此操作受限。请尽快
完成实名制验证
,或联系
裁决委员会
以
获取操作权限
。
注:若您是非中国大陆用户,您应当联络电子邮件staff
qiuwen.org以获得帮助。
您尚未完成
电子邮件确认
,因此操作受限,请尽快
完成电子邮件确认
。
若您无法完成前述手续,请参考
帮助文档
,或通过适当渠道请求管理员或裁决委员协助。
您可以查看和复制此页面的源代码。
若您无权编辑本页面,您可以
提出编辑请求
,提请有权限者代为编辑。
{{NoteTA |G1 = Math }} '''素性测试'''或'''素数判定''',是檢驗一個給定的整數是否為[[質數]]的测试。 == 素数 == {{main|素数}} [[質數]]是除了自身和[[1]]以外,没有其它素数因子的[[自然数]]。自从[[欧几里得]]证明了有无穷个素数以后,人们就企图寻找一个可以构造所有素数的公式,寻找判定一个自然数是不是素数的方法。因为素数的地位非常重要。 == 素数判定的历史 == 鉴别一个自然数是素数还是合数,这个问题在中世纪就引起人们注意,当时人们试图寻找[[質数公式]],到了高斯时代,基本上确认了简单的質数公式是不存在的,因此,高斯认为对素性判定是一个相当困难的问题。从此以后,这个问题吸引了大批数学家。 質性判斷演算法可分為兩大類,確定性演算法及隨機演算法。前者可給出確定的結果但通常較慢,後者則反之。詳見以下列表。 == 確定型演算法 == * 試除法([[埃拉托斯特尼篩法]]) ** 嘗試從 <math>2</math> 到 <math>\sqrt{N}</math> 的整數是否整除 <math>N</math>。 <syntaxhighlight lang="c"> // 以 C 語言實現埃拉托斯特尼篩法 // 用以判斷質數的 is_prime 副函式 int is_prime(int x) { if(x < 2) return 0; // 1 不是質數,且不考慮負整數與 0,故輸入 x<=1 時回傳 0 for(int i = 2; i * i <= x; ++i) if(x % i == 0) return 0; // 一旦出現整除,回傳 0 return 1; // 迴圈跑完後都沒有整除,回傳 1 } </syntaxhighlight> * [[卢卡斯-莱默检验法]] * [[AKS質數測試]] ** PRIMES is in P這篇論文提到的方法,是第一個多項式時間的質數測試演算法。 == [[隨機演算法]] == * [[费马素性检验]] ** 利用[[費馬小定理]]來測試。 * [[米勒-拉賓檢驗]] * 歐拉-雅科比測試 ** 對於n,挑選随机的<math>a<n</math>,測試<math>( {a \over n} ) = a ^ {( n - 1) / 2} \mod n</math>,这里<math>( {a \over n} )</math>为雅可比符号。如果N為質數,等式一定成立;如果N為合數,等式有一半的機率不成立。 == 参见 == * [[素数公式]] * [[费马小定理]] * [[埃拉托斯特尼筛法]] * [[卢卡斯-莱默检验法]] * [[米勒-拉宾检验]] * [[试除法]] * [[费马素性检验]] * [[孪生素数]] * [[三胞胎素数]] * [[四胞胎素数]] * [[素数判定法则]] * [[表兄弟素数]] * [[六素数]] * [[X²+1素数]] == 外部链接 == {{数论算法}} [[Category:素性测试| ]] [[Category:非对称密钥算法]]
返回
素性测试
。