實驗三、數(shù)論基礎(chǔ)（下）
一、實驗內(nèi)容
1、中國剩余定理（Chinese Remainder Theorem）
（1）、算法原理
m1, m2, … mk 是一組兩兩互素的正整數(shù)，且 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）、算法的代碼實現(xiàn)（C語言）
#include <stdio.h>
int reverse(int k, int m); // 函數(shù)，返回k模m的逆元
int main()
{
int i;
int r; // 方程組中的方程個數(shù) （不能超過100）
int b[100]; // 余數(shù)數(shù)組
int m[100]; // 模數(shù)數(shù)組
int mul = 1;
int M[100]; // M數(shù)組
int M1[100]; // M'數(shù)組
int x = 0; // 方程組的根
// printf("%d", reverse(3, 7)); // 一行測試代碼
printf("請輸入方程的個數(shù)：");
scanf_s("%d", &r); // 選用安全的輸入函數(shù)，避免可能的棧溢出（攻擊）
printf("請輸入 %d 個余數(shù)，之間以空格分隔：", r);
for(i = 0;i < r;i ++)
{
scanf("%d", &b[i]);
}
printf("請輸入 %d 個模數(shù)，之間以空格分隔：", 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)
運(yùn)行時截圖：
解為 x == 17 (mod 140)
測試點2：
x == 7 (mod 23)
x == 9 (mod 28)
x == 16 (mod 33)
運(yùn)行時截圖：
解為 x == 19189 (mod 21252)
測試點3：
x == 23 (mod 283)
x == 28 (mod 102)
x == 33 (mod 35)
運(yùn)行時截圖：
解為 x == 43888 (mod 1010310)
2、素性檢測算法（Miller-Rabin’s Test for Primality）
（1）、算法原理
根據(jù)費(fèi)馬小定理，設(shè) p 是素數(shù)，a 為整數(shù)，且滿足 (a, p) = 1, 則滿足 a ^ (p - 1) = 1 (mod p), 以及二次探測定理：如果 p 是一個素數(shù)，且 0 < x < p, 且同余方程 x ^ 2 = 1 (mod p) 成立，那么 x = 1 或x = p - 1。米勒·拉賓 Miller-Rabin 素性檢測算法是基于以上兩個定理的隨機(jī)化算法，用于判斷一個整數(shù)是合數(shù)還是素數(shù)。
（2）、算法流程
本算法的大致流程如下圖所示：
（3）、算法的代碼實現(xiàn)（C語言）
#include <stdio.h>
#include <stdlib.h>
typedef long long unsigned LLU;
typedef int BOOL;
#define TRUE 1
#define FALSE 0
// 長整數(shù)快速模乘算法
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;
}
// 長整數(shù)快速冪取模算法
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; // 隨機(jī)地選取一個a∈[2,n-2]
int s = 0; // s為d中的因子2的冪次數(shù)。
d = n - 1;
while ((d & 1) == 0)
{
// 將d中的因子2全部提取出來。
s ++;
d >>= 1;
}
x = quickPower(a, d, n);
for (i = 0; i < s; i ++)
{ // 進(jìn)行s次二次探測
newX = quickPower(x, 2, n);
if (newX == 1 && x != 1 && x != n - 1)
return FALSE; // 用二次定理的逆否命題，此時n被確定為合數(shù)。
x = newX;
}
if (x != 1)
return FALSE; // 用費(fèi)馬小定理的逆否命題判斷，此時x=a^(n-1) (mod n)，那么n確定為合數(shù)。
return TRUE; //用費(fèi)馬小定理的逆命題判斷。能經(jīng)受住考驗至此的數(shù)，大概率為素數(shù)。
}
//經(jīng)過連續(xù)特定次數(shù)的Miller-Rabin測試后，
//如果返回值為TRUE表示n為素數(shù)，返回值為FALSE表示n為合數(shù)。
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;
}
// 主函數(shù)
int main()
{
LLU n;
printf("請輸入待判斷素性的整數(shù)：");
scanf("%lld", &n);
BOOL result;
result = isPrimeByMR(n);
printf("\n------判斷中......------\n\n");
if(result == TRUE)
printf("%llu 是素數(shù)", n);
else
printf("%llu 是合數(shù)", n);
return 0;
}
（4）、算法測試
測試點1：
判斷1000023是素數(shù)還是合數(shù)。（答：合數(shù)）
運(yùn)行時截圖：
測試點2：
判斷1000033是素數(shù)還是合數(shù)。（答：素數(shù)）
運(yùn)行時截圖：
測試點3：
判斷100160063是素數(shù)還是合數(shù)。（答：合數(shù)）
運(yùn)行時截圖：
測試點4：
判斷1500450271是素數(shù)還是合數(shù)。（答：素數(shù)）
運(yùn)行時截圖：
說明：算法為概率性判斷，即可能將合數(shù)錯判為素數(shù)（對計算機(jī)來說，已在極短的時間內(nèi)完成了100次重復(fù)的MR測試，故該錯判的概率極低），但絕無可能將素數(shù)錯判為合數(shù)。
二、參考文獻(xiàn)
1、《密碼編碼學(xué)與網(wǎng)絡(luò)安全——原理與實踐（第七版）》（Cryptography and Network Security, Principles and Practice, Seventh Edition），【美】威廉 斯托林斯 William Stallings 著，王后珍等 譯，北京，電子工業(yè)出版社，2017年12月。文章來源：http://www.zghlxwxcb.cn/news/detail-785407.html
2、《密碼學(xué)實驗教程》，郭華 劉建偉等 主編，北京，電子工業(yè)出版社，2021年1月。文章來源地址http://www.zghlxwxcb.cn/news/detail-785407.html
到了這里，關(guān)于【網(wǎng)絡(luò)安全】【密碼學(xué)】【北京航空航天大學(xué)】實驗三、數(shù)論基礎(chǔ)（下）【C語言實現(xiàn)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
