说明

1、语言：C语言

2、环境：VS2019

随机素数（指定范围）生成器

#define _CRT_SECURE_NO_WARNINGS
#include  
#include  
#include 
#define randomInt(a,b) (rand()%(b-a)+a)
int prime(int n)
{
	int i;
	if (n < 2) {
		return -1;
	}
	else {
		for (i = 2; i < n; i++) {//判断n在2~n-1中有没有因数
			if (n % i == 0)//如果用可以除尽的数,则非素数
				break;
		}
		if (i < n) {//存在2~n-1之间有因数
			return -1;
		}
		else
			return 0;
	}
	return 0;
}

int main()
{
	int  k,res,a,b;
	printf("-------------素数生成器--------------\n");
	printf("           输入范围：[a,b)\n");
	printf("-------------------------------------\n");
	int ntime = 20;
	while (ntime > 0)
	{
		scanf("%d %d", &a, &b);
		srand((unsigned)time(NULL));
		do
		{
			res = randomInt(a, b);
			k = prime(res);
		} while (k == -1);
		printf("素数：%d\n", res);
		ntime--;
		printf("还有%d次！\n",ntime - 1);
	}
	system("pause");
	return 0;
}

求逆元

基于扩展欧几里得算法

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 

int exgcd(int a, int b, int& x, int& y)//扩展欧几里得算法
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int ret = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return ret;
}
int getInv(int a, int mod)//求a在mod下的逆元，不存在逆元返回-1
{
    int x, y;
    int d = exgcd(a, mod, x, y);
    return d == 1 ? (x % mod + mod) % mod : -1;
}
int main() {
    int m, n;
    puts("          扩展欧几里得求逆元\n");
    puts("       对m * x = 1 mod n，求x\n");
    printf("请输入m=");
    scanf("%d", &m);
    printf("请输入n=");
    scanf("%d", &n);
    printf("x=%d\n", getInv(m, n));
    system("pause");
    return 0;
}

基于费马定理算法

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 

int main()
{
	int m, n, x;
    puts("          基于费马定理求逆元\n");
    puts("       对m * x = 1 mod n，求x\n");
    printf("请输入m=");
    scanf("%d", &m);
    printf("请输入n=");
    scanf("%d", &n);
	x = (int)pow(m, n - 2) % n;
	printf("x=%d\n", x);
	system("pause");
	return 0;
}

计算时间差

引入头文件：

#include 

给出定义变量：

time_t begin, end;

前后分别写：

begin = clock();

....

end = clock();

printf("\n\t\t\t加密时间: %f seconds\n", (double)(end - begin) / CLOCKS_PER_SEC);

ElGamal算法中素数的生成元

使用大数库“miracl”

#include
#include
#include "miracl.h"
#include 
time_t begin, end;
int main()
{
	int MAX_D=0;
	miracl* mip = mirsys(MAX_D + 10, 10);
	big p = mirvar(0);
	big p_1 = mirvar(0);//p-1
	big p_2 = mirvar(0);//p-2
	big q = mirvar(0);
	big g = mirvar(0);

	big flag = mirvar(0);//中间变量
	big one = mirvar(1);//常量1

	printf("----------------------------\n\n");
	printf("        素数生成元\n\n");
	printf("----------------------------\n\n");
	printf("请输入生成素数的位数：");
	scanf("%d", &MAX_D);
	//密钥生成部分
	{
		irand((unsigned)time(NULL)); // 使用当前时间作为随机数种子 
		//随机生成一个安全素数p
		bigdig(MAX_D, 10, q);//生成一个150位的随机数
		nxsafeprime(0, 0, q, p);//生成一个比q大的安全素数p
		copy(p, q);
		decr(q, 1, q);
		subdiv(q, 2, q);//生成q=(p-1)/2
		decr(p, 1, p_1);//生成p_1=p-1
		decr(p, 2, p_2);//生成p_2=p-2
		//寻找一个本原根
		//irand((unsigned)time(NULL)); // 使用当前时间作为随机数种子 
		while (1)
		{
			bigrand(p_1, g);//g小于p-1
			if (compare(g, one) <= 0)//保证g大于1
				continue;
			powmod(g, mirvar(2), p, flag);
			if (compare(flag, one) != 0)
			{
				powmod(g, q, p, flag);
				if (compare(flag, one) != 0)
				{
					multiply(q, mirvar(2), flag);
					powmod(g, flag, p, flag);
					if (compare(flag, one) == 0)
						break;
				}

			}
		}//end
		printf("p = ");
		cotnum(p, stdout);
		printf("g = ");
		cotnum(g, stdout);
	}
	mirexit();
	system("pause");
	return 0;
}

将字符串转为整数

在将字符串转十进制的过程中，若是较长的字符串，转的十进制比较大，下面按照如下公式，进行转换：

#include   
#include   
#include   
#include   
#define pow_2(n) (1< 'F' && ch < 'a') || ch > 'z' )  
                return -1;  
  
        // 如果是大写字母，则用数字的ASCII码减去55, 如果ch = 'A' ,则 'A' - 55 = 10  
        // 如果是小写字母，则用数字的ASCII码减去87, 如果ch = 'a' ,则 'a' - 87 = 10  
        if(isalpha(ch))  
                return isupper(ch) ? ch - 55 : ch - 87;  
  
        return -1;  
}  
  
/* 
 * 功能：将十六进制字符串转换为整型(int)数值 
 * */  
int hex2dec(char *hex)  
{  
        int len;  
        int num = 0;  
        int temp;  
        int bits;  
        int i;  
          
        // 此例中 hex = "1de" 长度为3, hex是main函数传递的  
        len = strlen(hex);  
  
        for (i=0, temp=0; i

生成随机数

#include 
#include 
/*
    生成随机数
    取得[0,x)的随机整数：rand()%x；
    取得[0,x]的随机整数：rand()%(x+1)；
    取得[a,b)的随机整数：rand()%(b-a)+a；
    取得(a,b]的随机整数：rand()%(b-a)+a+1；
    取得[a,b]的随机整数：rand()%(b-a+1)+a；
    取得0-1之间的浮点数：rand()/double(RAND_MAX)
*/

int rand_n(int p)
{ 
    return rand()%p;
}
int main()
{
    int i=0;
    srand((unsigned)time(0));
	for(i;i<5;i++)
    {
        printf("%d\n",rand_n(5));
    }
    system("pause");
    return 0;
}