大素数检测算法 Miller-Rabin

一时失言乱红尘 2022-05-16 14:06 158阅读 0赞

转载自：[https://blog.csdn.net/u012061345/article/details/48241581][https_blog.csdn.net_u012061345_article_details_48241581]

typedef long long llt;
    //利用二进制计算a*b%mod
    llt multiMod(llt a,llt b,llt mod){
        llt ret = 0LL;
        a %= mod;
        while( b ){
            if ( b & 1LL ) ret = ( ret + a ) % mod, --b;
            b >>= 1LL;
            a = ( a + a ) % mod;
        }
        return ret;
    }
    
    //计算a^b%mod
    llt powerMod(llt a,llt b,llt mod){
        llt ret = 1LL;
        a %= mod;
        while( b ){
            if ( b & 1LL ) ret = multiMod(ret,a,mod),--b;
            b >>= 1LL;
            a = multiMod(a,a,mod);
        }
        return ret;
    }
    
    //Miller-Rabin测试,测试n是否为素数
    bool Miller_Rabin(llt n,int repeat){
        if ( 2LL == n || 3LL == n ) return true;
        if ( !( n & 1LL ) ) return false;
    
        //将n分解为2^s*d
        llt d = n - 1LL;
        int s = 0;
        while( !( d & 1LL ) ) ++s, d>>=1LL;
    
        srand((unsigned)time(0));
        for(int i=0;i<repeat;++i){//重复repeat次
            llt a = rand() % ( n - 3 ) + 2;//取一个随机数,[2,n-1)
            llt x = powerMod(a,d,n);
            llt y = 0LL;
            for(int j=0;j<s;++j){
                y = multiMod(x,x,n);
                if ( 1LL == y && 1LL != x && n-1LL != x ) return false;
                x = y;
            }
            if ( 1LL != y ) return false;
        }
        return true;
    }

[https_blog.csdn.net_u012061345_article_details_48241581]: https://blog.csdn.net/u012061345/article/details/48241581

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关素数的算法

素数就是质数，除了1和他本身，不能整除其他小于他自己的自然数。网上和书本上的定义都是不能被其他1和他本身之外的自然数整除，实际上很容易让人产生歧义，多大范围的自然数？

我会带着你远行/ 2022年10月22日 04:28/ 0 赞/ 162 阅读

相关第K大素数

第K大素数 Time Limit: 1000ms Memory limit: 32768K 有疑问？点这里^\_^ 题目描述大家都知道素数是数学中很有意思的

超、凢脫俗/ 2022年08月10日 04:59/ 0 赞/ 423 阅读

相关亚像素数值极值检测算法总结

动机在计算机视觉领域，经常需要检测极值位置，比如SIFT关键点检测、模板匹配获得最大响应位置、统计直方图峰值位置、边缘检测等等，有时只需要像素精度就可以，有时则需要亚像

悠悠/ 2022年05月19日 12:37/ 0 赞/ 176 阅读

相关大素数检测算法 Miller-Rabin

转载自：[https://blog.csdn.net/u012061345/article/details/48241581][https_blog.csdn.net_u012

一时失言乱红尘/ 2022年05月16日 14:06/ 0 赞/ 159 阅读

相关素数的高效算法

素数最简单的判断方法是采用枚举，复杂度为O（n）。（这里不作解释）这里将介绍下列几点： 1）素数判断，复杂度为O（√n）的原理及代码。 2）素数表的获取。 3）

水深无声/ 2022年04月24日 07:36/ 0 赞/ 205 阅读

相关算法：素数筛选

include <stdio.h> include <stdlib.h> int main(void) { //这个是输出1000以内的

Love The Way You Lie/ 2022年03月20日 15:58/ 0 赞/ 267 阅读

相关 java中大素数生成算法

目前的公开密钥算法大部分基于大整数分解、有限域上的离散对数问题和椭圆曲线上的离散对数问题，这些数学难题的构建大部分都需要生成一种超大的素数，尤其在经典的RSA算法中，生成

心已赠人/ 2022年02月22日 02:40/ 0 赞/ 179 阅读

相关素数算法3种

① \-------------------------------------------------------------------------- \--

末蓝、/ 2021年12月03日 07:37/ 0 赞/ 246 阅读

相关 HDU 6608 Fansblog——————大素数检测

[Fansblog][] 点击题目查看题面 [点击这里也可以][Fansblog] Source [2019 Multi-University Training C

冷不防/ 2021年11月16日 07:42/ 0 赞/ 227 阅读

相关素数筛选高效算法

用普通的筛法，1000 0000 的数，需要用时1600ms左右。 include <stdio.h> include <string.h> incl

妖狐艹你老母/ 2021年11月02日 14:32/ 0 赞/ 346 阅读