而那里本身用了Miller-Rabin素性测试的算法,通常没事时能够记一些素数下来以710官方网站

其二种,Solovay-Strassen 素性测试
1) 对i从1到t 做如下循环:
  1.1) 接纳八个小于n的妄动数b;
  1.2) 计算j≡b^((n-1)/2) mod n;
  1.3) 假设j≠1或-1,则赶回n不是素数;
  1.4) 计算Jacobi符号J(b,n)=(b/n);
  1.5) 如若 j≠(b/n),重返n不是素数。
2) 返回n是素数
算法中的1.3平等利用了第2条定律判断出合数。而后又用素数性质加强了判断,所以这一测试准确度更高。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
//  计算(a * b) % mod
long long multiMod(long long a,long long b,long long mod)
{
    long long res=0;
    while(b)
    {
        if(b&1)
        {
            res=res+a;
            if(res>=mod) res-=mod;
        }
        a=a+a;
        if(a>=mod) a-=mod;
        b>>=1;
    }
    return res;
}
//  计算 (a ^ b) % mod
long long powMod(long long a,long long b,long long mod)
{
    long long res=1;
    while(b)
    {
        if(b&1)
        {
            res=multiMod(res,a,mod);
        }
        a=multiMod(a,a,mod);
        b>>=1;
    }
    return res;
}
//  通过a ^ (n - 1) = 1(mod n)来判断n是不是素数
//  n - 1 = x * 2 ^ t中间使用二次判断
//  是合数返回true,不一定是合数返回false
bool check(long long a,long long n,long long x,int t)
{
    long long res=powMod(a,x,n);
    long long last=res;
    for(int i=1;i<=t;i++)
    {
        res=multiMod(res,res,n);
        if(res==1&&last!=1&&last!=n-1) return true;//合数
        last=res;
    }
    return res!=1;//最后res=(a^(n-1) % n),如果res!=1,那么不满足费小马定理,说明不是素数
}
//  生成[ 0 , n ]的随机数
long long randomVal(long long n)
{
    //rand(): 0~RAND_MAX;
    return ((double)rand()/RAND_MAX*n+0.5);
}
//  随机算法判定次数,一般8~10次就够了
const int times=8;
//  Miller_Rabin算法
//  是素数返回true,(可能是伪素数)
//  不是素数返回false
bool Miller_Rabin(long long n)
{
    if(n<2) return false;
    if(n==2) return true;
    if(!(n&1)) return false;//  偶数(合数)
    long long x=n-1,t=0;
    while((x&1)==0)
    {
        t++;
        x>>=1;
    }
    for(int i=0;i<times;i++)
    {
        long long a=randomVal(n-2)+1;
        if(check(a,n,x,t)) return false;
    }
    return true;
}
int main()
{
    long long n,t;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        if(Miller_Rabin(n)) printf("Yes\n");
        else printf("No\n");
    }
}

// cout<<“是合数”<<endl;

DATA_TYPE ComputeR(DATA_TYPE a,DATA_TYPE k,DATA_TYPE n)
{
        DATA_TYPE tmp;
        DATA_TYPE Power[8*sizeof(DATA_TYPE)]={0};
        int i,BitNum;
        int Bin[8*sizeof(DATA_TYPE)]={0};
        BitNum=DecToBin(k,Bin);
//将n-1转换到二进制,二进制位数赋给BitNum
        tmp=a;
        Power[0]=tmp;
        for(i=1;i<BitNum;i++)
        {
                tmp=(tmp*tmp)%n;
                Power[i]=tmp;
        }
        for(i=0,tmp=0;i<BitNum;i++)
        {
                if(Bin[i]==1)
                {
                        if(0==tmp) tmp=1;
                        tmp=(tmp*Power[i])%n;
                }
        }
        return tmp;
}

