rsa-crt算法高效率,多注释,带时间记录,尽可能少的行数的c语言实现代码
时间: 2023-02-06 09:47:05 浏览: 73
以下是 RSA-CRT 算法的 C 语言实现代码,带有注释和时间记录功能,尽可能简洁:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 计算 (a * b) % m
long long mulmod(long long a, long long b, long long m) {
long long res = 0;
a %= m;
while (b > 0) {
if (b & 1) res = (res + a) % m;
a = (a * 2) % m;
b >>= 1;
}
return res;
}
// 计算 (a ^ b) % m
long long powmod(long long a, long long b, long long m) {
long long res = 1;
a %= m;
while (b > 0) {
if (b & 1) res = mulmod(res, a, m);
a = mulmod(a, a, m);
b >>= 1;
}
return res;
}
// 检查 n 是否为质数
int is_prime(long long n) {
if (n <= 1 || n == 4) return 0;
if (n <= 3) return 1;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
for (int i = 0; i < 20; i++) {
long long a = rand() % (n - 3) + 2;
long long x = powmod(a, d, n);
if (x == 1 || x == n - 1) continue;
int r;
for (r = 1; r <= d - 1; r++) {
x = mulmod(x, x, n);
if (x == n - 1) break;
}
if (r == d) return 0;
}
return 1;
}
// 求最小的质数 p,使得 p % 4 == 3
long long get_prime() {
long long p = rand() % 100000 + 100000;
while (p % 4 != 3 || !is_prime(p)) {
p++;
}
return p;
}
// 计算最大公约数
long long gcd(long long a, long long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
// 求逆元 x^-1 mod m
long long invmod(long long x, long long m) {
long long y = m, u = 1, v = 0;
while (y != 0) {
long long t = x / y;
x -= t * y;
long long tmp = x;
x = y;