【网络安全】【密码学】【北京航空航天大学】实验三、数论基础（下）【C语言实现】

实验三、数论基础（下）

一、实验内容

1、中国剩余定理（Chinese Remainder Theorem）

（1）、算法原理

m1, m2, … mk 是一组两两互素的正整数，且 M = m1 · m2 · … · mk 为它们的乘积, 则如下的同余方程组：
x == a1 (mod m1)
x == a2 (mod m2)
…
x == ak (mod mk)
对于模M有唯一的解 x = (M · e1 · a1 / m1 + M · e2 · a2 / m2 + … + M · ek · ak / mk) (mod M)
其中 ei 满足 M / mi · ei == 1(mod mi)

（2）、算法流程

本算法的大致流程如下图所示：

（3）、算法的代码实现（C语言）

#include <stdio.h>

int reverse(int k, int m);  // 函数，返回k模m的逆元

int main()
{
	int i;
	int r;       // 方程组中的方程个数 （不能超过100）
	int b[100];  // 余数数组
	int m[100];  // 模数数组
	int mul = 1;
	int M[100];  // M数组
	int M1[100];  // M'数组
	int x = 0;  // 方程组的根
	
	//	printf("%d", reverse(3, 7));  // 一行测试代码
	printf("请输入方程的个数：");
	scanf_s("%d", &r);  // 选用安全的输入函数，避免可能的栈溢出（攻击）
	
	printf("请输入 %d 个余数，之间以空格分隔：", r);
	for(i = 0;i < r;i ++)
	{
		scanf("%d", &b[i]);
	}
	
	printf("请输入 %d 个模数，之间以空格分隔：", r);
	for(i = 0;i < r;i ++)
	{
		scanf("%d", &m[i]);
		mul *= m[i];
	}
	
	for(i = 0;i < r;i ++)
	{
		M[i] = mul / m[i];
	}
	
	for(i = 0;i < r;i ++)
	{
		M1[i] = reverse(M[i], m[i]);
	}
	
	for(i = 0;i < r;i ++)
	{
		x += M1[i] * M[i] * b[i];
	}
	
	x %= mul;
	
	printf("此同余方程组的解（模%d）是：", mul);
	printf("%d", x);
	
	return 0;
}

int reverse(int k, int m)
{
	int i;
	for(int i = 1;i < m;i ++)
	{
		if(k * i % m == 1)
		{
			return i;
		}
	}
	return -1;
}

（4）、算法测试

测试点1：

x == 1 (mod 4)
x == 2 (mod 5)
x == 3 (mod 7)

运行时截图：

解为 x == 17 (mod 140)

测试点2：

x == 7 (mod 23)
x == 9 (mod 28)
x == 16 (mod 33)

运行时截图：

解为 x == 19189 (mod 21252)

测试点3：

x == 23 (mod 283)
x == 28 (mod 102)
x == 33 (mod 35)

运行时截图：

解为 x == 43888 (mod 1010310)

2、素性检测算法（Miller-Rabin’s Test for Primality）

（1）、算法原理
根据费马小定理，设 p 是素数，a 为整数，且满足 (a, p) = 1, 则满足 a ^ (p - 1) = 1 (mod p), 以及二次探测定理：如果 p 是一个素数，且 0 < x < p, 且同余方程 x ^ 2 = 1 (mod p) 成立，那么 x = 1 或x = p - 1。米勒·拉宾 Miller-Rabin 素性检测算法是基于以上两个定理的随机化算法，用于判断一个整数是合数还是素数。

（2）、算法流程

本算法的大致流程如下图所示：

（3）、算法的代码实现（C语言）

#include <stdio.h>
#include <stdlib.h>

typedef long long unsigned LLU;
typedef int BOOL;

#define TRUE 1
#define FALSE 0

// 长整数快速模乘算法
LLU quickMult(LLU a, LLU b, LLU c)
{
    LLU result = 0;
    while(b > 0) 
	{
        if(b & 1)
            result = (result + a) % c;
        a = (a + a) % c;
        b >>= 1;
    }
    return result;
}

// 长整数快速幂取模算法
LLU quickPower(LLU a, LLU b, LLU c) 
{
    LLU result = 1;
    while(b > 0) 
	{
        if(b & 1)
            result = quickMult(result, a, c);
        a = quickMult(a, a, c);
        b >>= 1;
    }
    return result;
}



// 米勒·拉宾素性检验算法（单次测试）
BOOL MillerRabinPrimeTest(LLU n) 
{
    LLU d, x, newX, a = 1;
    int i;
    for (i = 0; i < 4; i ++)
        a *= rand();
    a = a % (n - 3) + 2;  // 随机地选取一个a∈[2,n-2]
    int s = 0;  // s为d中的因子2的幂次数。
    d = n - 1;
    while ((d & 1) == 0) 
	{   
		// 将d中的因子2全部提取出来。
        s ++;
        d >>= 1;
    }

    x = quickPower(a, d, n);
	for (i = 0; i < s; i ++) 
	{ // 进行s次二次探测
        newX = quickPower(x, 2, n);
        if (newX == 1 && x != 1 && x != n - 1)
            return FALSE;  // 用二次定理的逆否命题，此时n被确定为合数。
        x = newX; 
    }
	
    if (x != 1)
        return FALSE;  // 用费马小定理的逆否命题判断，此时x=a^(n-1) (mod n)，那么n确定为合数。

    return TRUE; //用费马小定理的逆命题判断。能经受住考验至此的数，大概率为素数。
}


//经过连续特定次数的Miller-Rabin测试后，
//如果返回值为TRUE表示n为素数，返回值为FALSE表示n为合数。
BOOL isPrimeByMR(LLU n) 
{
    if((n & 1) == 0)
        return FALSE;
    int i;
    for (i = 0; i < 100; i ++)
        if(MillerRabinPrimeTest(n) == FALSE)
            return FALSE;
    return TRUE;
}


// 主函数
int main()
{
    LLU n;
	
	printf("请输入待判断素性的整数：");
    scanf("%lld", &n);
	
    BOOL result;
    result = isPrimeByMR(n);
	
	printf("\n------判断中......------\n\n");
	
    if(result == TRUE)
        printf("%llu 是素数", n);
    else
        printf("%llu 是合数", n);
	
    return 0;
}

（4）、算法测试

测试点1：
判断1000023是素数还是合数。（答：合数）

运行时截图：

测试点2：
判断1000033是素数还是合数。（答：素数）

运行时截图：

测试点3：
判断100160063是素数还是合数。（答：合数）

运行时截图：

测试点4：
判断1500450271是素数还是合数。（答：素数）

运行时截图：

说明：算法为概率性判断，即可能将合数错判为素数（对计算机来说，已在极短的时间内完成了100次重复的MR测试，故该错判的概率极低），但绝无可能将素数错判为合数。

二、参考文献

1、《密码编码学与网络安全——原理与实践（第七版）》（Cryptography and Network Security, Principles and Practice, Seventh Edition），【美】威廉 斯托林斯 William Stallings 著，王后珍等 译，北京，电子工业出版社，2017年12月。

2、《密码学实验教程》，郭华 刘建伟等 主编，北京，电子工业出版社，2021年1月。