转载自Matrix大牛
  一个数是素数(也叫质数),当且仅当它的约数唯有七个——1和它本人。规定那三个约数不能够一如既往,因而1不是素数。对素数的斟酌属于数论范畴,你可以看到众多地翻译家没事就想出一部分契合某种性质的素数并称它为某某某素数。整个数论差不多就围绕着整除和素数之类的词转过去转过来。对于写代码的人的话,素数比
想像中的更要紧,谷歌(Google)一下BigPrime依然big_prime你总会发现大堆大堆用到了素数常量的程序代码。平日没事时能够记一些素数下来以
备急用。小编会选一些好记的素数,比如4567, 124567, 3214567, 23456789,
55566677, 1234567894987654321, 11111111111111111111111
(2二个1)。作者的手机号前十位是个素数。小编的网站域名的ASCII码连起来(77 97 116
114 105 120 54 55 46 99 111 109)也是个素数。
  素数有广大神奇的质量。作者写5个在底下供大家欣赏。
1. 素数的个数无限多(不设有最大的素数)
  评释:反证法,假诺存在最大的素数P,那么我们得以协会3个新的数2 * 3
* 5 * 7 * … * P +
1(全体的素数乘起来加1)。显明那些数无法被任一素数整除(全数素数除它都余1),那注脚大家找到了三个更大的素数。
2.
设有任意长的一段连接数,在那之中的全数数都以合数(相邻素数之间的间距任意大)

  证明:当0<a<=n时,n!+a能被a整除。长度为n-1的数列n!+2, n!+3,
n!+4, …,
n!+n中,全体的数都以合数。那几个结论对具备大于1的平头n都建立,而n能够取到任意大。
3. 有所大于2的素数都足以唯一地意味着成七个平方数之差。
   声明:大于2的素数都以奇数。若是那几个 数是2n+1。由于(n+1)^ 2=n^2 +
2n+1,(n+1)^
2和n^2正是我们要找的多个平方数。下边评释这些方案是唯一的。假诺素数p能表示成
a2-b2,则p=a^2-
b^2=(a+b)(a-b)。由于p是素数,那么只恐怕a+b=p且a-b=1,那交给了a和b的绝无仅有解。
4. 当n为大于2的整数时,2 ^n
+1和2^n-1八个数中,要是内部贰个数是素数,那么另三个数一定是合数。

   申明:2^ n不可能被3整除。尽管它被3除余1,那么2^n
-1就能被3整除;假诺被3除余2,那么2^n +1就能被3整除。不问可见,2^n +1和2^n
-第11中学至少有二个是合数。
5. 一旦p是素数,a是小于p的正整数,那么a^(p-1) mod p = 1。
  那些阐明就有点麻烦了。
  首先我们作证那样三个结论:要是p是2个素数的话,那么对自由1个小于p的正整数a,a,
2a, 3a, …, (p-1)a除以p的余数正好是2个1到p-1的排列。例如,5是素数,3, 6,
9, 12除以5的余数分别为3, 1, 4, 2,正好便是1到4那四个数。
  反证法,如若结论不创立以来,那么身为有多少个小于p的正整数m和n使得na和ma除以p的余数相同。无妨假使n>m,则p能够整除a(n-m)。但p是素数,那么a和n-m中至少有三个包蕴因子p。那明显是不大概的,因为a和n-m都比p小。
  
