素数随机判定(miller_rabin)代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】素数随机判定(miller_rabin)

作者:雅玉 / 发布于2016/2/23/ 543

//miller rabin
//判断自然数n是否为素数
//time越高失败概率越低,一般取10到50
#include <stdlib.h>
#ifdef WIN32
typedef __int64 i64;
#else
typedef long long i64;
#endif

int modular_exponent(int a,int b,int n){ //a^b mod n
	int ret;
	for (;b;b>>=1,a=(int)((i64)a)*a%n)
		if (b&1)
			ret=(int)((i64)ret)*a%n;
	return ret;
}

// Carmicheal number: 561,41041,825265,321197185
int miller_rabin(int n,int time=10){
	if (n==1||(n!=2&&!(n%2))||(n!=3&&!(n%3))||(n!=5&&!(n%5))||(n!=7&&!(n%7)))
		return 0;
	while (time--)
		if (modular_exponent(((rand()&0x7fff<<16)+rand()&0x7fff+rand()&0x7fff)%(n-1)+1,n-1,n)!=1)
			return 0;
	return 1;
}

试试其它关键字

　素数　　随机判定　

同语言下

.C分鱼问题
.链表
.最大连续和
.编码字符串
.libiconv字符编码处理及判断字符串是否为utf8
.一组数中两两二元组，差最大有几对，差最小呢？（数组
.通过管道获取一个进程的执行状态
.多关键字排序
.字符串字典序排序
.3元一次方程(牛顿迭代法求方程的根)

可能有用的

.C#实现的html内容截取
.List 切割成几份工具类
.SQL查询多列合并成一行用逗号隔开
.一行一行读取txt的内容
.C#动态修改文件夹名称(FSO实现，不移动文件)
.c# 移动文件或文件夹
.c#图片添加水印
.Java PDF转换成图片并输出给前台展示
.网站后台修改图片尺寸代码
.处理大图片在缩略图时的展示

雅玉贡献的其它代码(8)

.POM.XML文件常用标签
.读取Excel并转化为List
.属性配置文件工具类
.汉字转化为拼音类
.FormBuilder 设置金额显示格式
.欧拉回路(邻接阵形式)
.获取每个文件的名称和大小.py
.素数随机判定(miller_rabin)