判断100位的整数为素数的算法

判断100位的整数为素数的算法
判断100位的整数为素数的算法

判断100位的整数为素数的算法
Miller-Rabbin素数测试法

除以6余1

与1到根号这个数+1相除，都不能整除就为素数

这个一般是要借助于计算机的，网上有很多这样的程序，如果靠手算的话，确实没有简单的方法。

素数算法
素数判定算法（印度理工学院计算机科学与工程学系的科学家马宁德拉·阿格拉瓦和他的两位在校本科生尼拉叶·卡雅尔和尼汀·萨克斯特纳）
（当且仅当n为素数时，最终输出数才为素数）
Input： integer n>l
1. (n is of the form ab，b>1) output COMPOSITE;
2. r=2;
3. whi...

全部展开

素数算法
素数判定算法（印度理工学院计算机科学与工程学系的科学家马宁德拉·阿格拉瓦和他的两位在校本科生尼拉叶·卡雅尔和尼汀·萨克斯特纳）
（当且仅当n为素数时，最终输出数才为素数）
Input： integer n>l
1. (n is of the form ab，b>1) output COMPOSITE;
2. r=2;
3. while(r
4. if(gcd(n，r)≠1) output COMPOSITE；
5. if(r is prime)
6. let q be the largest prime factor of r-1;
7. if(q ≥) and (n ?1(mod r))
8. break；
9. r←r+1;
10. }
11.for a=1 to logn
12. if((x-a)n?(xn-a)(mod xr1,n)) output COMPOSITE;
13.output PRIME;
判定素数的确定性多项式算法(同上)
有朋友发EMAIL问到这个算法,现在我把算法公布出来.论文可以参考2002年,印度,Agrawal等人论文的"primes is in P".
s1: r=2
s2: 当rs3: 若gcd(n,r)<>1,则判定n为合数;
s4: 若r是素数,q是r-1的最大素数因子,若(q>=4sqrt(r)log(n)^(power(n,r-1/q)<>1 mod r),则转s6,否则转s5;
s5: r=r+1
s6: 对1<=a<=2sqrt(r)log(n),若power(x-a,n)<>(power(n,n)-a)mod(power(x,r)-1,n),则n是合数;
s7: n为素数.


曾经有个古老的传说,网络本来很安全,但是当研究安全的人出现后就不安全了!


Rabin-Miller算法:
数论学家利用费马小定理研究出了多种素数测试方法，目前最快的算法是拉宾米
勒测试算法，（现在不是最快，印度的一名老师和他的两个本科生的算法是最快的：印度理工学院计算机科学与工程学系的科学家马宁德拉·阿格拉瓦和他的两位在校本科生尼拉叶·卡雅尔和尼汀·萨克斯特纳）其过程如下：
（1）计算奇数M，使得N=(2**r)*M+1
（2）选择随机数A（3）对于任意i（4）或者，若A**M MOD N = 1，则N通过随机数A的测试
（5）让A取不同的值对N进行5次测试，若全部通过则判定N为素数
若N 通过一次测试，则N 不是素数的概率为 25%，若N 通过t 次测试，则N 不是
素数的概率为1/4**t。事实上取t 为5 时，N 不是素数的概率为 1/128，N 为素数的
概率已经大于99.99%。
在实际应用中，可首先用300—500个小素数对N 进行测试，以提高拉宾米勒测试
通过的概率，从而提高测试速度。而在生成随机素数时，选取的随机数最好让 r=0，
则可省去步骤（3） 的测试，进一步提高测试速度

#include
#include
#include
bool Witness(int a,int n)
{
int i,d=1,x;
for (i=(int)ceil(log((double)n-1)/log(2.0))-1;i>=0;--i) {
x=d;
d=(d*d)%n;
if ((1==d) && (x!=1) && (x!=n-1)) return 1;
if (((n-1)&(1<0) d=(d*a)%n;
}
return (d!=1);
}
bool Rabin_Miller(int n,int s)
{
int j,a;
for (j=0;j a=rand()*(n-2)/RAND_MAX+1;
if (Witness(a,n)) return false;
}
return true;
}
int main()
{
int i;
for (i=3;;i+=2) if (Rabin_Miller(i,20)) printf("%d\n",i);
/* 这里第二个参数取20，能够保证出错概率小于2^(-20)，也可以改的更大使得出错概率更小。 */
return 0;
}
素数判定新方法的启示
日前，印度的三位计算机专家震惊了数学界，他们不但为古老的素数判定问题找到了答案，而且令人始料未及的是，他们的判定方法出奇地简单，简单到足以让数学家们警觉起来，启发他们重新审视许多复杂问题的解决方法。
作为除了1和自身外没有其他约数的正整数，数千年来素数一直是数论的基本构件。对于如何判定一个数是否为素数，公元前240年，希腊数学家埃拉托色尼给出了一个一直沿用到今天的方法——“筛选法”。该方法有其局限性，即随着数字的增大，筛选所耗用的时间呈指数增长。如果要判定相当大的自然数，哪怕采用最先进的计算机进行运算，计算时间比宇宙年龄都要长。因此，长期以来，数学家们一直致力于寻找的，就是在可以接受的时间内能够完成的判定方法。
在过去的几十年间，由于素数判定问题被引入了密码学领域，这方面的研究工作变得倍受关注。因为当前的因特网加密程序，主要是基于大数的素因子分解相当困难这一假定。虽然目前有一些高速程序可以给出一个大数是素数的概率，但它毕竟没有彻底解决问题。
印度理工学院计算机科学与工程学系的科学家马宁德拉·阿格拉瓦和他的两位在校本科生尼拉叶·卡雅尔和尼汀·萨克斯特纳在这方面取得了成功。
这三个人的成功主要得益于采用了崭新的思路。其他人的着眼点往往是“这个数是否是素数”，他们却另辟蹊径，将问题转化成关于待判定数的一系列小的问题或 “方程”。于是，简单的算法诞生了，只需用13行便可写明。阿格拉瓦解释说：“如果某个数字使所有等式成立，那么它就是素数；否则，便不是。”
卡尔·波默朗斯是美国新泽西州贝尔实验室的素数问题专家，他评论说：“这是一个漂亮的算法，我为之高兴。同时，也很遗憾自己没找到它。他们的方法很简洁，但并不平凡。他们的工作充满智慧。”
英国沃里克大学的数学家和科普作家伊恩·斯图亚特认为，这一理论突破就其本身而言固然重要，但它给人们思路上带来的启发意义更加深远。如果采用它所蕴含的换个角度、化繁为简的思想，对于那些目前处在死胡同中的难题，科学家们也许可以找到解决办法。
因特网安全目前还未因此受到威胁。来自英国一个加密安全公司的本·哈德利说：“相对于原来的概率计算算法，新算法并没有给素因子分解提供好的算法，所以这一新突破对密码安全行业并没有太大的实际影响。”
但是，波默朗斯坚信新算法将使密码学专家担忧。他认为，既然存在简单的素数判定算法，也就很可能存在简单的素因子分解算法，只是我们还没注意到罢了。
这恐怕也正是阿格拉瓦等人研究工作的真正意义所在。两名本科生的毕业项目能产生如此重大的成果，这说明我们很可能忽略掉了更多重大数学问题的简单解答方法。波默朗斯感慨颇深地说：“这是一个提醒，原来我们非常容易忽略掉一些简单的东西。”

收起