【数学 逆元】HDU 1211 RSA

2019-04-13 21:01发布

站内文章 / 模拟电子
15879 0 1350
链接：天气不好 模拟了一下RSA算法就好了。主要的过程在于求逆元。 #include #include #include #include #include #include using namespace std; int cal_d(int r, int s) { int MOD[150][2] = {0}, num = 0, x2 = 1, y2 = 0, x1, y1; MOD[num][0] = r, MOD[num][1] = s; while(MOD[num][1]) { num ++; MOD[num][0] = MOD[num - 1][1]; MOD[num][1] = MOD[num - 1][0] % MOD[num - 1][1]; } for(int i = num - 1; i >= 0; i --) { x1 = y2; y1 = x2 - MOD[i][0] / MOD[i][1] * y2; x2 = x1, y2 = y1; } if(x1 <= 0) x1 += s; return x1; } int pppp(int c, int d, int n) { int xx = 1; for(int i = 1; i <= d; i++) { xx *= c; xx %= n; } return (int)xx; } int main() { int p, q, e, l; while(scanf("%d%d%d%d", &p, &q, &e, &l) != EOF) { int fn = (p-1)*(q-1), n = p * q; int dd = cal_d(e,fn); while(l--) { int hehe; scanf("%d", &hehe); printf("%c", pppp(hehe, dd, n)); } printf(" "); } return 0; }

热门文章