同余式发挥,大家证实了:
  (p-1)! ≡ a * 2a * 3a * … * (p-1)a (mod p)
   也即:
  (p-1)! ≡ (p-1)! * a^(p-1) (mod p)
  两边同时除以(p-1)!,就拿走了小编们的尾声结论:
  1 ≡ a^(p-1) (mod p)
 可惜最终那一个定律最初不是本人表达的。那是大化学家Fermat注解的,叫做Fermat小定理(Fermat’s
Little
西奥rem)。Euler对那几个定律举行了推广,叫做Euler定理。Euler毕生的定律太多了,为了和其他的“Euler定理”不一样开来,某些地方叫做Fermat小定理的Euler推广。Euler定理中须求用3个函数f(m),它表示小于m的正整数中有微微个数和m互素(多个数只有公约数1称
为互素)。为了便于,我们见惯不惊用记号φ(m)来代表这些函数(称作Euler函数)。Euler建议,借使a和m互素,那么a^φ(m)
≡ 1 (mod
m)。可以观察,当m为素数时,φ(m)就等于m-1(全数小于m的正整数都与m互素),因而它是Fermat小定理的加大。定理的表达和Fermat小
定理大约一致,只是要考虑的架势变成了独具与m互素的数的乘积:m_1 * m_2
… m_φ(m) ≡ (a * m_1)(a * m_2) … (a * m_φ(m)) (mod
m)。小编干吗要顺便说一下Euler定理呢?因为上面一句话能够增加本人网站的PV:这一个定律出现在了The
Hundred Greatest
Theorems
里。
  谈到Fermat小定理,数学历史上有很多误解。相当短一段时间里,人们都是为Fermat小定理的逆命题是科学的,并且有人亲自表达了
a=2,
p<300的享有情状。外国甚至流传着一种说法,认为中夏族民共和国在孔圣人时代就表明了那般的定律:假如n整除2^(n-1)-1,则n正是素数。后来某些大不列颠及北爱尔兰联合王国学者进行考证后才意识那是因为他们翻译中华夏族民共和国文言时出了错。1819年有人发现了Fermat小定理逆命题的首先个反例:纵然2的33九次方除以341余
1,但341=11*31。后来,人们又发现了561, 645,
1105等数都评释a=2时Fermat小定理的逆命题不树立。即使那样的数不多,但不能够忽视它们的存在。于是,人们把拥有能整除2^(n-1)-1的合
数n叫做伪素数(pseudoprime),意思便是告诉人们那么些素数是假的。
  不满足2^(n-1) mod n =
1的n一定不是素数;借使满足的话则多半是素数。那样,三个交锋除法效能更高的素雅判断格局出现了:制作一张伪素数表,记录有个别范围内的有着伪素数,那么
全体满意2^(n-1) mod n =
1且不在伪素数表中的n就是素数。之所以那种艺术更快,是因为大家能够运用二分法速算2^(n-1)
mod n
的值,那在电脑的推来推去下变得万分简单;在微型计算机中也能够用二分查找有序数列、Hash表开散列、创设Trie树等艺术使得搜索伪素数表效用更高。
   有
人本来会关切这样一个题材:伪素数的个数到底有些许?换句话说,倘诺笔者只计算2^(n-1)
mod
n的值,事先不准备伪素数表,那么素性判断失误的可能率有些许?切磋那些难点是很有价值的,毕竟大家是OIer,不容许背1个尺寸上千的常量数组带上考场。
计算评释,在前10亿个自然数中国共产党有508475三12个素数,而满足2^(n-1) mod n =
1的合数n有5598个。这样算下来,算法出错的或者约为0.00011。这些概率太高了,要是想免去建立伪素数表的行事,大家须要革新素性判断的算
法。 
   最简便易行的想法便是,大家刚刚只考虑了a=2的情事。对于式子a^(n-1) mod
n,取差异的a大概引致分化的结果。3个合数可能在a=2时透过了测试,但a=3时的总括结果却排除了素数的或然。于是,人们扩充了伪素数的定义,称满足a^(n-1) mod n = 1的合数n叫做以a为底的伪素数(pseudoprime to base
a)。前10亿个自然数中还要以2和3为底的伪素数唯有12柒十三个,那么些数目不到刚刚的四分之一。那告诉大家要是同时验证a=2和a=3二种状态,算法出错
的票房价值降到了0.000025。简单想到,选拔用来测试的a越多,算法越规范。平日我们的做法是,随机采纳若干个低于待测数的正整数作为底数a进行多少次
测试,只要有2遍没有经过测试就立马把这么些数扔回合数的世界。那就是Fermat素性测试。
  人们当然会想,倘诺设想了全部小于n的底数a,出错的概率是还是不是就能够降到0呢?没想
