如何快速检查一个素数的素性（算法）

网上有关“如何快速检查一个素数的素性（算法）”话题很是火热 ，小编也是针对如何快速检查一个素数的素性（算法）寻找了一些与之相关的一些信息进行分析
，如果能碰巧解决你现在面临的问题，希望能够帮助到您 。

算好,我以前也研究过素数问题.现在资料还保存着.. 拿来给你分享吧. (这个算法检测速度,还是很快的,你可以试试看哦~~)

一种适合32位机器数的确定性素数判定法

作者：

王浩（great_wh@tom.com）

此论文是为发布个人研究成果与大家分享交流而提交 ，本人教育背景如下：

计算机应用专业/管理工程专业双学士

天津大学

于1995年到1999年在校就读

日期________________2006-11-28___________________

摘要

一种适合32位机器数的确定性素数判定法

作者：王浩

本文通过对米勒-拉宾非确定性素数判定法如何转化为确定性素数判定法的研究
，发现了与之相关的伪素数的一些性质，引入了伪素数的最小可判定底数的概念 ，并总结出了一些规律
。通过这些规律找出了一种特别适合32位机器数的确定性素数判定法，该方法对于32位机器数进行素数判定最多只需要进行16log(n) 次乘/除法。该方法具有实现简单、速度快的优点
，非常具有推广价值 。

本文中总结出的一些规律如果能够得到证明和推广，则有可能彻底解决把米勒-拉宾非确定性素数判定法转化为确定性素数判定法的问题 ，从而对素数判定理论和实践产生一定的促进作用
。

本文共有五章。分述如下：

第一章：讲述素数判定法的现状
，列举了目前常用的一些素数判定法及其适用范围 。

第二章：讲解伪素数表生成过程。

第三章：分析伪素数表，引入了伪素数的最小可判定底数的概念 ，并且总结出了一些规律
。根据这些规律
，找出了一种特别适合32位机器数的确定性素数判定法，并且进行了多种优化 ，给出了时间复杂度分析。

第四章：算法的C++语言实现和解释说明 。

第五章：算法的可推广性分析和未来发展展望
。

目录

第一章 素数判定法现状... 1

第二章 2-伪素数表的生成... 2

第三章 寻找2-伪素数的最小可判定底数... 3

第四章 算法实现和解释... 5

第五章 算法可推广性分析... 8

参考文献... 9

词汇表

素数判定法：判定一个自然数是否素数的方法。

确定性素数判定法：一个素数判定法判定某个自然数为素数的充要条件是该自然数确实是素数
，该判定法就是确定性素数判定法 。即该判定法不存在误判的可能性
。

32位机器数：在计算机上用32个二进制位表示的无符号整数。

64位机器数：在计算机上用64个二进制位表示的无符号整数 。

第一章 素数判定法现状

现在，确定性素数判定法已经有很多种 ，常用的有试除法 、威廉斯方法
、艾德利曼和鲁梅利法
。它们的适用范围各不相同
，威廉斯方法比较适合10^20到10^50之间的数，艾德利曼和鲁梅利法适合大于10^50的数 ，对于32位机器数，由于都小于10^10
，所以一般都用试除法来判定。

也许有人会问：“你为什么没有提马宁德拉.阿格拉瓦法呢？不是有人说它是目前最快的素数判定法吗？ ” 其实这是一个很大的误解，阿格拉瓦法虽然是log(n)的多项式级算法 ，但目前只有理论上的意义
，根本无法实用，因为它的时间复杂度是O(log(n)^12) ，这个多项式的次数太高了 。就拿最慢的试除法跟它来比吧
，试除法的时间复杂度为O(n^(1/2)*log(n)^2)，当n = 16时 ，log(n)^12 = 16777216
，而n^(1/2)*log(n)^2 = 64，你看相差有多么大！如果要让两者速度相当 ，即log(n)^12 = n^(1/2)*log(n)^2
，得出n = 10^43.1214，此时需要进行的运算次数为log(n)^12 = 10^25.873（注意：本文中log（）函数缺省以2为底） ，这样的运算次数在一台主频3GHz的计算机上运行也要10^8.89707年才能运行完，看来我们这辈子是别指望看到阿格拉瓦法比试除法快的这一天啦！

