核心公式：xa + yb = gcd（a，b）
逆元為上述公式的特殊情況（gcd（a，b）== 1，a和b互為質(zhì)數(shù)）
老師上課提問：1~26哪些滿足與26互質(zhì)叨恨，滿足互質(zhì)其逆元為多少？（即求乘法加密的key）
代碼實現(xiàn)
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0) {
return a;
}
else {
return gcd(b, a % b);
}
}
int x, y, q;
void ex_Eulid(int a, int b) {
if (b == 0) {
x = 1;
y = 0;
q = a;
}
else {
ex_Eulid(b, a % b);
double temp = x;
x = y;
y = temp - a / b * y;
}
}
int main() {
int i;
for (i = 1; i <= 26; i++) {
if(gcd(i,26) == 1){
ex_Eulid(i,26);
printf("%d=(%d)*%d+(%d)*%d\n", q, x, i, y, 26);
}
}
return 0;
}
運行結(jié)果
運行結(jié)果
上課筆記
仿真加密
擴展歐幾里得遞歸系數(shù)推導(dǎo)
擴展歐幾里得
