首页 > 分享 > 密码学学习之旅

密码学学习之旅

花匠小妙招
2024-12-04 02:13

在用欧几里得算法以前先得说说整除，最小公倍数，最大公因数
1.整除：a=bq，则称b整除a，或者a能被b整除。记为: b|a 。若b 不能被a整除则：b|/a(这里的|/是穿过那一竖的，因为某些原因不能打出来)
2.最大公因数：a1,a2,a3…an为n个不全为0 的整数，d是其中每个数的因数，则称d为a1,a2,a3,…,an的公因数所有公因数中最大的称为最大公因数。记为：gcd(a1,a2,a3,…an),或者(a1,a2,a3,…an)。
3，最小公倍数：所有公倍数中最小的正整数成为最小公倍数。记为：lcm(a1,a2,a3,…,an)或者[a1,a2,a3,…an]。

欧几里得算法又成为辗转相除法

反复使用带余算法求最大公约数。
例:r0=a,r1=b,反复运用欧几里得:
r0=r1q1+r2
r1=r2q2+r3
…
rn-1=rnqn+rn+1;rn+1=0;
这时的rn 就是a,b的最大公因数。
举例：
计算（93991，102757）：
102757 = 939911 + 8766
93991 = 876611 - 2435
8766 = 24354 - 974
2435 = 9742 + 487
974 = 4872+0
所以（93997，102757）=487
这样就求出最大共因数，要想求出最小公倍数可以用a/gcd(a,b) * b
我们用C语言来进行试试叭。

#include<stdio.h> #include<math.h> int gcd(int a,int b) { int c; c= a % b; while(c>0) { a=b; b=c; c= a % b; } return b; } int main() { int a,b,d; long lcm; printf("请输入a,b 的值：n"); scanf("%d %d",&a,&b); a = abs(a); b = abs(b); d = gcd(a,b); lcm = a / d * b; printf("a,b的最大公因数为:%d,最小公倍数为：%ld",&d,&lcm); return 0; }

12345678910111213141516171819202122232425262728'

二元一次方程求解

ax+by=c 有整数解时：gcd(a,b)|c。
通解为：x=x0+bt/(a,b);
y=y0-at/(a,b)
例如：求方程243x+198y=909的整数解
243=198+45 9=（243-198）9-1982=2439-19811
198=454+18 9=45-（198-454）2=459-19811
45=182+9 9=45-182
18=92