实验三、数论基础（下）
一、实验内容
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月。