到的是,居然就有那样的合数,它能够透过全体a的测试(这几个说法不标准,详见笔者在地核楼层的东山再起)。Carmichael第一个意识那样极其的伪素数,他
把它们称作Carmichael数。你肯定会以为那样的数一定一点都不小。错。第③个Carmichael数小得惊心动魄,仅仅是三个二位数,561。前10亿个自
然数中Carmichael数也有600个之多。Carmichael数的留存表明,我们还亟需继续坚实素性判断的算法。
  Miller和Rabin四人的劳作让Fermat素性测试迈出了探索性的一步,建立了故事中的Miller-Rabin素性测试算法。
新的测试基于下边包车型地铁定律:假如p是素数,x是小于p的正整数,且x^2 mod p =
1,那么照旧x=1,要么x=p-1。这是无人不晓的,因为x^2 mod p =
1相当于p能整除x^2-1,也即p能整除(x+1)(x-1)。由于p是素数,那么只大概是x-1能被p整除(此时x=1)或x+1能被p整除(此时
x=p-1)。
  
大家下边来演示一下上边的定律怎样行使在Fermat素性测试上。前边说过341得以透过以2为底的Fermat测试,因
为2^ 340 mod 341=1。如若341正是素数的话,那么2^ 170 mod
34一只大概是1或340;当算得2^ 170 mod 341确实等于1时,我们得以继续翻看2^
85除以341的结果。我们发现,2^ 85 mod
341=32,这一结实摘掉了34一头上的素数皇冠,面具前面真实的嘴脸显现了出去,想装扮素数和自家的素MM交往的谋划暴光了出去。
   那正是Miller-Rabin素性测试的方法。不断地领到指数n-第11中学的因子2,把n-1表示成d*2^
r(当中d是八个奇数)。那么大家必要计算的东西就 变成了a的d*2^
r次方除以n的余数。于是,a^(d * 2^
(r-1))要么等于1,要么等于n-1。要是a^(d * 2^
(r-1))等于1,定理继续适用于a^(d * 2^
(r-2)),这样持续开药方开下去,直到对于有些i满意a^(d * 2^i) mod n =
n-1大概最终指数中的2用完了获取的a^d mod n=1或n-1。
  那样,Fermat小定理抓好为如下情势:
   尽只怕提取因子2, 把n-1表示成d*2^r ,要是n是一个素数,那么照旧a^d
mod n=1,大概存在某些i使得a^ (d*2^ i) mod n=n-1 ( 0<=i<r )
(注意i能够等于0,那就把a^d mod n=n-1的境况统一到背后去了)
   Miller-Rabin
素性测试相同是不明确算法,大家把能够经过以a为底的Miller-Rabin测试的合数称作以a为底的强伪素数(strong
pseudoprime)。第多个以2为底的强伪素数为2047。第四个以2和3为底的强伪素数则大到1
373 653。
  Miller-
Rabin算法的代码也格外简单:计算d和r的值(能够用位运算加速),然后二分总结a^d
mod n的值,最终把它平方r次。
素数的性格。

        a = (a + a) % mod;  

int Jacobi(DATA_TYPE a,DATA_TYPE n)
{
        DATA_TYPE temp,e=0,a1,n1;
        int s;
        if(0==a ||1== a)
                return 1;
        temp=a;
        while(temp%2==0)
        {
                temp/=2;
                e++;
        }
        a1=temp;
        if(0== e%2)
                s=1;
        else
        {
                if(1== n%8||7== n%8)
                        s=1;
                else if(3== n%8|| 5== n%8)
                        s=-1;
        }
        if(3== n%4&&3== a1%4)
                s=-s;
        n1=n%a1;
        if(1== a1)
                return s;
        else
                return s*Jacobi(n1,a1);
}

