精华内容
下载资源
问答
  • 复查素数测试算法并测试其性能,以找出最快的算法。
  • Miller-Rabin素数测试算法

    万次阅读 多人点赞 2018-09-02 12:18:49
    知识点系列之---Miller-Rabin素数测试

    【作用】

    有时候我们想快速的知道一个数是不是素数,而这个数又特别的大导致 O( \sqrt{n} ) 的算法不能通过,这时候我们可以对其进行 Miller-Rabin 素数测试,可以大概率测出其是否为素数。

    【两个基础理论】

    (1)费马小定理:当 p 为质数,有 a^{p-1}\equiv 1(mod \: \, p),不过反过来不一定成立,也就是说,如果 ap 互质,且 a^{p-1}\equiv 1(mod \: \, p),不能推出 p 是质数,比如 Carmichael 数(这个就自行百度吧)

    (2)二次探测:如果 p 是一个素数,0 < x < p, 则方程 x^{2}\equiv 1(mod\: \, p) 的解为 x = 1x = p - 1

    【两个基本理论的证明】

    证明转载费马小定律&二次探测的证明

    【算法流程】

    (1)对于偶数和 0,1,2 可以直接判断。

    (2)设要测试的数为 x,我们取一个较小的质数 a,设 s,t,满足 2^s\cdot t=x-1(其中 t 是奇数)。

    (3)我们先算出 a^t,然后不断地平方并且进行二次探测(进行 s 次)。

    (4)最后我们根据费马小定律,如果最后 a^{x-1}\not\equiv 1(mod \:\, x),则说明 x 为合数。

    (5)多次取不同的 a 进行 Miller-Rabin 素数测试,这样可以使正确性更高

    【备注】

    (1)我们可以多选择几个 a,如果全部通过,那么 x 大概率是质数。

    (2)Miller-Rabin 素数测试中,“大概率”意味着概率非常大,基本上可以放心使用。

    (3)当 a 取遍小等于 30 的所有素数时,可以证明 int 范围内的数不会出错。

    (4)代码中我用的 int 类型,不过实际上 Miller-Rabin 素数测试可以承受更大的范围。

    (5)另外,如果是求一个 long long 类型的平方,可能会爆掉,因此有时我们要用“快速积”,不能直接乘。

    【代码】

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int prime[10]={2,3,5,7,11,13,17,19,23,29};
    int Quick_Multiply(int a,int b,int c)  //快速积(和快速幂差不多) 
    {
        long long ans=0,res=a;
        while(b)
        {
            if(b&1)
              ans=(ans+res)%c;
            res=(res+res)%c;
            b>>=1;
        }
        return (int)ans;
    }
    int Quick_Power(int a,int b,int c)     //快速幂,这里就不赘述了 
    {
        int ans=1,res=a;
        while(b)
        {
            if(b&1)
              ans=Quick_Multiply(ans,res,c);
            res=Quick_Multiply(res,res,c);
            b>>=1;
        }
        return ans;
    }
    bool Miller_Rabin(int x)     //判断素数 
    {
        int i,j,k;
        int s=0,t=x-1;
        if(x==2)  return true;   //2是素数 
        if(x<2||!(x&1))  return false;     //如果x是偶数或者是0,1,那它不是素数 
        while(!(t&1))  //将x分解成(2^s)*t的样子 
        {
            s++;
            t>>=1;
        }
        for(i=0;i<10&&prime[i]<x;++i)      //随便选一个素数进行测试 
        {
            int a=prime[i];
            int b=Quick_Power(a,t,x);      //先算出a^t
            for(j=1;j<=s;++j)    //然后进行s次平方 
            {
                k=Quick_Multiply(b,b,x);   //求b的平方 
                if(k==1&&b!=1&&b!=x-1)     //用二次探测判断 
                  return false;
                b=k;
            }
            if(b!=1)  return false;   //用费马小定律判断 
        }
        return true;   //如果进行多次测试都是对的,那么x就很有可能是素数 
    }
    int main()
    {
        int x;
        scanf("%d",&x);
        if(Miller_Rabin(x))  printf("Yes");
        else  printf("No");
        return 0;
    }

    展开全文
  • Miller-Rabin概率素数测试算法

    万次阅读 多人点赞 2016-11-05 16:37:23
    下面我们开始正文,从源头开始真正的梳理一下素数测试1.素数我们都知道,素数在当今的数论中占有非常重要的地位,主要原因就是素数最根本的性质——除了1,和自身以外,不会被任何一个数整除 并且,素数现在在我们...

    本文首先鸣谢以下资料文章:
    资料1
    资料2
    资料3
    下面我们开始正文,从源头开始真正的梳理一下素数测试

    1.素数

    我们都知道,素数在当今的数论中占有非常重要的地位,主要原因就是素数最根本的性质——除了1,和自身以外,不会被任何一个数整除
    并且,素数现在在我们的日常生活中伴有非常重要的地位,这一点的其一主要原因就是素数已经是密码学中最重要的一点,我们当今的密码学常常要涉及到利用超大素数作为我们的密钥和核心,所以说,我们对素数的研究就变得非常的重要了
    很是遗憾,现在我们并没有一套合理的算法体系去真正的获取一个绝对100%是素数的一个非常大的数,这是当前做不到的,因为目前的确定性的算法朝朝大素数无外乎两种情况,耗时和空间占用,但是本文将从一种全新的角度带大家研究一种非确定性算法,该算法虽然并不是100%正确的,但是我们如果加上限制条件,我们可以将该算法的错误率降低到几乎可以忽略的程度,这也就是我们本文即将讲述的重点——Miller-Rabin算法

    2.朴素素数测试 + 筛法

    我们从刚开始学编程的时候,大学老师都会给我们将一种非常糟糕的算法(当然这处理我们的考试已经够了)这种算法叫做试除法
    算法描述:
    对一个已知的待测的数n,k从2开始一直到n-1,我们如果发现k|n,那么我们认为这是一个合数
    当然,这是我们从素数的定义出发的一种算法,之所以说这种算法糟糕是因为当我们的待测的数非常的大的时候,我们不得不遍历一整遍数据来保证算法的正确性,这是无法容忍的
    可能有的人还想在这个算法上搞搞优化什么的,其实都是治标不治本
    至于朴素素数测试和筛法测试我会援引我的博客作为讲解
    Lantian的朴素素数测试和筛法素数生成算法讲解
    在这里我先声明:
    筛法是一种非常高效的算法,但是在这里筛法没有办法发挥他的优势,因为筛法真正强大在可以快速的生成一定范围内的所有的素数,但是我们这里强调的是对超大素数的测试,并不需要获取那么多的素数

    以上,筛法和朴素测试的时间复杂度都是O(n)和无限接近O(n),在这里我们确定性算法就走到了尽头,下面有请非确定性概率测试算法来施展身手

    3.必要数论基础知识

    在我们继续研究之前,我们还需要一些必备的知识来为我们打通道路
    1.费马小定理:
    其实在讲费马小定理之前,我们其实还需要讲解欧拉定理,飞马小丁立只是欧拉定理的特殊情况
    欧拉定理:
    欧拉定理这里的n,a必须是互素(Gcd(n,a)=1)
    费马小定理:
    费马小定理当欧拉定理中的n是素数的时候,很显然欧拉函数的值是n-1,费马小定理成立,这里就不描述费马小定理的证明了
    2.二次探测定理:
    二次探测定理
    为了更好的了解Miller-Rabin算法,我们在这里必须需要了解二次探测定理的证明和原理,相信我,这不难
    首先,先给出二次探测定理的描述:
    如果p是素数,x是小于p的正整数,且,那么要么x=1,要么x=p-1。这是显然的,因为相当于p能整除,也即p能整除(x+1)(x-1)。由于p是素数,那么只可能是x-1能被p整除(此时x=1) 或 x+1能被p整除(此时x=p-1)。

    4.费马测试

    首先我们先来看看费马测试
    刚才我们的费马小定理已经说明了素数成立的必要条件,也就是说,如果一个数不满足费马小定理,那么这个数必定是合数,但是如果这个数满足我们就没有办法确定是不是合数还是素数了,因为历史上有一种非常神秘的数的存在——卡密歇尔数,这类数我们也叫伪素数
    如果想要了解更多的话,可以百度查询,我们这里只需要了解到,因为卡米歇尔书满足费马小定理但是同时又不是素数,所以这使得我们的费马测试(费马小定理的逆定理)不是正确的,也就不能称之为算法
    但是我们还是需要知道这种测试的情况的,对于至少也是一种测试算法
    一般以2为a做测试,我们一般应用费马测试的时候都是提前利用了一张伪素数表来进行容错处理,当我们找到了满足费马测试并且又不在伪素数表(基于底数2)上的时候我们就可以断定是一个素数,但是这样有两个缺点:
    1.占用时间,我们生成伪素数需要很大的计算资源(我还真不知道有什么好的算法可以快速求伪素数)
    2.当我们内存资源不允许伪素数表的时候,我们的费马测试错误率太高,不能实际应用

    费马小定理毕竟只是素数判定的一个必要条件.满足费马小定理条件的整数n未必全是素数.有些合数也满足费马小定理的条件*.这些合数被称作Carmichael数,前3个Carmichael数是561,1105,1729.
    Carmichael数是非常少的.在1~100000000范围内的整数中,只有255个Carmichael数.数据越大,之后的卡米歇尔数越稀疏
    但是在允许伪素数表的情况下对于快速计算幂取模的话(因为测试的素数非常的大)我们可以用快速幂来实现:Lantian的快速幂算法详解

    5.Miller-Rabin素性测试

    Miller和Rabin两个人的工作让Fermat素性测试迈出了革命性的一步,建立了Miller-Rabin素性测试算法
    在这之前,我们为了更好的了解算法的本质,我们来看一下伪素数341是如何被Miller-Rabin的二次探测定理卡掉的
    一下摘引自资料1:
    我们下面来演示一下上面的定理如何应用在Fermat素性测试上。前面说过341可以通过以2为底的Fermat测试,因为2^340 mod 341=1。如果341真是素数(对于任意的x<341,我们必须都要满足x=1||x=340)的话,那么2^170(2^340开方,这时候的2^340满足了)mod 341只可能是1或340;当算得2^170 mod 341确实等于1时,我们可以继续查看2^85除以341的结果。我们发现,2^85 mod 341=32,这一结果摘掉了341头上的素数皇冠

    在这里,我们抽离一下本质,我们用Miller-Rabin做素数测试的时候将a^(n-1)
    转化成了a^(d*2^r)这里的d是一个正奇数(1也是)

    这就是Miller-Rabin素性测试的方法。不断地提取指数n-1中的因子2,把n-1表示成(其中d是一个奇数)。那么我们需要计算的东西就变成了除以n的余数。于是,要么等于1,要么等于n-1。如果等于1,定理继续适用于,这样不断开方开下去,直到对于某个i满足或者最后指数中的2用完了得到的
    在这里我们需要明确一点,当这种情况出现的时候,我们没有办法继续满足二次探测定理了,我们就不对这种情况继续判断,支队等于1的情况继续用二次探测定理判断

    所以我们的算法流程就出来了
    我们首先从先计算出
    x=(mod n)
    然后如果x=n-1,我们返回true,是一个素数
    如果不是我们继续判断知道,我们中途发现x!=1&&x!=n-1我们返回false,是个合数
    知道最后,我们看看剩下的数是1还是n-1还是别的数

    在这里我们还有一些技巧需要学习:
    1.利用数论的只是证明之后我们可以发现,只要我们的Miller-Rabin多次随机选择底数a的话,重复进行k次,我们可以将错误降低到2^(-k),次数越多越精确,错误概率越小
    2.Miller-Rabin素性测试同样是不确定算法,我们把可以通过以a为底的Miller-Rabin测试的合数称作以a为底的强伪素数(strong pseudoprime)。第一个以2为底的强伪素数为2047。第一个以2和3为底的强伪素数则大到1 373 653。
    Miller-Rabin算法的代码也非常简单:计算d和r的值(可以用位运算加速,即快速积,快速幂),然后二分计算的值,最后把它平方r次。
    3.对于大数的素性判断,目前Miller-Rabin算法应用最广泛。一般底数仍然是随机选取,但当待测数不太大时,选择测试底数就有一些技巧了。比如,如果被测数小于4 759 123 141,那么只需要测试三个底数2, 7和61就足够了。当然,你测试的越多,正确的范围肯定也越大。如果你每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试,所有不超过341 550 071 728 320的数都是正确的。如果选用2, 3, 7, 61和24251作为底数,那么10^16内唯一的强伪素数为46856248255981
    4.最好不要用合数作为底,出错概率太大,至少也是素数作为底,证明的话,不会

    6.Miller-Rabin 代码

    本人用正向迭代和反向迭代都了一遍,发现正向迭代在很大的偶数的情况下比反向的速度快一点点,平均的时间都差不多

    #include"iostream"
    #include"cstdio"
    #include"cstring"
    #include"cstdlib"
    #include"ctime"
    using namespace std;
    
    long long quicks(long long a,long long b,long long c)
    {
        long long ans=1;
        a=a%c;
        while(b!=0)
        {
            if(b & 1) ans=(ans*a)%c;
            b>>=1;
            a=(a*a)%c;
        }
        return ans;
    }
    
    bool Miller_Rabin_1(long long n)   //标准代码 
    {
        long long t=0;
        long long b=n-1;
        while((b&1)==0)
        {
            t++;
            b>>=1;
        }
        //现在的a^(b*2^t)=1(mod n)
        long long a=11;   //测试
        long long x=quicks(a,b,n);
        //个人认为这里如果加上优先判定是不是1,n-1的话,会更快一点?是不是呢????? 
        for(long long i=1;i<=t;i++)
        {
            long long y=quicks(x,2,n);
            if(y==1&&x!=1&&x!=n-1) return false;    //这里的意思是如果a^(d*2^r)是1,但是a^(d*2^(r-1))不是1也不是n-1的情况,这时候我们认为是合数 
            x=y;
        } 
        if(x!=1) return false;
        else return true;
    }
    
    bool Miller_Rabin_2(long long n)   //正向迭代 
    {
        long long p=n-1;
        long long a=11;
        long long x=quicks(a,p,n);
        if(x==n-1) return true;
        else
        {
            long long w;
            do
            {
                p>>=1;
                w=quicks(a,p,n);
                if(w==n-1) return true;
                else if(w!=1) return false;
            }
            while((p&1)!=1);
    
            if(w==1||w==n-1) return true;
            else return false;
        }
    }
    
    
    int main()
    {
        double time=clock();
        if(Miller_Rabin_1(2222222222222222222222)) printf("YES\n");
        else printf("NO\n");
        printf("%lf\n",clock()-time);
        time=clock();
        if(Miller_Rabin_2(2222222222222222222222)) printf("YES\n");
        else printf("NO\n");
        printf("%lf\n",clock()-time);
        return 0;
    }

    7.Thinking

    感谢前人的无私分享,我在匍匐前进,特以此文鸣谢资料和论文的作者
    剩余几个问题待解:
    1.算法中最后的(n-1)|x的情况为什么不考虑,只考虑x!=1的情况?
    2.在检查的过程中,如果出现了(n-1)|x我们怎么回避呢
    3.在计算出来d,b之后我们可不可以提前判断一下a^d是不是1或者n-1的倍数从而加快速度呢?

    展开全文
  • 素数测试算法-Miller-Rabin算法

    千次阅读 2015-11-01 20:45:31
    对于数据太大导致无法用素数筛选法打表处理(百万级),就可以用素数测试算法。 Miller-Rabin算法是目前主流的基于概率的素数测试算法,在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-...

    对于数据太大导致无法用素数筛选法打表处理(百万级),就可以用素数测试算法。

    Miller-Rabin算法是目前主流的基于概率的素数测试算法,在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究,证明在计算机中构建密码安全体系时, Miller-Rain算法是完成素数测试的最佳选择。通过对Miller-Rabin 算 法底层运算的优化,可以取得较以往实现更好的性能。

    模板代码:

    #include<iostream>
    #include<math.h>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    typedef unsigned long long llong;
    /*Miller-Rabin*/
    llong mod_pro(llong x,llong y,llong n)
    {
        llong ret=0,tmp=x%n;
        while(y)
        {
            if(y&0x1)if((ret+=tmp)>n)ret-=n;
            if((tmp<<=1)>n)tmp-=n;
            y>>=1;
        }
        return ret;
    }
    llong mod(llong a,llong b,llong c)
    {
        llong ret=1;
        while(b)
        {
            if(b&0x1)ret=mod_pro(ret,a,c);
            a=mod_pro(a,a,c);
            b>>=1;
        }
        return ret;
    }
    llong ran()
    {
        llong ret=rand();
        return ret*rand();
    }
    bool is_prime(llong n,int t)
    {
        if(n<2)return false;
        if(n==2)return true;
        if(!(n&0x1))return false;
        llong k=0,m,a,i;
        for(m=n-1;!(m&1);m>>=1,k++);
        while(t--)
        {
            a=mod(ran()%(n-2)+2,m,n);
            if(a!=1)
            {
                for(i=0;i<k&&a!=n-1;i++)
                    a=mod_pro(a,a,n);
    
                if(i>=k)return false;
            }
        }
        return true;
    }
    int main()
    {
        llong n;
        while(scanf("%I64u",&n)!=EOF)
            if(is_prime(n,3))
                cout<<"YES\n";
            else
                cout<<"NO\n";
            return 0;
    }
    


    展开全文
  • 看了好久终于把这个Miller_Rabin...然后费马定理是一个必要条件,也就是说素数一定满足这个定理,但满足这个定理的不一定是素数,比如说Carmichael数(我没研究过,有兴趣的同学自己百度吧,反正这种数就是反例)。...

    看了好久终于把这个Miller_Rabin搞懂了,觉得自己棒棒哒~~~最后是在下面那篇博客里搞懂的,这里推荐给大家

    -->参考<--

    【写在前面】

    费马定理 and 二次探测<证明来源>

    然后费马定理是一个必要条件,也就是说素数一定满足这个定理,但满足这个定理的不一定是素数,比如说Carmichael数(我没研究过,有兴趣的同学自己百度吧,反正这种数就是反例)。

     

    【正文】

    了解这两个东西后,我们就可以开始搞事情了

    问题引入

    这道题就是让我们在给出的整数集合中统计有多少个素数,这个整数集合的大小在int范围以内,大概就是4294967296(哈哈,其实就是1e9级别的)

    幼儿园做法:对于集合中的每一个数,我们都用试除法,每个数都会有\sqrt{n}次的枚举,大概就是一个数65536上线,然后还有好多好多的数,妥妥的TLE

    小学生做法:机智一点的小可爱会想到什么线性筛,什么埃拉托斯特尼筛法,但是哪一个的复杂度里没有带 n 的呢????又是一个TLE

    高中生做法:胡乱的来几下Miller_Rabin,没错就是宇宙无敌超可爱的博主我啦(请自动无视)

    通过这几种方法的对比,我们就知道了Miller_Rabin算法的作用,对于很大的一个数快速判断其是否为质数。

    但我们要知道Miller_Rabin这个算法是个大概率算法,也就是说不能100%保证验证的正确性,但据说75%的概率准确,而且通常情况下多搞几次,错的概率就很小了

    铺垫弄完了,我们正经的讲算法了!!!

    假设现在我们需要判断一个数x是否为质数:

    若为2,则判断true

    若为非2的偶数或1,则直接判断false

    若都不是的话,我们就前往下一步

    由于费马定理:a^(p-1)≡1(mod p).【p为质数】那如果我们的目标 x 不满足:a^(x-1)≡1(mod x)则x肯定不为质数

    然后令 x-1 = u* 2^t ,求出 u,t,其中u是奇数(因为如果u为偶数,那么u中肯定含有因子2,那就可以提到2^t里面去)

    变一下形:a^(x-1)≡1(mod x) => a^(u* 2^t )≡1(mod x) => (a^u)^(2^t )≡1(mod x) 【对于a我们是随机取的一个1~x之间的数】

    我们令b=(a^u)%x,然后是t次循环,每次循环都让y=(b*b)%x,b=y,这样t次循环之后b=a^(u*2^t)=a^(n-1)了。这个时候二次探测就派上用场了,由于y=(b*b)%x中b是1~x中间的一个数(因为b一直在对x取模),若 y=(b*b)%x = 1,假设x是质数,那么b=1或b=x-1,那反过来如果b!=1且b!=x-1,那x肯定不是素数了

    t次循环结束后,由于费马定理,这时如果b!=1,那x就不为素数了

    因为Miller-Rabin得到的结果的正确率为 75%,所以要多次循环来提高正确率

    最后若循环多次之后还没返回false,那么x肯定是素数了,返回true

     

    【代码】

    #include<cstdio>
    #include<cmath>
    #include<cstring> 
    #include<iostream> 
    #include<algorithm>
    #define ll long long
    #define in read()
    using namespace std;
    ll ans=0,n,x;
    inline ll read(){
    	char ch;ll res=0;
    	while((ch=getchar())<'0'||ch>'9');
    	while(ch>='0'&&ch<='9'){
    		res=(res<<3)+(res<<1)+ch-'0';
    		ch=getchar();
    	}
    	return res;
    }
    ll mod_mul(ll a,ll b,ll mod){//快速积(和快速幂思想一模一样)
    	ll ans=0;
    	while(b){
    		if(b&1) ans=(ans+a)%mod;
    		a=(a+a)%mod;
    		b>>=1;
    	}
    	return ans;
    }
    ll mod_pow(ll a,ll b,ll mod){//快速幂
    	ll ans=1;
    	while(b){
    		if(b&1) ans=mod_mul(ans,a,mod);//这个地方要注意一下在这里可以写作ans*a%mod,但更一般的情况下,比如测的数很大很大,此时乘的时候可能会爆long long,而用函数的时候就边乘边取模,就不会爆了
    		a=mod_mul(a,a,mod);
    		b>>=1;
    	}
    	return ans;
    }
    bool miller(ll x){//由于和讲解时使用的符号都是统一的,所以我就不再批注了
    	int i,j,k,s=10;//s是循环的次数,用来提高正确率的那个
    	ll u=x-1,t=0;
    	if(x==2) return true;
    	if(!(x&1)||x<2) return false;
    	while(!(u&1)){//如果为偶数,就一直除以2,直到u为奇数
    		t++;
    		u>>=1;
    	}
    	for(i=1;i<=s;++i){
    		ll a=rand()%(x-1)+1;//随机搞,不过由可爱的勾勾同学亲自试验,发现如果用素数搞会快哦
    		ll b=mod_pow(a,u,x),y;
    		for(j=0;j<t;++j){
    			y=mod_mul(b,b,x);
    			if(y==1&&b!=1&&b!=x-1)
    				return false;
    			b=y;
    		}
    		if(b!=1) return false;
    	}
    	return true;
    }
    int main()
    {
    	while(scanf("%lld",&n)!=EOF){
    		ans=0;
    		int i,j,k;
    		for(i=1;i<=n;++i){
    			x=in;
    			if(miller(x)) ans++;
    		}
    		cout<<ans<<endl;
    	}
    	return 0;
    }
     

    对于评论区我进行解释:

    由于这道题我是作为Miller_Rabin的板子题,就把它当做最一般的情况进行处理的,并没有太考虑数据范围

    所以有些地方针对此题是可以简写的,甚至用幼儿园做法

    展开全文
  • 素数测试算法

    2015-12-20 16:12:58
    素数测试算法课程设计,讲述了素数算法的代码,还有一些想法
  • 素数测试随机算法

    千次阅读 2017-10-30 22:16:24
    素数测试随机算法
  • 素数测试算法

    2016-05-17 13:54:18
    昨天刷LeetCode 时候遇到判断素数的问题 204.Count Primes ,想起hihocoder上之前也出现过,但是当时没看。 于是今天整理了一些关于判断一个数是否是素数的知识。因为大部分的内容都是别人的,所以下文主要是提供...
  • GMP大数库的中文使用手册,以及已经编译好的GMP大数库,仅适用于VC6.0,并有自己写的生成随机大素数,大整数模运算,以及Miller Rabin素数测试算法
  • 朴素算法能过 #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<vector> #include<queue> #include<stack>...
  • 一.Miller-Rabin素数测试算法: 快速判断一个1e18范围内的数是否为素数,对其进行Miller-Rabin素数测试,可以大概率判断其是否为素数,出错的概率为1/4的k次方,k为测试次数。故当测试次数越多,其出错概率越小。 1....
  • Miller_Rabin素数测试算法模板对比

    千次阅读 2015-08-28 16:12:15
    昨天在USACO做了一道判断素数的题,就想着学习一下Miller_Rabin素数测试算法,在网上找到两种模版,第一种十分简洁,运行速度也很快,但是会判错极少的几个非素数;第二种比较麻烦,运行速度很慢,所以我便想找到第...
  • 2、对该整数进行小素数检验,在进行miller_rabin算法检测 3、获得大素数p、q后,计算n、e、的d过程有说明 4、可以对任意数字字母汉字加解密 5、内容的注释详细,易理解;用像伪代码般的python码出来的更容易对代码...
  • 大佬博客 个人比较菜会用板子就好了。 送上例题hdu 2138 虽然暴力可以过但是还是用来学算法吧。#include #include #include #include #include #define LL long long using namespace std; const int maxn=1
  • Miller−rabinMiller-rabinMiller−rabin算法是一个用来快速判断一个正整数是否为素数算法,它利用了费马小定理和二次探测: 费马小定理:如果ppp是质数且a⊥pa \perp pa⊥p互质,那么ap−1≡1  (mod&...
  • 在数据范围在LL类型之中,N_maxLL=1e18,即使在O(sqrt(n))的时间复杂度之内也不能够满足要求,这时候我们可以对其进行Miller-Rabin 素数测试,可以大概率测出其是否为素数,大部分情况下是正确的; 二.理论基础: ...
  • 因为文中存在公式,只能用图片方式上传了! 以下为C语言源代码: #include <stdio.h> typedef long long unsigned LLU;...BOOL isPrime(LLU n) { //这是传统的方法,用于与Miller-Rabin算法的结...
  • 下面我们开始正文,从源头开始真正的梳理一下素数测试 1.素数 我们都知道,素数在当今的数论中占有非常重要的地位,主要原因就是素数最根本的性质——除了1,和自身以外,不会被任何一个数整除 并且,素数...
  • ++i) //随便选一个素数进行测试 { int a=prime[i]; int b=Quick_Power(a,t,x); //先算出a^t for(j=1;j;++j) //然后进行s次平方 { k=Quick_Multiply(b,b,x); //求b的平方 if(k==1&&b!=1&&b!=x-1) //用二次探测...
  • 素数判定算法

    千次阅读 2019-04-08 01:00:51
    1、取余算法 对一个大于1的自然数 n 依次判断 2 → √n 能否整除 n,如果发现一个数能整除 n,那么 n 不是素数,否则是。 C++代码如下: bool isPrime(int n) { if (n <= 1) return false;i for (int i =...
  • 普通的素数测试我们有O(√ n)的试除算法。事实上,我们有O(slog³n)的算法。 定理一:假如p是质数,且(a,p)=1,那么a^(p-1)≡1(mod p)。即假如p是质数,且a,p互质,那么a的(p-1)次方除以p的余数恒等于1。(费马小...
  • 最近看到一篇高效的素数判断算法文章,但是文章中有些部分写的还不够完整清晰,所以在此详细记录一下此算法理解过程。(理解此算法前应先明白使用 sqrt(num) 为判断条件判断素数的方法) 此算法产生的原因(定理):...
  • Miller-Rabin素数测试算法 前置技能: 1: 费马定理 2: 二次探测定理

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,249
精华内容 7,699
关键字:

素数测试算法