除了这些确定性素数判定法外
，还有基于概率的非确定性素数判定法，最常用的就是米勒-拉宾法
。

对于32位机器数（四则运算均为常数时间完成） ，试除法的时间复杂度是O(n^(1/2))
，而米勒-拉宾法的时间复杂度只有O(log(n))。所以后者要比前者快得多，但是由于米勒-拉宾法的非确定性 ，往往我们在需要确定解时仍然要依靠速度较慢的试除法 。那是否可以通过扩展米勒-拉宾法
，来找到一种更快的确定性素数判定法呢？结论是肯定的，本文就带你一起寻找这样一种方法。

第二章 2-伪素数表的生成

既然要扩展米勒-拉宾法 ，那首先我们应该知道为什么米勒-拉宾法是个非确定性素数判定法？答案很简单
，由于伪素数的存在
。由于米勒-拉宾法使用费尔马小定理的逆命题进行判断，而该逆命题对极少数合数并不成立 ，从而产生误判
，这些使费尔马小定理的逆命题不成立的合数就是伪素数。为了研究伪素数，我们首先需要生成伪素数表 ，原理很简单，就是先用筛法得出一定范围内的所有素数
，然后逐一判定该范围内所有合数是否使以2为底数的费尔马小定理的逆命题不成立，从而得出该范围内的2-伪素数表 。我的程序运行了100分钟 ，得出了32位机器数范围内的2-伪素数表
，如下：

341

561

645

1105

1387

1729

1905

2047

2465

2701

...

...

...

4286813749

4288664869

4289470021

4289641621

4289884201

4289906089

4293088801

4293329041

4294868509

4294901761

（共10403个，由于篇幅所限 ，中间部分省略
。）

第三章 寻找2-伪素数的最小可判定底数

对于2-伪素数表的每一个伪素数
，寻找最小的可以判定它们是合数的底数，我把这个底数称之为最小可判定底数。特别地 ，对于绝对伪素数
，它的最小质因子即是它的最小可判定底数 。由于已经证明了绝对伪素数至少有三个质因子，所以这个最小质因子一定不大于n^(1/3)
。下面就是我找到的最小可判定底数列表：

341 3

561 3

645 3

1105 5

1387 3

1729 7

1905 3

2047 3

2465 5

2701 5

...

...

...

4286813749 3

4288664869 3

4289470021 5

4289641621 3

4289884201 3

4289906089 3

4293088801 3

4293329041 3

4294868509 7

4294901761 3

通过统计这个列表 ，我发现了一个规律
，那就是所有的最小可判定底数都不大于n^(1/3)，由前述可知 ，对于绝对伪素数，这个结论显然成立。而对于非绝对伪素数
，虽然直观上觉得它应该比绝对伪素数好判定出来，但是我无法证明出它的最小可判定底数都不大于n^(1/3) 。不过没关系 ，这个问题就作为一个猜想留给数学家来解决吧
，更重要的是我已经通过实验证明了在32位机器数范围内这个结论成立
。

我们还有没有更好的方法来进一步减小最小可判定底数的范围呢？有的！我们可以在计算平方数时进行二次检测，下面是进行了二次检测后重新计算的最小可判定底数列表：

341 2

561 2

645 2

1105 2

1387 2

1729 2

1905 2

2047 3

2465 2

2701 2

...

...

...

4286813749 2

4288664869 2

4289470021 2

4289641621 2

4289884201 2

4289906089 2

4293088801 2

4293329041 2

4294868509 2

4294901761 3