Miller-Rabin质数测试
模板来源:

}

率先种,Fermat素性测试:
算法Fermat(n,t),个中n>2为奇数, t为测试次数.
1) 对 i 从1 到 t 做如下循环:
  1.1) 随机选用 a,1<a<n-1;
  1.2) 计算d=gcd(a,n),如果d>1,则返回“合数”。否则
  1.3) 计算 r ≡ a ^(n-1) (mod n);
  1.4) 若r≠1 ,则返回“合数”。
2) 返回“素数”。
算法主要选用了费马小定理,但a^(p-1)≡1(mod
p)仅是素数的须要条件。上述算法将1个合数判断为素数的出错可能率为5/10^t,但是回到合数的判断总是对的。只要扩充测试次数t,就足以把出错可能率降至趋近于0。

——————Made By Pinging、、、、、hhh  Welcome to
CUMT。。。

依据上述定理大家能够获得部分淡雅判定的功能较高的艺术。上边介绍三种:
Fermat素性测试,Lehmann素性测试和Solovay-Strassen 素性测试。

 

其次种,Lehmann素性测试:
1) 对i从1到t 做如下循环:
1.1)选拔二个小于n的妄动数b;
1.2) 计算b^((n-1)/2) mod n;
1.3) 假如b^((n-1)/2)≠1或-1,那么再次来到合数;(n肯定不是素数)
2) 重返素数。(n不是素数的大概至多是一半)
算法首要行使了下边提到的第三条定律,2是素数且是n-1的素因子,在此间代表了q。

        b /= 2;  

  对一个数是n否为素数的论断能够从2到根号n依次去除n,如若n能被里面1个整除则印证n不是素数,不然n是素数。还足以用厄拉多塞筛法,选拔构造素数表的法子,从2起,依次列出后续数字,假使某些数是日前数字的倍数,则从表中删除,即删掉全体素数的倍数,最终取得的表正是1个全是素数的表。用于程序达成的话,能够安装3个栈,初步时栈内唯有二个要素2,令从3起种种拉长,并判断要是i不是栈内任何三个数的翻番,则令i进栈,否则继续循环,直到达到供给截止。
       以上三种艺术对于较小的数的判断还足以采纳,不过当数字达到十分的大的时候,那二种方法的成效都会十分的低,因此大家要谋求更快的判定二个数是还是不是为素数的办法。首先看多少个定理:

}

定理:设n>1是五个奇数,假设对于n-1的种种素因子q存在七个整数a使得下式创制,则n为素数:
a^(n-1)≡1 (mod n)
a^((n-1)/q)≠1 (mod n)
费马小定理:若p是素数,则对此随意的正整数a≠0(mod p),有
a^(p-1)≡1(mod p)
素数首要性质: a^((p-1)/2)≡ (a/p)(mod p),在那之中p是素数,(a/p)
是雅可比符号

算法的争鸣功底:

  最初的小说地址https://www.douban.com/note/271270932/

    }  

int DecToBin(DATA_TYPE num,int a[])
//十进制转化成二进制,再次回到二进制位数
{
        int BitNum;
        for(BitNum=0;num;BitNum++)
        {
                if(0==num%2)
                        a[BitNum]=0;
                else
                        a[BitNum]=1;
                num/=2;
        }
        return BitNum;
}

return 0;

       两种算法都留存关键性一步便是计量有个别数的幂次模n值,如Fermat素性测试中,总计总括r ≡ a ^(n-1) (mod
n),假设利用对a逐次去总计的办法,时间复杂度是O(n),还比不上起初说的二种算法。所以要想赢得迅捷的朴素判定算法,就要对这一步进行优化。
       逐次总结的三个毛病是,没有丰硕利用每一遍循环中已赢得的音讯。进而能够想到,假若能像人工业总会括时一致,记录下a^2
