实验二、数论基础(中)
一、实验内容
1、扩展欧几里得算法(Extended Euclid’s Algorithm)
(1)、算法原理
已知整数 a , b ,扩展的欧几里得算法可以在求得 a , b 的最大公约数的同时,找到一对整数 x , y ,使得 a , b , x , y 满足如下等式:ax + by = d = gcd(a,b), 其中 gcd(a, b) 为 a 和 b 的最大公约数。
(2)、算法流程
本算法的大致流程如下图所示:
(3)、 算法的代码实现(C语言)
# include <stdio.h>
int r2, s2, t2;
void Extended_Euclid(int a, int b);
int main(){
int a, b;
printf("请输入整数a:\n");
scanf("%d", &a);
printf("请输入整数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)、算法测试
测试点1:a = 7, b = 5
测试点2:a = 31, b = -13
测试点3:a = 24, b = 36
(5)、一点思考
线性系数x和y不是唯一的,比如样例3中既可以是24 * (-1) + 36 * 1 = 12,也可以是24 * 2 + 36 * (-1) = 12. 如何能使算法找出所有满足条件的解?
2、简单幂取模算法(Simple Exponentiation-Module Algorithm)
(1)、算法原理
每次做乘法操作时都取模,即“乘一次模一次,循环往复”。数学表达式为 d = (((x^(n-1))mod m)*x) mod m
(2)、算法流程
本算法的大致流程如下图所示:
(3)、算法的代码实现(C语言)
#include <stdio.h>
int main(){
int x, n, m;
int ans;
int i;
printf("请输入底数x的值:\n");
scanf_s("%d", &x);
printf("请输入指数n的值:\n");
scanf_s("%d", &n);
printf("请输入模数m的值:\n");
scanf_s("%d", &m);
ans = 1;
for(i = 1;i <= n;i ++)
{
ans = (ans * x) % m;
}
printf("%d", ans);
return 0;
}
(4)、算法测试
测试点1:x = 7, n = 16, m = 3
运行时截图:
测试点2:x = 5, n = 1003, m = 31
运行时截图:
2、快速幂取模算法(Fast Exponentiation-Module Algorithm)
(1)、算法原理
常规的幂取模算法包含过多的乘法以及取模运算,计算步骤多,导致算法的效率很低。根据模运算和幂运算的性质,可以将幂次(指数n)用2进制进行表示,然后再迭代进行求模幂,从而减少乘法和取模的次数。
(2)、算法流程
本算法的大致流程如下图所示:
(3)、算法的代码实现(C语言)
#include <stdio.h>
int main()
{
int x, n, m;
int d = 1;
printf("请输入底数x的值:\n");
scanf_s("%d", &x);
printf("请输入指数n的值:\n");
scanf_s("%d", &n);
printf("请输入模数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("快速幂取模计算结果:\n");
printf("%d", d);
return 0;
}
(4)、算法测试
测试点1:x = 7, n = 16, m = 3
运行时截图:
测试点2:x = 5, n = 1003, m = 31
运行时截图:
二、参考文献
1、《密码编码学与网络安全——原理与实践(第七版)》(Cryptography and Network Security, Principles and Practice, Seventh Edition),【美】威廉 斯托林斯 William Stallings 著,王后珍等 译,北京,电子工业出版社,2017年12月。文章来源:https://www.toymoban.com/news/detail-789931.html
2、《密码学实验教程》,郭华 刘建伟等 主编,北京,电子工业出版社,2021年1月。文章来源地址https://www.toymoban.com/news/detail-789931.html
到了这里,关于【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!