很显然 ，二次检测是有效果的
，经过统计，我发现了新的规律 ，那就是经过二次检测后所有的最小可判定底数都不大于n^(1/6)
，真的是开了一个平方呀，哈哈！这个结论的数学证明仍然作为一个猜想留给数学家们吧。我把这两个猜想叫做费尔马小定理可判定上界猜想 。而我已经完成了对32位机器数范围内的证明
。

通过上面总结的规律 ，我们已经可以设计出一个对32位机器数进行素数判定的 O(n^(1/6)*log(n)) 的确定性方法。但是这还不够
，我们还可以优化，因为此时的最小可判定底数列表去重后只剩下了5个数（都是素数）：{2,3,5,7,11} 。天哪 ，就是前5个素数，这也太容易记忆了吧。

不过在实现算法时
，需要注意这些结论都是在2-伪素数表基础上得来的，也就是说不管如何对2的判定步骤必不可少 ，即使当2>n^(1/6)时
。

还有一些优化可以使用
，经过实验，当n>=7^6时 ，可以不进行n^(1/6)上界限制
，而固定地用{2,5,7,11}去判定，也是100%正确的。这样就可以把判定次数降为4次以下 ，而每次判定只需要进行4log(n)次乘除法（把取余运算也看作除法）
，所以总的计算次数不会超过16log(n) 。经过实验，最大的计算次数在n=4294967291时出现 ，为496次
。

第四章 算法实现和解释

算法实现如下：（使用C++语言）

#include <iostream>

#include <math.h>

using namespace std;

//定义跨平台的64位机器数类型

#ifndef _WIN32

typedef unsigned long long longlong_t;

#else

typedef unsigned __int64 longlong_t;

#endif

//使用费尔马小定理和二次检测针对一个底数进行判定

bool IsLikePrime(longlong_t n, longlong_t base)

{

longlong_t power = n-1;

longlong_t result = 1;

longlong_t x = result;

longlong_t bits = 0;

longlong_t power1 = power;

//统计二进制位数

while (power1 > 0)

{

power1 >>= 1;

bits++;

}

//从高位到低位依次处理power的二进制位

while(bits > 0)

{

bits--;

result = (x*x)%n;

//二次检测

if (result == 1 && x != 1 && x != n-1)

{

return false;

}

if ((power&((longlong_t)1<<bits)) != 0)

{

result = (result*base)%n;

}

x = result;

}

//费尔马小定理逆命题判定

return result == 1;

}

//前5个素数

const int primes[]={2,3,5,7,11};

//前5个素数的6次方
，由后面的init对象初始化

int primes_six[sizeof(primes)/sizeof(primes[0])];

//静态初始化类

class CInit

{

public:

CInit()

{

int num = sizeof(primes)/sizeof(primes[0]);

for (int i = 0; i < num; i++)

{

primes_six[i] = primes[i]*primes[i]*primes[i];

primes_six[i] *= primes_six[i];

}

}

}init;

//王浩素数判定函数

bool JudgePrime(longlong_t n)

{

if (n < 2)

return false;

if (n == 2)

return true;

int num = sizeof(primes)/sizeof(int);

bool bIsLarge = (n >= primes_six[3]);

for (int i = 0; i < num; i++)

{

if (bIsLarge)

{

//当n >= 7^6时，不进行上界判断 ，固定地用{2,5,7,11}做判定。

if (primes[i] == 3)

continue;

}

else

{

//当n < 7^6时，进行上界判断
，但是2例外 。

if (primes[i] != 2 && n < primes_six[i])

break;

}

//做一次子判定

if (!IsLikePrime(n, primes[i]))

return false;

}

//所有子判定通过，则n必为素数！

return true;

}

//主程序

int main()

{

longlong_t n;

//对标准输入的每一个数进行素数判定

while (cin >> n)

{

if (JudgePrime(n))

{

//如果是素数 ，则输出到标准输出
。

cout << n << endl;

}

//如果是合数
，不输出。

}

return 0;

}

