RSA 开发日志

1.质数筛

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1LL<<32
mt19937 rnd(time(0));
vector<int> pri;
bitset<N>not_prime;
signed main() {
	for (int i = 2; i <= N; ++i) {
		if (!not_prime[i]) {
			pri.push_back(i);
		}
		for (int pri_j : pri) {
			if (i * pri_j > N) break;
			not_prime[i * pri_j] = true;
			if (i % pri_j == 0) {
				break;
			}
		}
	}
	for(int i=0; i<100; i++)
	cout << pri[rnd()%pri.size()] << '\n';
	return 0;
}

选择p，q，然后求出n，再选择e

2.逆元

#include<bits/stdc++.h>
using namespace std;
#define ll __int128
#define N 105
void extend_gcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1, y = 0;
        return;
    }
    extend_gcd(b, a % b, x, y);
    ll tmp = x;
    x = y;
    y = tmp - (a / b) * y;
}
ll mod_inverse(ll a, ll mod){
    ll x, y;
    extend_gcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}
int main(){
	
	cout << (unsigned long long)mod_inverse(e, (p-1)*(q-1));

	return 0;
}

求出 d，结束

可以用 python 验证