Fermat素性检测算法试验的实现

Fermat素性检测算法试验的实现

一.试验目的

在本篇文章中，使用密码学试验专用的miracl库，实现素性检测算法。

二.试验工具

1.VMware 虚拟机 windows7 系统。 2.Microsoft Visual C++ 6.0。 3.Miracl_5.5.4 函数库。

三.试验原理 3.1 fermat 小定理

给定素数p、整数a，则满足：

3.2 推论

我们可以得出结论：素数一定满足fermat小定理。 从而可以得到判定素数m的一类方法： （1）如果有一个整数a，满足a、m互素，但是不满足fermat定理。则这个数 一定为合数。 （2）如果有一个整数a，满足a、m互素，并且满足fermat定理。则这个数 可能为素数。 如果使用韦恩图表示，则：

四.试验环境的配置 4.1 VMware win7的安装

1.[VMware 下载地址](https://my.vmware.com/cn/web/vmware/downloads/info/slug/desktop_end_user_computing/vmware_workstation_pro/16_0) 2.[Win7 镜像下载地址](http://www.win7zhijia.cn/jiaocheng/win7_23964.html) 3.[安装教程](https://jingyan.baidu.com/article/335530da65b1be59ca41c36e.html)

4.2 Microsoft Visual C++ 6.0的安装

[软件安装管家 VC6](https://mp.weixin.qq.com/s?__biz=MzIwMjE1MjMyMw==&mid=502712680&idx=1&sn=b835b4e2496712712784004427f1f4b2&chksm=0ee169843996e0920669a8c2e1ea4122a3cf9a11a11f3a1c01dc4c39623b2910108ffd88be21&xtrack=1&scene=0&subscene=10000&clicktime=1601717943&enterid=1601717943&ascene=7&devicetype=android-29&version=27001337&nettype=WIFI&abtest_cookie=AAACAA==&lang=zh_CN&exportkey=A+FS3hZw2xpbLF5DY4UrecI=&pass_ticket=3QBHSn5gJs6AkFMwrBG6W3CqwX+UZJ5Nfo5qr0Ua/nTjsq89lymBZLI2vkdi0FW1&wx_header=1)

4.3 Miracl.5.5.4的配置

step1:下载安装包。下载地址：https://download.csdn.net/download/foxlfj/12639579?ops_request_misc=%7B%22request%5Fid%22%3A%22160171816719725222458102%22%2C%22scm%22%3A%2220140713.130102334.pc%5Fall.%22%7D&request_id=160171816719725222458102&biz_id=1&utm_medium=distribute.pc_search_result.none-task-download-2~all~first_rank_v2~rank_v28-1-12639579.pc_first_rank_v2_rank_v28&utm_term=miracl5.5.4+32位版本&spm=1018.2118.3001.4187 step2:将miracl.5.5.4安装包里所有的文件（记住：是所有的文件，不是文 件夹！！）放入到一个文件夹中。 step3:找到 ms32doit 批处理文件并点击运行，会生成miracl.lib。 step4:打开VC6，打开工具栏—>选项—>目录—>include files step5:在其中添加路径，路径为：miracl安装包下的include文件夹位置。 step6:点击工程—>设置—>连接—>分类：常规—>对象/库模块中添加：miracl.lib step7:紧接着，分类：输入—>附加库路径中，添加miracl.lib文件的所在位置。

五.miracl库所用函数

（1）miracl* mirsys(int nd,int nb)

说明：初始化miracl系统，必须在调用Miracl库前执行 用法：miracl *mip=mirsys(30,10);//初始化30位10进制数

（2）mirvar(int x)

说明：初始化大数 用法：temp=mirvar(0);//将大数temp初始值设置为0

（3）cinstr(big x,char* str)

说明：将字符串转化为大数 用法：cinstr(temp,str);//将字符串str转化为大数temp

（4）compare(big x,big y)

说明：比较两个大数的大小 用法：如果x>y，返回1；如果x=y，返回0；如果x<y，返回-1

（5）subdivisible(big x,int n)

说明：测试n能否整除x 用法：如果n能整出x，返回true;否则，返回false

（6）decr(big x,int n,big z)

说明：一个big大数减一个int整数 用法：z=x-n

（7）egcd(big x,big y,big z)

说明：计算两个大数的最大公因数 用法：z=gcd(x,y)

（8）powmod(big x,big y,big z,big w)

说明：模幂运算 用法：w=x^y (mod z)

六.算法流程图 七.实现代码

extern "C" { #include "miracl.h" } #include<stdio.h> #include<math.h> #include<string.h> int main(){ big m,temp1,temp2,a,temp3,g,temp4,r,temp5; char str[200]={0}; int k,i; miracl *mip=mirsys(30,10); m=mirvar(0); temp1=mirvar(3); temp2=mirvar(2); a=mirvar(0); temp3=mirvar(0); g=mirvar(0); temp4=mirvar(0); r=mirvar(0); temp5=mirvar(1); printf("**********欢迎来到fermat素性检测程序！**********\n"); //输入符合条件的m printf("要输入的奇整数m为:"); gets(str); cinstr(m,str); if(compare(m,temp1)!=1||subdivisible(m,2)){ printf("输入的m不符合条件\n"); printf("**********程序结束**********"); return 0; } decr(m,2,temp3);//生成m-2 decr(m,1,temp4);//生成m-1 //输入安全参数k printf("请输入安全参数k:"); scanf("%d",&k); for(i=0;i<k;i++){ //随机选取满足条件的a while(1){ bigrand(temp4,a); if(compare(a,temp2)!=(-1)&&compare(temp3,a)!=(-1))break; } //判断最大公约数是否为1 egcd(a,m,g); if(compare(g,temp5)!=0){ printf("m为合数\n"); printf("**********程序结束**********");break; } //判断r是否为1 powmod(a,temp4,m,r); if(compare(r,temp5)!=0){ printf("m为合数\n");printf("**********程序结束**********"); break; } } if(i==k){ printf("m可能为素数的概率为:%.2f%%\n",(1.0-1.0/float(pow(2,k)))*100); printf("**********程序结束**********"); } } 注意：miracl为C的库，引入时使用： extern "C"{ #include "miracl.h" }

八.试验结果