程序中已经加了足够的注释，应该不难理解 。

需要说明的一点是 ，虽然我在输入时使用了longlong_t
，那是为了类型一致性，有效的输入范围仍然是0 ~ 2^32-1 
。

第五章 算法可推广性分析

如果前述的费尔马小定理可判定上界猜想可以被证明 ，那么该算法可以被推广到任意位数的n
，此时的时间复杂度为O(n^(1/6)*log(n)^3)。这样我们就可以完成米勒-拉宾非确定性素数判定法向确定性素数判定法的转化，这对于数论理论是一个补充 ，对于实践中使用米勒-拉宾素数判定法具有指导意义 。

本文所做的研究只是向米勒-拉宾非确定性素数判定法的确定化方向迈出了一小步
，我相信，在不久的将来 ，米勒-拉宾非确定性素数判定法的确定化方向会有更大进展，从而对数论理论和实践产生深远影响
。

参考文献

《计算机算法设计与分析（第2版）》
，王晓东编著，电子工业出版社 ，2004年7月。

费马小定理

质数是指在大于1的自然数中
，除了1和它本身以外不再有其他因数的自然数 。

中文名

质数

外文名

prime number

别名

素数

讨论范围

非0自然数

定义

只有1和它本身两个因数的自然数

快速

导航

性质

分布规律

数目计算

性质

公式

应用

编程

猜想

孪生素数无限多的证明

难题

定义

质数又称素数。一个大于1的自然数，除了1和它自身外 ，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）
。

性质

质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明 。它使用了证明常用的方法：反证法
。具体证明如下：假设质数只有有限的n个
，从小到大依次排列为p1，p2 ，……
，pn，设N=p1×p2×……×pn ，那么
， 是素数或者不是素数。

如果 为素数，则 要大于p1 ，p2，……
，pn，所以它不在那些假设的素数集合中 。

1、如果 为合数 ，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1
，所以不可能被p1，p2 ，……
，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中
。因此无论该数是素数还是合数 ，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立 。也就是说
，素数有无穷多个
。

2 、其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁 ，哈里·弗斯滕伯格则用拓扑学加以证明 。

分布规律

以36N（N+1）为单位
，随着N的增大，素数的个数以波浪形式渐渐增多
。

孪生质数也有相同的分布规律。

费马小定理介绍如下：

费马小定理(Fermat's little theorem)是数论中的一个重要定理 ，在1636年提出 。如果p是一个质数，而整数a不是p的倍数
，则有a^（p-1）≡1（mod p）。

发展简史：

皮耶·德·费马于1636年发现了这个定理
。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求，但是这个要求实际上是不必要的 。

1736年 ，欧拉出版了一本名为“一些与素数有关的定理的证明
”（拉丁文：Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio）的论文中第一次提出证明
，但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明
。

有些学家独立制作相关的假说（有时也被错误地称为中国的假说），当成立时 ，p是素数。这是费马小定理的一个特殊情况 。然而
，这一假说的前设是错的：例如，341 ，而341=11×31是一个伪素数
。所有的伪素数都是此假说的反例。

如上所述
，中国猜测仅有一半是正确的 。符合中国猜测但不是素数的数被称为伪素数
。更极端的反例是卡迈克尔数：假设a与561互质，则a560被561除都余1。这样的数被称为卡迈克尔数 ，561是最小的卡迈克尔数 。

Korselt在1899年就给出了卡迈克尔数的等价定义
，但直到1910年才由卡迈克尔（Robert Daniel Carmichael）发现第一个卡迈克尔数：561
。1994年William Alford
、Andrew Granville及Carl Pomerance证明了卡迈克尔数有无穷多个。

关于“如何快速检查一个素数的素性（算法）”这个话题的介绍，今天小编就给大家分享完了 ，如果对你有所帮助请保持对本站的关注！