数学实验之五 ---素数中国科学技术大学数学系陈发来
12 1 3 4 6 6 9 1 7?
实验内容
素数的个数
素数表的构造
素数的判别
最大的素数
求解素数的公式
素数的分布
1、素数的个数
算术基本定理：任何整数都可以分解为
设 为所有的素数。考察
nppp,,,21?
121 npppN?
kdkdd pppn?21 21?
如果 N为合数，则 N必以某些 为因子。
这是不可能的！
虽然素数有无穷多个，但随着整数范围越来越大，素数似乎越来越稀少。
[1,100]----25
[1000,1100]---16
[100000,100100]---6
[10000000,10000100]---2
ip
2、素数表的构造
Eratosthenes筛法
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25
26 27 28 29 30 31 32 33
经过众多学者的艰辛努力,D.N.Lehmer
于 1914年编织出了 10000000以内的素数表。
试除法假设我们已经找到了前 n个素数 p_1=2,
p_2=3,...,p_n,为了寻找下一个素数我们从 p_n+2开始依次检验每一个整数 N,看
N是否能被某个 p_i,i=1,2,...,n整除,
如果 N能被前面的某个素数整除,则 N为合数,否则 N即为下 一个素数 p_{n+1},
为提高算法的效率，只需用不超过的素数去除 N。
N
3、素数的判别威尔逊判别法
n是素数的充要条件是这里 是指 a-b 被 p整除。
不过该算法的运算量为 O(nlogn^2),计算量太大。
pba m od?
)( mo d01)!1( nn
Fermat判别法如果 p是素数,a与 p互素，那么实际上，大约 2500年前，中国古代数学家就发现了上述结论。他们由此得出：如果,则 n为素数。该判别法的运算量为 O(log^3n).
pa p m o d11
)2( m o d22?n
通过编程计算发现，反过来结论并不成立。例如，
但是 341=11x34为合数！称使得成立的 p为伪素数。
3 4 1m o d12 340?
pp m o d12 1
注意同余的计算：
进一步，伪素数有多少个？
341m o d1)13413(
1024)2(2
34
343410340
答案是无穷多个。实际上，数学家迈罗在 1903年证明,如果 n为伪素数，
那么 2^n-1也是伪素数。
不过，同素数个数相比，伪素数的个数非常少。例如，在 2x10^10之内，
伪素数不到素数的百万分之三。因此，
可以认为 Fermat定理的逆定理几乎成立。
利用伪素数表，可以给出判别素数的新方法：如果 p不整除 2^n-1,则 p为合数；如果
p整除 2^n-1,且在伪素数表中，则 p为合数，
否则,p是素数。
伪素数可以推广到 a-伪素数。令人惊奇的是，存在这样的数 p,它对任何 a都是伪素数。例如,561=3x11x17就是这样一个伪素数，即
)5 6 1( m o d1560?a
这样的数称为绝对伪素数，也称迈克尔数。如果迈克尔数只有有限个，则对
n>M,素数的判别变得比较容易。但迈克尔可能有无限个，这使得直接用 Fermat
定理判别素性变得困难。
n-1检验法假设 n-1=FR,F>R,gcd(F,R)=1,如果对 F的每一个素因子 q都存在一个整数 a>1满足则 n是素数。
1),1g c d (),( m o d1 /)1(1 nana qnn
基于广义黎曼猜想的判别
1976年，缪内发现了素性判别与黎曼猜想之间的一个深刻联系。他的结论是：
在广义黎曼假设下，存在常数 C,对任何整数 n,若 n为合数，则存在 a<C(logn)^2
使得
)( m od2
1
n
n
a
a
n
维路于 1978年指出，上述常数 C=70.
由此可以设计如下多项式算法：
对任意 n,依次对 a=1,2,…,70(logn)^2 检验上式是否成立。若对每一个 a都不成立，
则 n为素数。否则,n 为合数。
上述算法的运算量为 O(logn)^5.
１９８０年数学家 Adleman,Rumely,
Cohen和 Lenstra研究出一种非常复杂、具有高度技巧的素数判别方法，检验一个
２０位数的素性只需１０秒，对一个５
０位数，只要１５秒，而一个１００位数只用４０秒。如果用试除法，判别一个５０位数的素性要一百亿年！
概率判别法
Lehmann,给定 p,判断它是否为素数：
（１）选择一个小于 p的随机数 a;
（２）如果 a与 p不互素，则 p为合数；
（３）计算 J=a^(p-1) mod p；
（４）如果 J<>1或 -1,那么 p为合数；
（５）如果 J=1或 -1,那么 p不是素数的可能性最多是 50%.
重复 k次实验，那么 p不是素数的可能性不超过 1/2^k.
利用上述算法可以产生大的随机素数：
（ 1）产生随机数 p;
（ 2）确保 p不被较小的素数整除。
（ 3）产生随机数 a,利用上述算法检测 p
的素性。直到经过多次测试为止。
素性判别的多项式算法给定一个 n位的整数，假设某一算法能在
f(n)步内判断出该整数是否素数。如果 f(n)
是一个多项式的话，则称该算法具有多项式复杂性，称该问题是“多项式可解的”。如果不存在一个算法其具有多项式的计算复杂性，则称该问题属于 NP问题。
2002年 8月，印度理工大学计算机系的三位学者提出了整数素性判别的多项式算法！即素性判别问题是 P类问题。他们指出算法复杂性一般为 O(n^12)。如果提供某些启发线索的话，算法的复杂性可以降到 O(n^6)甚至 O(n^3).
一个令人关注的问题是，该算法是否会威胁现有的 RSA公钥密码体系的安全？
4、最大的素数
Mersenne数形如 的数称为 Mersenne数。
利用 Mersenne数可以构造出非常大的素数。
很显然，如果 n是合数，则 M_n也为合数，
但 n为素数时,M_n不一定为素数。例如，
M_11=2047=23x89是合数。
12 nnM
1644年 Mersenne宣称，对 n=2,3,5,13,
17,19,31,67,127,257,M_n都是素数，
而且对其它 n<257,M_n都是合数。
然而，后人证明 M_67,M_257不是素数，
而 M_61,M_89,M_107都是素数。
877 6 1 8 3 8 2 5 7 21 9 3 7 0 7 7 2 112 67
截止 2002年 2月,数学家仅发现了 39个
Mersenne素数,
n 位数 时间
86143 25962 1982
110503 33265 1983
132049 39751 1983
216091 65050 1985
n 位数 时间
756839 227832 1992
859433 258716 1994
1257787 378632 1996
1398269 420921 1996
2976221 895932 1997
3021377 909526 1998
6972593 2098960 1999
13466917 4053945 2002
Mersenne数素性的判别方法定义数列 u_0=4,u_{k+1}= u_k^2-2
(mod M_n),k=1,2,...,n,如果 u_{n-1}
=0(mod M_n),则 M_n为素数,否则,M_n
为合数,
关于 Mersenne素数的进一步问题,
（ 1） Mersenne素数是否有无穷多个？
（ 2）对什么样的 n,M_n是素数？是否存在求 n的公式？至少使 M_n为素数的 n应该具有什么性质？
（ 3）如果 M_n是合数，如果分解 M_n？
5、生成素数的公式
是否存在单变量整系数的多项式,它只生成素数并且生成所有的素数?
更一般地,是否存在一个生成素数的多变量函数公式?
如果这样的公式不存在,能否找到一个虽不能给出全部但能给出无穷多个素数
(且只给出素数 )的公式?
Fermat数形如 F_n=2^{2^n}+1的数被称为 Fermat数。
Fermat宣称，对所有的整数 n,F_n永远是素数。 的确,F_0=3,F_1=5,F_2=17,
F_3=257,F_4=65537都是素数。
但 Euler指出
F_5=4294967297=641?6700417 是合数。
后人验证出 F_n (n<=19)均为合数。因此有人猜测 F_n(n>4)都是合数。
Fermat数 F_n与正多边形做图有紧密的联系,古代数学家认为，当 n为大于 6的素数时，正 n边形不能用圆规与直尺做出。
但是，在 1796年,19岁的德国数学家
Gauss找到了用直尺与圆规做正 17边形的方法。这一辉煌的成果轰动了整个数学界。
五年后他进一步证明了,一个正 n边行可用直尺与园规作图的充要条件是,n=2^k
或者 n=2^k p_1 p_2..,p_r,其中
p_1,p_2,...,p_r为不同的 Fermat数,特别地,正 17边形可以用直尺与园规做出,
此后，数学家梨西罗与盖尔美斯给出了正 257边形与正 65537边形的做图法！
关于 Fermat数主要研究的问题是：
（ 1）如何分解 Fermat数？
（ 2） Fermat素数是否只有有限个？
（ 3） Fermat合数是否有无穷多个？
（ 4） Fermat数有没有平方因子？
Euler素数生成公式
Euler曾研究过公式,f(n)=n^2+n+41,
可以验证，当 n=0,1,…,39时,f(n)都是素数，但 f(40)是合数。有趣的是，公式能给出相当多的素数。
公式 n^2+n+41有一个非常奇特的性质,
为揭示这一特性,我们考察它的二次求根公式的判别式 d=1^2-4?1?41 =-163.
163有什么特别的地方？有 ! 请看
00 0 0 0 0 0 0 0 0 04 0 7 6 8 7 4 4,02 6 2 5 3 7 4 1 2 6163e
作为 Hilbert第十问题的一个推论,马蒂雅舍维奇证明了,存在一个多元多项式
P(x_1,x_2,...,x_n),其正值构成的集合恰好是素数的全体,遗憾的是,他并没有给出怎样具体地构造这样的多项式,
后经众多数学家的努力,终于在 1977年构造出了一个具有 26个变量 25次的素数生成多项式 !
6、素数的分布
素数沿 数轴的分布
（ 1）随着整数范围的扩大，素数是不是越来越稀疏？稀疏的程度是否单调地增加？
（ 2）相邻素数之间的间隔值有哪些? 它们各重复多少次? 哪些间隔值的重复次数多? 最大间隔值是多少? 随整数范围扩大,最大间隔值是否也随之增大?
（ 3）间隔差为 2的素数对是否有无穷多个? 更一般地,间隔差为某一个固定偶数的素数对是否有无穷多个? 是否存在相邻的素数,其间隔值可以任意大?
用?(n)表示不超过 n的素数的个数,
(m,n)表示区间 [m,n]内素数的个数,
固定 d,绘制点列（ i,?(3^i,3^i+d)),
i=1,2,…,N.
10 20 30 40 50
5
10
15
20
25
100?d
10 20 30 40 50
25
50
75
100
125
150
1000?d
将素数从小到大顺序排列 p_1=2,
p_2=3,...,用 d_n=p_{n+1}-p_n表示相邻素数间的间隔,计算 d_1,d_2,...,d_N(如
N=1000,10000),然后将点 (p_n,d_n)标在平面坐标系中,
500 1000 1500 2000
5
10
15
20
25
500 1000 1500 2000
5
10
15
20
25
5 10 15 20 25 30 35
50
100
150
200
250
1 0 0 0?N
5 10 15 20 25 30 35
500
1000
1500
2000
1 0 0 0 0?N
素数的个数在二维坐标平面上标出点列 (n,?(n)),
n=1,2,...,N(取不同的 N,如 1000,
10000等 ),也可以用折线将点列连接起来,观察?(n)趋于无穷的趋势,
2000 4000 6000 8000 10000
200
400
600
800
1000
1200
2000 4000 6000 8000 10000
500
1000
1500
2000
2000 4000 6000 8000 10000
5
6
7
8
)(/ nn?
)l og ()(/ nnn?
由此猜测关于素数个数的近似公式首先是 Gauss 于
1792年给出的,但他当时没能给出证明,
勒让德也曾给出
)lo g (/)( nnn
)0 8 3 6 6.1/ ( l n)( xxx?
后来,Gauss还给出了近似公式：
最接近的公式是由 Rieman 猜想导出的：
这里
x x d xx 2 l o g/1)(?
1
!/)( l o g)1(/11)(
k
k knkkxR?
.,,3/12/11)( kkk?
1852年，俄国数学家切比雪夫证明了这里 a=0.92…,b=1.055,1892 年，英国数学家希尔维斯特改进切比雪夫的结果，得到 a=0.956…,b=1.044.
1896,Hadamard与 Poussin利用复变函数的理论加以证明,
xxbxxxa ln/)(ln/
素数定理的初等证明于 1949年著名数学家
Erdos获得。
Riemann猜想与素数的分布有紧密的联系。
不过 Riemann猜想至今仍未被证明,它无疑是数学上最著名的难题之一。
7,进一步的思考问题
Goldbach 猜想
Goldbach于 1742年给大数学家 Euler的信中提出了两个猜想,即每个不小于 6的偶数都可以表为两个奇素数之和 ; 每个不小于 9的奇数可以表为三个奇素数之和,
Euler在随后的复信中写道,任何不小于 6
的偶数都是两个奇素数之和,虽然我不能证明它,但我确信无疑这是完全正确的定理,这就是著名的 Goldbach猜想的由来,
两百多年来,无数数学家花费了大量的心血都未能解决这一问题,目前，有人验证到 10^14,命题仍然正确。
1900年,Hilbert在巴黎世界数学家大会上提出 23个问题供 20世纪数学家研究。
其中第 8问题中将 Goldbach猜想作为最重要的问题之一提出。
1912年，在第五届世界数学家大会上，
数学家兰道指出，即使证明下面较弱的命题，也是现代数学所力不能及的。
任何整数都可以表示为不超过 C个素数之和。
1921年英国数学家 Hardy在哥本哈根召开的数学会议上说,Goldbach猜想的困难程度可以跟任何没解决的数学问题想比
1930年，苏联数学家什尼尔列曼证明，
任意整数都可以表为不超过 k个素数之和,
且 k<800000.
1935年,k<=2208 （苏联，罗曼诺夫）
1936年,k<=71 (德国，海尔布伦）
1937年,k<=67（意大利，里奇）
1950年,k<=20（美国，夏彼得）
1956年,k<=18（中国，尹文霖）
1976年,k<=6 (旺格汉）
1937，苏联人维诺格拉夫证明，充分大的奇数可以表为三个素数的和。
另一条路线：将大偶数表示为 s个素数之积加上 t个素数之和。记为,s+t”.
年份 证明者 国家 结果
1920 布龙 挪威 9+9
1924 拉特马赫 德国 7+7
1938 布赫夕太勃 苏联 5+5; 4+4
1948 兰恩尼 匈牙利 1+C
1956 王元 中国 3+4； 3+3
1962 潘乘洞 中国 1+5
1962 王元 中国 1+4
1965 布赫夕太勃 苏联 1+3
1966 陈景润 中国 1+2
Fermat大定理设 n是大于 2的整数，则方程无不存在非平凡的整数解。
nnn zyx
Fermat 本人证明了 n=4的情形。
1753年,Euler证明了 n=3.
1825年,Dirchlet与 Legendre证明了 n=5.
1832年，法国女数学家索非热尔曼证明：
如果 n和 2n+1为素数,Fermat大定理成立。
1839年，拉梅证明了 n=7.
1847年，德国数学家 Kummer证明了对
n<100(除出 37,59,67),Fermat定理成立。
1983年，德国数学家法尔廷斯证明了：
对每个 n>2,方程只有有限个解。
1993年,Princeton大学的教授威尔斯宣布证明了 Fermat定理。但数学家发现了证明中的一个漏洞。经过九个月的努力
威尔斯修正了这一错误，这标志着
Fermat大定理被彻底征服。
威尔斯的证明完全采用了全新的路线，
用到了现代数学的许多分支：椭圆曲线论，模形式论，伽罗华表示论等。
所谓椭圆曲线是如下形式的曲线：
dcxbxaxy 232
椭圆曲线与模形式之间有紧密的联系。
50年代，日本数学家谷山丰和志村五郎猜测：有理数域上的每条椭圆曲线都存在模形式。被乘为,谷山 -志村,猜想。
60年代,有人将 Femat 方程与椭圆曲线联系起来。 1984年，佛赖证明，如果
Fermat大定理不成，则由 Fermat方程确定的椭圆曲线不可能是模形式，这与 谷山 -
志村猜想矛盾！因此，要证明 Fermat大定理，只需证明谷山 -志村猜想。威尔斯所做的正是证明了该猜想。
大整数的素因子分解正如判断一个大数的素性一样,将一个大整数分解为素因子的乘积是一件相当艰难的事情,迄今尚无一种通用有效的方法 (试除法显然是不用考虑的 ),目前，
最有效的素因子分解方法的运算量大约为 O(exp(cL^(1/3)log(L)^(2/3))),其中 L为要分解的整数 N的位数 。
利用现有大型计算机的能力,能够分解的最大整数不能超过 100位,例如,至今尚无人能分解 Fermat数 F_9,读者能否给出 F_6的分解?
1994年，美国数学家 Peter Shor做出了一项惊人的工作。他指出，如果使用量子计算机，则因子分解算法的运算量为
O(L^2log(L)loglog(L)).
完全数所谓完全数是指它的所有因子 (除去它本身 )
之和等于该完全数,例如,6是一个完全数,
因为 1+2+3=6,下一个完全数是 28,请读者找出 10000以内的所有完全数,并对它做素因子分解,你能据此猜测完全数的通式吗?
完全数与 Mersenne素数有何联系? 你能由此找到更多的完全数吗? 是否存在奇完全数?
完全数是否有无穷多个?
除 6以外,完全数都有一个奇妙的特性,
就是每个完全数可以表为几个连续的奇数之立方和,如 28=1^3+2^3,请你对你找出的完全数验证此特性,
完全数的另一个特性是它的因子的倒数和为 1。如 1/2+1/3+1/6=1。
把完全数（除 6）各位数相加得另一数，
这样一直做下去，最后得 1。
完全数二进制形式为,11…100…0
孪生素数间隔为 2的相邻素数，如 3与 5,5与 7。关于孪生素数的猜想是：孪生素数有无穷多个。
1919年，挪威数学家布隆考虑孪生素数的倒数和：
)7/15/1()5/13/1(B
如果上述数列发散，则孪生素数有无穷多个。遗憾的是，上述数列收敛，其和为 B=1.90216054….
用 p(x)表示不超过 x的孪生素数的个数。
英国数学家 Hardy与 Littlewood猜测
其中
2)/ ( l n2)( xcxxp?
)6/11)(4/11)(2/11( 222c
迄今为止，孪生素数猜想还没有证明。
目前最好的结果是我国数学家陈景润于
1966年获得：存在无穷多个素数 p,使
p+2是不超过两个素数的乘积。截止
1999年发现的最大孪生素数是
1236 17 00 055 3 9 0 2 0
青一色数的素性由 n个 1组成的数 11...1叫做青一色数,当
n为何值时,青一色数是素数? 如果青一色数是合数,如何将它做素因子分解?
很显然，如果 n为合数，则清一色数为合数。目前只得到 n=2,19,23,317,1031时，
清一色数为素数。
Bertrand猜测当 n>3时,n与 2n-2之间至少存在一个素数,1852年,俄国数学家切比雪夫证明该猜想。
进一步，对怎样大的 d>0,n与 (1+d)n之间必然有素数呢？ 1893年法国数学家凯恩证明，对任意 d>0,只要 n足够大，上述结论成立。
继 Bertrand猜想之后,1882年奥波曼提出新的猜想：在 n^2和 n(n+1)之间必有素数。
但现在还没有获得证明。目前的最好结果是,n^2与 n^2+n^k之间有素数。这里
k>12/11.
相关的 Mathematica函数
FactorInteger[n]
Mod[m,n]
PrimeQ[n]
Prime[n]
ListPlot[{{x1,y1},{x2,y2},…{x_n,y_n
}}]
PlotJoined->True
Table
Thank you very much
for your presence
12 1 3 4 6 6 9 1 7?
实验内容
素数的个数
素数表的构造
素数的判别
最大的素数
求解素数的公式
素数的分布
1、素数的个数
算术基本定理：任何整数都可以分解为
设 为所有的素数。考察
nppp,,,21?
121 npppN?
kdkdd pppn?21 21?
如果 N为合数，则 N必以某些 为因子。
这是不可能的！
虽然素数有无穷多个，但随着整数范围越来越大，素数似乎越来越稀少。
[1,100]----25
[1000,1100]---16
[100000,100100]---6
[10000000,10000100]---2
ip
2、素数表的构造
Eratosthenes筛法
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25
26 27 28 29 30 31 32 33
经过众多学者的艰辛努力,D.N.Lehmer
于 1914年编织出了 10000000以内的素数表。
试除法假设我们已经找到了前 n个素数 p_1=2,
p_2=3,...,p_n,为了寻找下一个素数我们从 p_n+2开始依次检验每一个整数 N,看
N是否能被某个 p_i,i=1,2,...,n整除,
如果 N能被前面的某个素数整除,则 N为合数,否则 N即为下 一个素数 p_{n+1},
为提高算法的效率，只需用不超过的素数去除 N。
N
3、素数的判别威尔逊判别法
n是素数的充要条件是这里 是指 a-b 被 p整除。
不过该算法的运算量为 O(nlogn^2),计算量太大。
pba m od?
)( mo d01)!1( nn
Fermat判别法如果 p是素数,a与 p互素，那么实际上，大约 2500年前，中国古代数学家就发现了上述结论。他们由此得出：如果,则 n为素数。该判别法的运算量为 O(log^3n).
pa p m o d11
)2( m o d22?n
通过编程计算发现，反过来结论并不成立。例如，
但是 341=11x34为合数！称使得成立的 p为伪素数。
3 4 1m o d12 340?
pp m o d12 1
注意同余的计算：
进一步，伪素数有多少个？
341m o d1)13413(
1024)2(2
34
343410340
答案是无穷多个。实际上，数学家迈罗在 1903年证明,如果 n为伪素数，
那么 2^n-1也是伪素数。
不过，同素数个数相比，伪素数的个数非常少。例如，在 2x10^10之内，
伪素数不到素数的百万分之三。因此，
可以认为 Fermat定理的逆定理几乎成立。
利用伪素数表，可以给出判别素数的新方法：如果 p不整除 2^n-1,则 p为合数；如果
p整除 2^n-1,且在伪素数表中，则 p为合数，
否则,p是素数。
伪素数可以推广到 a-伪素数。令人惊奇的是，存在这样的数 p,它对任何 a都是伪素数。例如,561=3x11x17就是这样一个伪素数，即
)5 6 1( m o d1560?a
这样的数称为绝对伪素数，也称迈克尔数。如果迈克尔数只有有限个，则对
n>M,素数的判别变得比较容易。但迈克尔可能有无限个，这使得直接用 Fermat
定理判别素性变得困难。
n-1检验法假设 n-1=FR,F>R,gcd(F,R)=1,如果对 F的每一个素因子 q都存在一个整数 a>1满足则 n是素数。
1),1g c d (),( m o d1 /)1(1 nana qnn
基于广义黎曼猜想的判别
1976年，缪内发现了素性判别与黎曼猜想之间的一个深刻联系。他的结论是：
在广义黎曼假设下，存在常数 C,对任何整数 n,若 n为合数，则存在 a<C(logn)^2
使得
)( m od2
1
n
n
a
a
n
维路于 1978年指出，上述常数 C=70.
由此可以设计如下多项式算法：
对任意 n,依次对 a=1,2,…,70(logn)^2 检验上式是否成立。若对每一个 a都不成立，
则 n为素数。否则,n 为合数。
上述算法的运算量为 O(logn)^5.
１９８０年数学家 Adleman,Rumely,
Cohen和 Lenstra研究出一种非常复杂、具有高度技巧的素数判别方法，检验一个
２０位数的素性只需１０秒，对一个５
０位数，只要１５秒，而一个１００位数只用４０秒。如果用试除法，判别一个５０位数的素性要一百亿年！
概率判别法
Lehmann,给定 p,判断它是否为素数：
（１）选择一个小于 p的随机数 a;
（２）如果 a与 p不互素，则 p为合数；
（３）计算 J=a^(p-1) mod p；
（４）如果 J<>1或 -1,那么 p为合数；
（５）如果 J=1或 -1,那么 p不是素数的可能性最多是 50%.
重复 k次实验，那么 p不是素数的可能性不超过 1/2^k.
利用上述算法可以产生大的随机素数：
（ 1）产生随机数 p;
（ 2）确保 p不被较小的素数整除。
（ 3）产生随机数 a,利用上述算法检测 p
的素性。直到经过多次测试为止。
素性判别的多项式算法给定一个 n位的整数，假设某一算法能在
f(n)步内判断出该整数是否素数。如果 f(n)
是一个多项式的话，则称该算法具有多项式复杂性，称该问题是“多项式可解的”。如果不存在一个算法其具有多项式的计算复杂性，则称该问题属于 NP问题。
2002年 8月，印度理工大学计算机系的三位学者提出了整数素性判别的多项式算法！即素性判别问题是 P类问题。他们指出算法复杂性一般为 O(n^12)。如果提供某些启发线索的话，算法的复杂性可以降到 O(n^6)甚至 O(n^3).
一个令人关注的问题是，该算法是否会威胁现有的 RSA公钥密码体系的安全？
4、最大的素数
Mersenne数形如 的数称为 Mersenne数。
利用 Mersenne数可以构造出非常大的素数。
很显然，如果 n是合数，则 M_n也为合数，
但 n为素数时,M_n不一定为素数。例如，
M_11=2047=23x89是合数。
12 nnM
1644年 Mersenne宣称，对 n=2,3,5,13,
17,19,31,67,127,257,M_n都是素数，
而且对其它 n<257,M_n都是合数。
然而，后人证明 M_67,M_257不是素数，
而 M_61,M_89,M_107都是素数。
877 6 1 8 3 8 2 5 7 21 9 3 7 0 7 7 2 112 67
截止 2002年 2月,数学家仅发现了 39个
Mersenne素数,
n 位数 时间
86143 25962 1982
110503 33265 1983
132049 39751 1983
216091 65050 1985
n 位数 时间
756839 227832 1992
859433 258716 1994
1257787 378632 1996
1398269 420921 1996
2976221 895932 1997
3021377 909526 1998
6972593 2098960 1999
13466917 4053945 2002
Mersenne数素性的判别方法定义数列 u_0=4,u_{k+1}= u_k^2-2
(mod M_n),k=1,2,...,n,如果 u_{n-1}
=0(mod M_n),则 M_n为素数,否则,M_n
为合数,
关于 Mersenne素数的进一步问题,
（ 1） Mersenne素数是否有无穷多个？
（ 2）对什么样的 n,M_n是素数？是否存在求 n的公式？至少使 M_n为素数的 n应该具有什么性质？
（ 3）如果 M_n是合数，如果分解 M_n？
5、生成素数的公式
是否存在单变量整系数的多项式,它只生成素数并且生成所有的素数?
更一般地,是否存在一个生成素数的多变量函数公式?
如果这样的公式不存在,能否找到一个虽不能给出全部但能给出无穷多个素数
(且只给出素数 )的公式?
Fermat数形如 F_n=2^{2^n}+1的数被称为 Fermat数。
Fermat宣称，对所有的整数 n,F_n永远是素数。 的确,F_0=3,F_1=5,F_2=17,
F_3=257,F_4=65537都是素数。
但 Euler指出
F_5=4294967297=641?6700417 是合数。
后人验证出 F_n (n<=19)均为合数。因此有人猜测 F_n(n>4)都是合数。
Fermat数 F_n与正多边形做图有紧密的联系,古代数学家认为，当 n为大于 6的素数时，正 n边形不能用圆规与直尺做出。
但是，在 1796年,19岁的德国数学家
Gauss找到了用直尺与圆规做正 17边形的方法。这一辉煌的成果轰动了整个数学界。
五年后他进一步证明了,一个正 n边行可用直尺与园规作图的充要条件是,n=2^k
或者 n=2^k p_1 p_2..,p_r,其中
p_1,p_2,...,p_r为不同的 Fermat数,特别地,正 17边形可以用直尺与园规做出,
此后，数学家梨西罗与盖尔美斯给出了正 257边形与正 65537边形的做图法！
关于 Fermat数主要研究的问题是：
（ 1）如何分解 Fermat数？
（ 2） Fermat素数是否只有有限个？
（ 3） Fermat合数是否有无穷多个？
（ 4） Fermat数有没有平方因子？
Euler素数生成公式
Euler曾研究过公式,f(n)=n^2+n+41,
可以验证，当 n=0,1,…,39时,f(n)都是素数，但 f(40)是合数。有趣的是，公式能给出相当多的素数。
公式 n^2+n+41有一个非常奇特的性质,
为揭示这一特性,我们考察它的二次求根公式的判别式 d=1^2-4?1?41 =-163.
163有什么特别的地方？有 ! 请看
00 0 0 0 0 0 0 0 0 04 0 7 6 8 7 4 4,02 6 2 5 3 7 4 1 2 6163e
作为 Hilbert第十问题的一个推论,马蒂雅舍维奇证明了,存在一个多元多项式
P(x_1,x_2,...,x_n),其正值构成的集合恰好是素数的全体,遗憾的是,他并没有给出怎样具体地构造这样的多项式,
后经众多数学家的努力,终于在 1977年构造出了一个具有 26个变量 25次的素数生成多项式 !
6、素数的分布
素数沿 数轴的分布
（ 1）随着整数范围的扩大，素数是不是越来越稀疏？稀疏的程度是否单调地增加？
（ 2）相邻素数之间的间隔值有哪些? 它们各重复多少次? 哪些间隔值的重复次数多? 最大间隔值是多少? 随整数范围扩大,最大间隔值是否也随之增大?
（ 3）间隔差为 2的素数对是否有无穷多个? 更一般地,间隔差为某一个固定偶数的素数对是否有无穷多个? 是否存在相邻的素数,其间隔值可以任意大?
用?(n)表示不超过 n的素数的个数,
(m,n)表示区间 [m,n]内素数的个数,
固定 d,绘制点列（ i,?(3^i,3^i+d)),
i=1,2,…,N.
10 20 30 40 50
5
10
15
20
25
100?d
10 20 30 40 50
25
50
75
100
125
150
1000?d
将素数从小到大顺序排列 p_1=2,
p_2=3,...,用 d_n=p_{n+1}-p_n表示相邻素数间的间隔,计算 d_1,d_2,...,d_N(如
N=1000,10000),然后将点 (p_n,d_n)标在平面坐标系中,
500 1000 1500 2000
5
10
15
20
25
500 1000 1500 2000
5
10
15
20
25
5 10 15 20 25 30 35
50
100
150
200
250
1 0 0 0?N
5 10 15 20 25 30 35
500
1000
1500
2000
1 0 0 0 0?N
素数的个数在二维坐标平面上标出点列 (n,?(n)),
n=1,2,...,N(取不同的 N,如 1000,
10000等 ),也可以用折线将点列连接起来,观察?(n)趋于无穷的趋势,
2000 4000 6000 8000 10000
200
400
600
800
1000
1200
2000 4000 6000 8000 10000
500
1000
1500
2000
2000 4000 6000 8000 10000
5
6
7
8
)(/ nn?
)l og ()(/ nnn?
由此猜测关于素数个数的近似公式首先是 Gauss 于
1792年给出的,但他当时没能给出证明,
勒让德也曾给出
)lo g (/)( nnn
)0 8 3 6 6.1/ ( l n)( xxx?
后来,Gauss还给出了近似公式：
最接近的公式是由 Rieman 猜想导出的：
这里
x x d xx 2 l o g/1)(?
1
!/)( l o g)1(/11)(
k
k knkkxR?
.,,3/12/11)( kkk?
1852年，俄国数学家切比雪夫证明了这里 a=0.92…,b=1.055,1892 年，英国数学家希尔维斯特改进切比雪夫的结果，得到 a=0.956…,b=1.044.
1896,Hadamard与 Poussin利用复变函数的理论加以证明,
xxbxxxa ln/)(ln/
素数定理的初等证明于 1949年著名数学家
Erdos获得。
Riemann猜想与素数的分布有紧密的联系。
不过 Riemann猜想至今仍未被证明,它无疑是数学上最著名的难题之一。
7,进一步的思考问题
Goldbach 猜想
Goldbach于 1742年给大数学家 Euler的信中提出了两个猜想,即每个不小于 6的偶数都可以表为两个奇素数之和 ; 每个不小于 9的奇数可以表为三个奇素数之和,
Euler在随后的复信中写道,任何不小于 6
的偶数都是两个奇素数之和,虽然我不能证明它,但我确信无疑这是完全正确的定理,这就是著名的 Goldbach猜想的由来,
两百多年来,无数数学家花费了大量的心血都未能解决这一问题,目前，有人验证到 10^14,命题仍然正确。
1900年,Hilbert在巴黎世界数学家大会上提出 23个问题供 20世纪数学家研究。
其中第 8问题中将 Goldbach猜想作为最重要的问题之一提出。
1912年，在第五届世界数学家大会上，
数学家兰道指出，即使证明下面较弱的命题，也是现代数学所力不能及的。
任何整数都可以表示为不超过 C个素数之和。
1921年英国数学家 Hardy在哥本哈根召开的数学会议上说,Goldbach猜想的困难程度可以跟任何没解决的数学问题想比
1930年，苏联数学家什尼尔列曼证明，
任意整数都可以表为不超过 k个素数之和,
且 k<800000.
1935年,k<=2208 （苏联，罗曼诺夫）
1936年,k<=71 (德国，海尔布伦）
1937年,k<=67（意大利，里奇）
1950年,k<=20（美国，夏彼得）
1956年,k<=18（中国，尹文霖）
1976年,k<=6 (旺格汉）
1937，苏联人维诺格拉夫证明，充分大的奇数可以表为三个素数的和。
另一条路线：将大偶数表示为 s个素数之积加上 t个素数之和。记为,s+t”.
年份 证明者 国家 结果
1920 布龙 挪威 9+9
1924 拉特马赫 德国 7+7
1938 布赫夕太勃 苏联 5+5; 4+4
1948 兰恩尼 匈牙利 1+C
1956 王元 中国 3+4； 3+3
1962 潘乘洞 中国 1+5
1962 王元 中国 1+4
1965 布赫夕太勃 苏联 1+3
1966 陈景润 中国 1+2
Fermat大定理设 n是大于 2的整数，则方程无不存在非平凡的整数解。
nnn zyx
Fermat 本人证明了 n=4的情形。
1753年,Euler证明了 n=3.
1825年,Dirchlet与 Legendre证明了 n=5.
1832年，法国女数学家索非热尔曼证明：
如果 n和 2n+1为素数,Fermat大定理成立。
1839年，拉梅证明了 n=7.
1847年，德国数学家 Kummer证明了对
n<100(除出 37,59,67),Fermat定理成立。
1983年，德国数学家法尔廷斯证明了：
对每个 n>2,方程只有有限个解。
1993年,Princeton大学的教授威尔斯宣布证明了 Fermat定理。但数学家发现了证明中的一个漏洞。经过九个月的努力
威尔斯修正了这一错误，这标志着
Fermat大定理被彻底征服。
威尔斯的证明完全采用了全新的路线，
用到了现代数学的许多分支：椭圆曲线论，模形式论，伽罗华表示论等。
所谓椭圆曲线是如下形式的曲线：
dcxbxaxy 232
椭圆曲线与模形式之间有紧密的联系。
50年代，日本数学家谷山丰和志村五郎猜测：有理数域上的每条椭圆曲线都存在模形式。被乘为,谷山 -志村,猜想。
60年代,有人将 Femat 方程与椭圆曲线联系起来。 1984年，佛赖证明，如果
Fermat大定理不成，则由 Fermat方程确定的椭圆曲线不可能是模形式，这与 谷山 -
志村猜想矛盾！因此，要证明 Fermat大定理，只需证明谷山 -志村猜想。威尔斯所做的正是证明了该猜想。
大整数的素因子分解正如判断一个大数的素性一样,将一个大整数分解为素因子的乘积是一件相当艰难的事情,迄今尚无一种通用有效的方法 (试除法显然是不用考虑的 ),目前，
最有效的素因子分解方法的运算量大约为 O(exp(cL^(1/3)log(L)^(2/3))),其中 L为要分解的整数 N的位数 。
利用现有大型计算机的能力,能够分解的最大整数不能超过 100位,例如,至今尚无人能分解 Fermat数 F_9,读者能否给出 F_6的分解?
1994年，美国数学家 Peter Shor做出了一项惊人的工作。他指出，如果使用量子计算机，则因子分解算法的运算量为
O(L^2log(L)loglog(L)).
完全数所谓完全数是指它的所有因子 (除去它本身 )
之和等于该完全数,例如,6是一个完全数,
因为 1+2+3=6,下一个完全数是 28,请读者找出 10000以内的所有完全数,并对它做素因子分解,你能据此猜测完全数的通式吗?
完全数与 Mersenne素数有何联系? 你能由此找到更多的完全数吗? 是否存在奇完全数?
完全数是否有无穷多个?
除 6以外,完全数都有一个奇妙的特性,
就是每个完全数可以表为几个连续的奇数之立方和,如 28=1^3+2^3,请你对你找出的完全数验证此特性,
完全数的另一个特性是它的因子的倒数和为 1。如 1/2+1/3+1/6=1。
把完全数（除 6）各位数相加得另一数，
这样一直做下去，最后得 1。
完全数二进制形式为,11…100…0
孪生素数间隔为 2的相邻素数，如 3与 5,5与 7。关于孪生素数的猜想是：孪生素数有无穷多个。
1919年，挪威数学家布隆考虑孪生素数的倒数和：
)7/15/1()5/13/1(B
如果上述数列发散，则孪生素数有无穷多个。遗憾的是，上述数列收敛，其和为 B=1.90216054….
用 p(x)表示不超过 x的孪生素数的个数。
英国数学家 Hardy与 Littlewood猜测
其中
2)/ ( l n2)( xcxxp?
)6/11)(4/11)(2/11( 222c
迄今为止，孪生素数猜想还没有证明。
目前最好的结果是我国数学家陈景润于
1966年获得：存在无穷多个素数 p,使
p+2是不超过两个素数的乘积。截止
1999年发现的最大孪生素数是
1236 17 00 055 3 9 0 2 0
青一色数的素性由 n个 1组成的数 11...1叫做青一色数,当
n为何值时,青一色数是素数? 如果青一色数是合数,如何将它做素因子分解?
很显然，如果 n为合数，则清一色数为合数。目前只得到 n=2,19,23,317,1031时，
清一色数为素数。
Bertrand猜测当 n>3时,n与 2n-2之间至少存在一个素数,1852年,俄国数学家切比雪夫证明该猜想。
进一步，对怎样大的 d>0,n与 (1+d)n之间必然有素数呢？ 1893年法国数学家凯恩证明，对任意 d>0,只要 n足够大，上述结论成立。
继 Bertrand猜想之后,1882年奥波曼提出新的猜想：在 n^2和 n(n+1)之间必有素数。
但现在还没有获得证明。目前的最好结果是,n^2与 n^2+n^k之间有素数。这里
k>12/11.
相关的 Mathematica函数
FactorInteger[n]
Mod[m,n]
PrimeQ[n]
Prime[n]
ListPlot[{{x1,y1},{x2,y2},…{x_n,y_n
}}]
PlotJoined->True
Table
Thank you very much
for your presence