mod n, a^4 mod n,……,每一回总括时根据须要采用那些已获得的值,比如总计a^254
mod 255。算出a^2 mod 255, a^4 mod 255,……,a^128 mod
255,就能够依照已算得的结果计算a^254 mod
255=a^128*a^64*a^32*a^16*a^8*a^4*a^2 mod
255,丰硕利用了已有音讯。
      于是二个理所当然的想法就是,首先循环三回把a^i mod
n的值记录在三个表中,当中i是2的幂次,然后求出n-1的二进制表示由没有到高位存款和储蓄在数组中,r开端时为1,遍历数组,某位为1时则把表中对应地方的a^i
mod n乘以r的值赋值给r,那样循环三回后即获得了a^(n-1)mod
n的值,速度大大提升。原来总计a^64急需61遍,创新后只需总结a^2,a^4,
a^8,a^16,a^32,a^64 mod
n共5遍即可,并且通过那4遍总计,a的1~六1贰回方模n都可被计算出来,多次测试中均可使用,即便对不小的测试次数也有很高功能。对于long
long 型数据,最大只需循环61遍即可。时间复杂度由O(n)降到了O(logn)。
        这一步达成了,别的细节只须求稍加调节和测试即可,那里仅付给Solovay-Strassen
素性测试的代码。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX_TIME 11111
#define DATA_TYPE long long
bool Solovay_Strassen (DATA_TYPE n,int t);
int Jacobi(DATA_TYPE a,DATA_TYPE n);
DATA_TYPE ComputeR(DATA_TYPE a,DATA_TYPE k,DATA_TYPE n);//计算r=a^k
mod n
int DecToBin(DATA_TYPE num,int a[]);
//十进制转化成二进制,重返二进制位数
int main()
{
        DATA_TYPE n;
        while(1)
        {
                printf(“请输入要一口咬定的数:\n”);
                scanf(“%lld”,&n);
                if(n<=1||(n>2&&n%2==0)||!Solovay_Strassen(n,n>MAX_TIME?MAX_TIME:n-2))
                        printf(“%lld不是素数\n”,n);
                else
                        printf(“%lld是素数\n”,n);
                printf(“\n”);
        }
        return 0;
}
bool Solovay_Strassen (DATA_TYPE n,int t)
{
        int i;
        DATA_TYPE Rand_Num,r,jac;
        srand((unsigned int)time(NULL));
        for(i=0;i<t;i++)
        {
                //注释起来这一段用来判定是还是不是有专擅数重复,如再一次则再次生成,在n丰富大时,这一段理论上得以忽略
/* DATA_TYPE Choosed[MAX_TIME]; //记录已选的妄动数
                bool flag; //标记是不是有重复
                do
                {
                        flag=0;
                        do
                        {
                                Rand_Num=rand()%n;
                        }while(Rand_Num<=1||Rand_Num>n-1);
                        for(int j=0;j<i;j++)
                        {
                                if(Rand_Num==Choosed[j]) //已采用过
                                {
                                        flag=1; //置标记位为1
                                        break;
                                }
                        }
                }while(flag);
                Choosed[i]=Rand_Num;*/
                do
                {
                        Rand_Num=rand()%n;
                }while(Rand_Num<=1||Rand_Num>n-1);
                r=ComputeR(Rand_Num,(n-1)/2,n);
                if(!(1==r ||r==n-1))
                        return 0;
                jac=Jacobi(Rand_Num,n);
                if(jac<0)
                        jac=n+jac;
                if(r!=jac)
                        return 0;
        }
        return 1;
}

试验须求基于那么些算法的说理来落到实处对素数的判定效用,而自笔者将上述申辩用C++的
情势写了出去,然后在部分细节的算法上少做润色,成功落到实处了对素数的扭转和判断。

 

ll num;

}

 

srand((unsigned)time(NULL));

    long long ans = 0;  

// if(b&1) ans = (ans*base)%mod;

