實(shí)驗(yàn)二、數(shù)論基礎(chǔ)（中）
一、實(shí)驗(yàn)內(nèi)容
1、擴(kuò)展歐幾里得算法（Extended Euclid’s Algorithm）
（1）、算法原理
已知整數(shù) a , b ,擴(kuò)展的歐幾里得算法可以在求得 a , b 的最大公約數(shù)的同時(shí)，找到一對(duì)整數(shù) x , y ,使得 a , b , x , y 滿足如下等式：ax + by = d = gcd(a,b)， 其中 gcd(a, b) 為 a 和 b 的最大公約數(shù)。
（2）、算法流程
本算法的大致流程如下圖所示：
（3）、 算法的代碼實(shí)現(xiàn)（C語(yǔ)言）
# include <stdio.h>
int r2, s2, t2;
void Extended_Euclid(int a, int b);
int main(){
int a, b;
printf("請(qǐng)輸入整數(shù)a:\n");
scanf("%d", &a);
printf("請(qǐng)輸入整數(shù)b:\n");
scanf("%d", &b);
Extended_Euclid(a, b);
printf("a和b的最大公因子為: %d\n", r2);
printf("滿足ax + by = gcd(a, b)的因子x和y分別為: %d %d\n", s2, t2);
return 0;
}
void Extended_Euclid(int a, int b){
int r, s, t;
int r1, s1, t1;
int tmp1, tmp2, tmp3;
int q;
r = a;
s = 1;
t = 0;
r1 = b;
s1 = 0;
t1 = 1;
while(r1 != 0){
q = r / r1;
tmp1 = r - q * r1;
tmp2 = s - q * s1;
tmp3 = t - q * t1;
r = r1;
s = s1;
t = t1;
r1 = tmp1;
s1 = tmp2;
t1 = tmp3;
}
r2 = r;
s2 = s;
t2 = t;
return;
}
（4）、算法測(cè)試
測(cè)試點(diǎn)1：a = 7, b = 5
測(cè)試點(diǎn)2：a = 31, b = -13
測(cè)試點(diǎn)3：a = 24, b = 36
（5）、一點(diǎn)思考
線性系數(shù)x和y不是唯一的，比如樣例3中既可以是24 * (-1) + 36 * 1 = 12,也可以是24 * 2 + 36 * (-1) = 12. 如何能使算法找出所有滿足條件的解？
2、簡(jiǎn)單冪取模算法（Simple Exponentiation-Module Algorithm）
（1）、算法原理
每次做乘法操作時(shí)都取模，即“乘一次模一次，循環(huán)往復(fù)”。數(shù)學(xué)表達(dá)式為 d = (((x^(n-1))mod m)*x) mod m
（2）、算法流程
本算法的大致流程如下圖所示：
（3）、算法的代碼實(shí)現(xiàn)（C語(yǔ)言）
#include <stdio.h>
int main(){
int x, n, m;
int ans;
int i;
printf("請(qǐng)輸入底數(shù)x的值：\n");
scanf_s("%d", &x);
printf("請(qǐng)輸入指數(shù)n的值：\n");
scanf_s("%d", &n);
printf("請(qǐng)輸入模數(shù)m的值：\n");
scanf_s("%d", &m);
ans = 1;
for(i = 1;i <= n;i ++)
{
ans = (ans * x) % m;
}
printf("%d", ans);
return 0;
}
（4）、算法測(cè)試
測(cè)試點(diǎn)1：x = 7, n = 16, m = 3
運(yùn)行時(shí)截圖：
測(cè)試點(diǎn)2：x = 5, n = 1003, m = 31
運(yùn)行時(shí)截圖：
2、快速冪取模算法（Fast Exponentiation-Module Algorithm）
（1）、算法原理
常規(guī)的冪取模算法包含過(guò)多的乘法以及取模運(yùn)算，計(jì)算步驟多，導(dǎo)致算法的效率很低。根據(jù)模運(yùn)算和冪運(yùn)算的性質(zhì)，可以將冪次（指數(shù)n）用2進(jìn)制進(jìn)行表示，然后再迭代進(jìn)行求模冪，從而減少乘法和取模的次數(shù)。
（2）、算法流程
本算法的大致流程如下圖所示：
（3）、算法的代碼實(shí)現(xiàn)（C語(yǔ)言）
#include <stdio.h>
int main()
{
int x, n, m;
int d = 1;
printf("請(qǐng)輸入底數(shù)x的值：\n");
scanf_s("%d", &x);
printf("請(qǐng)輸入指數(shù)n的值：\n");
scanf_s("%d", &n);
printf("請(qǐng)輸入模數(shù)m的值：\n");
scanf_s("%d", &m);
while(n > 0)
{
if((n % 2) == 1)
{
d = (d * x) % m;
n = (n - 1) / 2;
}
else
{
n = n / 2;
}
x = (x * x) % m;
}
printf("快速冪取模計(jì)算結(jié)果：\n");
printf("%d", d);
return 0;
}
（4）、算法測(cè)試
測(cè)試點(diǎn)1：x = 7, n = 16, m = 3
運(yùn)行時(shí)截圖：
測(cè)試點(diǎn)2：x = 5, n = 1003, m = 31
運(yùn)行時(shí)截圖：
二、參考文獻(xiàn)
1、《密碼編碼學(xué)與網(wǎng)絡(luò)安全——原理與實(shí)踐（第七版）》（Cryptography and Network Security, Principles and Practice, Seventh Edition），【美】威廉 斯托林斯 William Stallings 著，王后珍等 譯，北京，電子工業(yè)出版社，2017年12月。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-789931.html
2、《密碼學(xué)實(shí)驗(yàn)教程》，郭華 劉建偉等 主編，北京，電子工業(yè)出版社，2021年1月。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-789931.html
到了這里，關(guān)于【網(wǎng)絡(luò)安全】【密碼學(xué)】【北京航空航天大學(xué)】實(shí)驗(yàn)二、數(shù)論基礎(chǔ)（中）【C語(yǔ)言和Java實(shí)現(xiàn)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
