埃拉托色尼筛法
埃拉托色尼筛法（，），或作埃拉托斯特尼筛法，簡稱-{zh-cn:埃氏筛; zh-tw:埃氏篩; zh-hk:愛氏篩}-，是一种用來質數的筛法，得名於古希臘數學家埃拉托色尼。其基本步骤是從最小的質數2開始，將该質數的所有倍數標記成合數，而下一个尚未被标记的最小自然数3即是下一个質數。如此重复这一过程，将各个质数的倍数标记为合数并找出下一个质数，最终便可找出一定範圍內所有質數。 埃拉托色尼筛法可能在埃拉托色尼的时代之前就已经为人所知，并记载…
标签：#素性测试
共 9 篇文章
素性测试
素性测试或素数判定，是檢驗一個給定的整數是否為質數的测试。 素数 質數是除了自身和1以外，没有其它素数因子的自然数。自从欧几里得证明了有无穷个素数以后，人们就企图寻找一个可以构造所有素数的公式，寻找判定一个自然数是不是素数的方法。因为素数的地位非常重要。 素数判定的历史 鉴别一个自然数是素数还是合数，这个问题在中世纪就引起人们注意，当时人们试图寻找質数公式，到了高斯时代，基本上确认了简单的質数公式是不存在的，因此，高斯认为对素性判定是一…
费马素性检验
费马素性检验是一种質數判定法則，利用随机化算法判断一个数是合数还是可能是素数。 概念 根据费马小定理：如果 p 是素数，1 \le a \le p-1，那么 :a^{p-1} \equiv 1 \pmod{p}。 如果我们想知道 n 是否是素数，我们在中间选取 a，看看上面等式是否成立。如果对于数值 a 等式不成立，那么 n 是合数。如果有很多的a能够使等式成立，那么我们可以说 n 可能是素数，或者伪素数。 在我们检验过程中，有可能我们…
米勒-拉宾检验
米勒-拉賓質數判定法（）是一种質數判定法則，利用随机化算法判断一个数是合数还是可能是素数。1976年，卡内基梅隆大学的计算机系教授首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，於1980年，由以色列耶路撒冷希伯來大學的麥可·拉賓}-教授作出修改，提出了不依赖于该假设的随机化算法。 概念 首先介绍一个相关的引理。我们发现 1^2 \bmod p 和 (-1)^2\bmod p 总是得到 1，我们称 -1 和 1 是…
卢卡斯-莱默检验法
卢卡斯-莱默检验法（），是数学中检验梅森数的素性检验，由法國數學家爱德华·卢卡斯（）于1878年完善，美國數學家德里克·亨利·莱默（）随后于1930年代将其改进。 因特网梅森質数大搜索用这个检验法找到了不少很大的質数，最近几个最大的質数就是这个项目发现的。由于梅森数比随机选择的整数更有可能是質数，因此他们认为这是一个极有用的方法。 方法 卢卡斯－莱默检验法原理是这样： 令梅森数 Mp = 2p− 1作为检验对象（预设p是質数，否则Mp就…
AKS質數測試
AKS質數測試（又稱Agrawal–Kayal–Saxena質數測試和Cyclotomic AKS test）是一個決定型質數測試演算法 ，由三個來自的計算機科學家，、和，在2002年8月6日發表於一篇題為質數屬於P的論文。作者們因此獲得了許多獎項，包含了2006年的哥德爾獎和2006年的富尔克森奖。這個演算法可以在多項式時間之內，決定一個給定整數是質數或者合數。 重要性 AKS最關鍵的重要性在於它是第一個被發表的一般的、多項式的、確定…
Prime95
Prime95是一款运行于Windows中的开源软件，由寻找梅森質数的分布式计算项目GIMPS的乔治·沃特曼编写。 Prime95的另外一个作用是用于测试计算机系统的稳定性。由于该软件需要进行大量的运算工作，所以可以有效的测试计算机系统的稳定性。在许多的测试中被使用。 Prime95的Linux及FreeBSD版本稱為MPrime。 Prime95在PC爱好者和超频爱好者中很流行，因为它的数字“粉碎”算法能够很好的测试系统的稳定性。这个…
普罗斯定理
普罗斯定理是數論的一個定理，可以判斷普罗斯数是否是質數。 如果p是普罗斯数，也就是滿足k2n + 1形式的數，其中k為奇數，且k n，那么如果对于某个整数a，有 :a^{(p-1)/2}\equiv -1 \pmod{p}\,\! 则p是素数。此時p稱為普罗斯質數。这是一个有实际用途的方法，因为如果p是素数，任何选定的a都有百分之50的機會滿足這個關係式。 若a是是模p的二次非剩余，則上述定理的逆定理也成立，因此有一種可以找a的方式，就…
试除法
试除法是整数分解演算法中最简单和最容易理解的演算法。首次出現於義大利數學家費波那契出版於1202年的著作。 给定一个待分解的正整數n，试除法是用小于等于\sqrt{n}的每个素数去试除。如果找到一个数能够整除除尽，这个数就是可分解整数的因數。若n為合數，則试除法一定能够找到n的質因數，因為n最小的質因數不大於其平方根，所以如果这个演算法“失败”，也就证明了n是个素数。 某种意义上说，试除法是个效率非常低的演算法，如果从2开始，一直算到\…