if(Miller_Rabin(n)==0) return false;

        {  

k++;

 

return 0;

// }

一、试验代码:

q=q/2;

int times = 10;

 

long long q_mul( long long a, long long b, long long mod )   

//long long q_pow(ll a,ll b,ll mod){

if(result1 == n-1) return 1;

// return ans;

 

ll result1 = q_pow(a,q,n);

    while(b)  

{  

}

        a = q_mul( a, a, mod );  

if(True_Miller_Rabin(i)){

}

 

    {  

 

 

二、尝试结果(自行测试)

// if(Miller_Rabin(num)==1)

以上结果证实,该程序完全能够胜任在long
long类型范围下的素数判定职分。

            ans =(ans+ a)%mod;  

 

那是对输入素数的判读

//}

return true;

long long q_pow( long long a, long long b, long long mod )  

// base = (base*base)%mod;

{  

        b /= 2;  

            ans = q_mul( ans, a, mod );  

if(n==2) return 1;

bool True_Miller_Rabin(ll n){

typedef unsigned long long ll;

cout<< i<<“是素数”<<endl;

 

int Miller_Rabin(ll n) {

// ll base=a;

// while(b!=0){

 

if(result1 == 1||result1 == n-1){

 

times–;

 

 

 

2.
 纵然n是八个奇素数,将n−1表示成2^s*r的情势,r是奇数,a与n是互素的别样随机整数,那么a^r
≡ 1 mod n恐怕对某些j (0 ≤ j≤ s−1, j∈Z) 等式a^(2jr) ≡ −1 mod n 创设。

}

// b>>=1;

    {  

   

 

}

        }  

// cout<<“为素数”<<endl;

 

    return ans;  

while(k–){

        if(b & 1)  

ll a = rand(); //要保证a在(1,n-1)之间,开区间

 

        if(b & 1)  

ll k=0,q=n-1;

for(ll i=1000000;i<=1005000;i++){

a=(a%(n-2))+2;

// while(1){

            

  1. Fermat定理:若n是奇素数,a是轻易正整数(1≤ a≤ n−1),则 a^(n-1) ≡ 1
    mod n。

    return ans;  

}

三、试行计算

    }  

 

 

int main()

{

// ll ans = 1;

if(n<2) return 0;

大家都理解LANDSA的加密的安全性正是能够找到一个适龄的大素数,而前天判定大素数的措施有不足为奇,比如Fermat素性测试可能米尔er-Rabin素性测试,而那边笔者用了Miller-Rabin素性测试的算法,具体的驳斥本身写到上面。

    long long ans = 1;  

那是对一千000000000000000到一千00000000000陆仟里全体素数判定的结果

    while(b)  

            b–;  

        {  

}

 

while(times){

#include<cstdlib>  

        }  

 

#include<cmath>

result1 = q_mul(result1,2,n);

}

 

#include<iostream>

// }

  

 

#include<ctime>

// cin>>num;

 return 1;

// }

using namespace std;

// else{

}

int a =0;

本次实验应用了Miller-Rabin算法,而在明亮算法的底子上大家要灵活运用。在算法中笔者最开首用到了C++函数里面包车型客车pow函数,但是那个函数导致小编素数输出不完整,经过很久的调节,笔者发现是C++自带Curry面包车型大巴数据类型与long long类型有出入,所以本身割舍了选用自带的函数库。之后,笔者选拔了火速幂算法。这么些算法比pow函数效果更好,能够对天意举行火速的幂总括。但是在高效幂计算的历程中执会调查计算局筹到两个数相乘,当八个Long 类型的数目相乘时会溢出从而导致总计的大素数长度有限。于是自个儿有考虑将幂计算里面的乘法分成若干个加法去开展演算,于是自身使用了高效乘与急迅幂想结合的格局,也正是自己上述代码浅暗黄的一对(灰色部分为单纯神速幂),由此作者讲幂运算的快慢有升级了2个程度,在此基础上也增大了总计素数的界定。

while(q%2==0){