模板:(数论:大素数判定-分解: Miller-Rabin算法)

2024-06-14 03:18

本文主要是介绍模板:(数论:大素数判定-分解: Miller-Rabin算法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码如下:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;//****************************************************************
// Miller_Rabin 算法进行素数测试
//速度快,而且可以判断 <2^63的数
//****************************************************************
const int S=20;//随机算法判定次数,S越大,判错概率越小//计算 (a*b)%c.   a,b都是long long的数,直接相乘可能溢出的
//  a,b,c <2^63
LL mult_mod(LL a, LL b, LL c) {a %= c;b %= c;LL ret=0;while(b) {if(b&1) {ret += a;ret %= c;}a <<= 1;if(a >= c)a %= c;b >>= 1;}return ret;
}//计算  x^n %c
LL pow_mod(LL x, LL n, LL mod) {//x^n%cif(n==1)return x % mod;x %= mod;LL tmp=x;LL ret=1;while(n){if(n&1) ret=mult_mod(ret, tmp, mod);tmp = mult_mod(tmp, tmp, mod);n >>= 1;}return ret;
}//以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
//一定是合数返回true,不一定返回false
bool check(LL a, LL n, LL x, LL t){LL ret = pow_mod(a,x,n);LL last = ret;for(int i=1; i<=t; i++) {ret = mult_mod(ret, ret, n);if(ret==1 && last!=1 && last!=n-1) return true;//合数last = ret;}if(ret != 1) return true;return false;
}// Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数,但概率极小)
//合数返回false;bool Miller_Rabin(LL n){if(n < 2)return false;if(n == 2)return true;if((n&1) == 0) return false;//偶数LL x = n-1;LL t = 0;while((x&1) == 0) {x >>= 1;t++;}for(int i=0; i<S; i++){LL a = rand()%(n-1)+1;//rand()需要stdlib.h头文件if(check(a, n, x, t))return false;//合数}return true;
}//************************************************
//pollard_rho 算法进行质因数分解
//************************************************
LL factor[100];//质因数分解结果(刚返回时是无序的)
int tol;//质因数的个数。数组小标从0开始LL gcd(LL a,LL b) {if(a==0)return 1;//???????if(a<0) return gcd(-a,b);while(b){long long t=a%b;a=b;b=t;}return a;
}long long Pollard_rho(LL x, LL c) {LL i = 1,k = 2;LL x0 = rand() % x;LL y = x0;while(true){i++;x0 = (mult_mod(x0, x0, x) + c) % x;LL d=gcd(y-x0, x);if(d!=1 && d!=x) return d;if(y == x0) return x;if(i == k) {y = x0;k += k;}}
}
//对n进行素因子分解
void findfac(LL n)
{if(Miller_Rabin(n)) {//素数factor[tol++] = n;return;}LL p = n;while(p >= n)p=Pollard_rho(p, rand()%(n-1)+1);findfac(p);findfac(n/p);
}int main(){//srand(time(NULL));//需要time.h头文件//POJ上G++不能加这句话LL n;while(scanf("%I64d",&n) != EOF){tol = 0;findfac(n);for(int i=0; i<tol; i++)printf("%lld ", factor[i]);if(Miller_Rabin(n))printf("Yes\n");else printf("No\n");}return 0;
}

再附上一份简短的,如果对于比表小的数,用这个模板 比较好,上面的会超时不知道什么原因

bool witness(__int64 a,__int64 n)
{__int64 t,d,x;d=1;int i=ceil(log(n-1.0)/log(2.0)) - 1;for(;i>=0;i--){x=d;  d=(d*d)%n;if(d==1 && x!=1 && x!=n-1) return true;if( ((n-1) & (1<<i)) > 0)d=(d*a)%n;}return d==1? false : true;
}
bool miller_rabin(__int64 n)
{if(n==2)    return true;if(n==1 || ((n&1)==0))    return false;for(int i=0;i<50;i++){__int64 a=rand()*(n-2)/RAND_MAX +1;if(witness(a, n))    return false;}return true;
}


这篇关于模板:(数论:大素数判定-分解: Miller-Rabin算法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1059221

相关文章

Java如何根据word模板导出数据

《Java如何根据word模板导出数据》这篇文章主要为大家详细介绍了Java如何实现根据word模板导出数据,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... pom.XML文件导入依赖 <dependency> <groupId>cn.afterturn</groupId>

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Python中Flask模板的使用与高级技巧详解

《Python中Flask模板的使用与高级技巧详解》在Web开发中,直接将HTML代码写在Python文件中会导致诸多问题,Flask内置了Jinja2模板引擎,完美解决了这些问题,下面我们就来看看F... 目录一、模板渲染基础1.1 为什么需要模板引擎1.2 第一个模板渲染示例1.3 模板渲染原理二、模板

利用Python打造一个Excel记账模板

《利用Python打造一个Excel记账模板》这篇文章主要为大家详细介绍了如何使用Python打造一个超实用的Excel记账模板,可以帮助大家高效管理财务,迈向财富自由之路,感兴趣的小伙伴快跟随小编一... 目录设置预算百分比超支标红预警记账模板功能介绍基础记账预算管理可视化分析摸鱼时间理财法碎片时间利用财

如何在 Spring Boot 中实现 FreeMarker 模板

《如何在SpringBoot中实现FreeMarker模板》FreeMarker是一种功能强大、轻量级的模板引擎,用于在Java应用中生成动态文本输出(如HTML、XML、邮件内容等),本文... 目录什么是 FreeMarker 模板?在 Spring Boot 中实现 FreeMarker 模板1. 环

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.