Fermat素性检验算法
一、实验目的
在前面的四次小实验中，对我们的考察难度不是很大，四个小实验对我们提出来的要求是，通过完成验证四个定理的过程，让我们能够相比较才学习信息安全数学基础与现代密码学时，能更加详细的了解关于这四个定理的内容。第一次的实验是使用Fermat素性检验算法（这是一个概率性算法），来判断从文本文件中输入进去的大整数是不是一个素数。在平时我们接触到的C语言结构中，最大的表示数值是unsigned int型数据，其最大可以表示数据，也就是八个字节的大小，即使是这样，对于我们信息安全实验来说，这样的数据类型长度是远远不够的。在实验中，我们需要用到miracl函数库，它定义了两种新的数据类型——表示大整数的big类型和表示有理数的flash（short for floating-slash）类型。通过本次实验，可以让我们熟悉miracl库中的一些基本操作函数，将Fermat素性检验算法在实验中展示出来。
二、方案设计（算法流程图）
三、主要函数的介绍
3.2.1 mirsys()
函数原型: miracl *mirsys(int nd, int nb);
功能说明: 初始化当前程序线程的MIRACL系统，如下所述,必须在尝试使用任何其他MIRACL例程之前调用:
（1）初始化错误跟踪机制。
（2）从nd和nb计算用于每个大/闪存号的计算机字数。
（3）初始化了16个大的工作变量（其中4个为双倍长度）。
（4）某些实例变量被赋予默认初始值。
（5）通过调用irand（0L）启动随机数发生器。
这个函数的返回值是是一个miracl实例指针，通过它可以访问所有实例变量，如果没有足够的内存来创建实例，则为NULL。
操作实例是miracl *mip=mirsys(500,10)，意思是我定义的这些变量最大长度都是500位（这个位是后面进制的位数），输入、输出、运算用的进制都是10进制。
3.2.2 实例变量IOBASE
IOBASE是用于控制输入和输出的进制问题的，可以在程序中随意更改， 必须大于或等于2且小于或等于256。使用实例是像这样的：mip->IOBASE=16，这样子输入的变量和输出的变量所使用的进制都是十六进制。
3.2.3 mirvar()
函数原型：flash mirvar(iv)
功能说明：通过为其保留适当数量的内存位置来初始化大/闪存变量，可以通过对函数mirkill()的后续调用来释放该存储器。并且在程序中，每个big型变量都必须赋初始值，否则会出错。
3.2.4 decr()
函数原型：void decr(x,n,z)
big x,z;
int n;
这个函数实现的功能是对一个big型的变量x减去一个int型的值后得出的big型数据，例如我们在Fermat素性检验算法中，产生的随机数范围在2至m-2中，如果我们需要得出m-2的话，有两种途径：第一，如果将减去的2视作为int类型的话，直接相减是不可行的，相当于是big型减去int型，需要用到这个函数，即decr(m,2,y),返回的结果是big y=m-2；第二，如果将2作为大数来看待的话，就需要先用negify()函数取2的复数，再使用add()函数得到m-2的结果。
3.2.5 bigrand()&bigdig()
函数原型: void bigrand(big w, big x);
功能说明: 使用内置的随机数发生器，产生一个小于w的大数随机数，x<w
函数原型: void bigdig(int n, int b, big x);
功能说明: 产生一个指定长度的进制的随机数，该函数使用内置的随机数发生器，初始化种子调用irand函数。
这两个函数都是可以生成随机数的，但是它们的功能确实略有差异的。bigrand()是产生一个小于w的大数随机数，x<w，如果w是一个十位的十进制数，那么x可能是一个十位的十进制数，只有九位的十进制数，也可能使只有一位的十进制数；bigdig()是产生一个指定长度的进制的随机数，比如说指定了产生一个十位的十进制数，那么这个函数就会严格的产生一个十位的十进制数。
3.2.6 compare()
函数原型: int compare(big x, big y);
功能说明: 比较两个大数的大小。
返回值: x>y时返回+1, x=y时返回0, x<y时返回-1。在这里需要注意的是，compare()函数比较的是两个big类型的数，此函数的返回值是int型的+1和-1。
3.2.7 egcd()
函数原型: int egcd(bigx, big y, big z);
功能说明:计算两个大数的最大公约数，z=gcd(x,y)。
3.2.8 powmod()
函数原型: void powmod(big x, big y,big z, big w);
功能说明: 模幂运算，。
3.2.9 mirkill()
函数原型：void mirkill(x) big x;
功能说明：通过将其归零并释放其内存来安全地杀死大/闪存数字。
3.2.10 mirexit()
函数原型: void mirexit();
功能说明: 清除MIRACL系统，释放所有内部变量。
四、算法实现的主要代码
#include "miracl.h"
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define round 6
int Fermatjdu_prime(big obj);
main()
{
FILE *fp;
big obj;
miracl *mip = mirsys(1500, 16);//定义的这些变量最大长度都是5000位（这个位是后面进制的位数），输入、输出、运算用的进制都是16进制。
mip->IOBASE = 16;
obj=mirvar(0); //初始化变量obj，obj是输入的需要判断是否为素数的大数
if((fp=fopen("data.txt","r+"))==NULL){
printf("Open the file failure...\n");
exit(0);
} //判断文件是否能够正确打开
while(!feof(fp)){ //检测文件结束符
cinnum(obj, fp); //从文件中读取一个数字进入，并将其强制转化为十六进制表的大数obj
cotnum(obj, stdout); //向屏幕上输出一个大数obj
if (Fermatjdu_prime(obj))
printf("This number has a %6.4f%% probability of being a prime number.\n", 100 * (1 - pow(0.5, round)));
else
printf("This number is 100%% definitely a Composite number! \n");
}
fclose(fp);
mirkill(obj); //释放大数obj所占用的空间
mirexit(); //清楚miracl系统
}
int Fermatjdu_prime(big obj)
{
big radn,trans,mgcd,trans1,r,num1,num2,cons;
int i,j;
miracl *mip = mirsys(1500, 16);
mip->IOBASE=16;
radn=mirvar(0);//对函数中使用到的big型变量进行初始化
trans=mirvar(0);
mgcd=mirvar(0);
trans1=mirvar(0);
r=mirvar(0);
num1=mirvar(1);
num2=mirvar(2);
cons=mirvar(0);
i=0;
j=0;
decr(obj,2,trans); //trans=obj-2
decr(obj,1,trans1); //trans=obj-1
srand((unsigned int)time(NULL));
for(i=0;i<round;i++)
{
bigrand(obj,radn); //生成所需要的随机数
egcd(radn,obj,mgcd); //计算obj和生成的随机数的最大公因数
if(!compare(mgcd,num1)) //判断obj和随机数是否互素，它们的最大公因数如果不是1的话， compare函数将会返回1，不满足条件
{
powmod(radn,trans1,obj,r); //计算 ，如果r=1，则obj可能是素数，进入下一个if语句
if(!compare(r,num1)) j++ //j是判断因子，如果一个数能够满足在当前的轮数下，满足上述的算法，则j能够计数；如果j不等于轮数，那么这个数就不是素数;
}
}
if(j==round)
return 1;
else
return 0;
mirkill(obj);
mirkill(radn);
mirkill(trans);
mirkill(trans1);
mirkill(r);
mirkill(mgcd);
}
最后说明环境配置问题：
编译miracl.lib文件和在VS2017中调用miracl库。网址链接分别是：