欧几里得扩展-逆元求解

核心公式：xa + yb = gcd（a，b）

逆元为上述公式的特殊情况（gcd（a，b）== 1，a和b互为质数）

老师上课提问：1~26哪些满足与26互质，满足互质其逆元为多少？（即求乘法加密的key）

代码实现

#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;
}

运行结果

运行结果

上课笔记

仿真加密 扩展欧几里得递归系数推导 扩展欧几里得