z11.2.cpp

#include <iostream>
#include <vector>
using namespace std;

bool isPrime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i*i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

int gcd(int a, int b)
{
    while(b != 0)
    {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// быстрое возведение в степень mod
long long modPow(long long base, long long exp, long long mod)
{
    long long res = 1;
    base %= mod;
    while (exp > 0)
    {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

// Мультипликативная обратная (простой перебор)
int modInverse(int e, int phi)
{
    for (int x = 1; x < phi; x++)
    {
        if ((1LL*e*x) % phi == 1) return x;
    }
    return -1;
}

// Функция для генерации (n, e, d)
bool generateRSA(int p, int q, long long &n, long long &phi, int &e, int &d)
{
    if (!isPrime(p) || !isPrime(q)) return false;
    n = (long long)p * q;
    phi = (long long)(p-1)*(q-1);

    // находим e
    e = 2;
    while(e < phi)
    {
        if (gcd(e, phi) == 1) break;
        e++;
    }
    d = modInverse(e, phi);
    if (d == -1) return false;
    return true;
}

int main()
{
    int p, q;
    cout << "Введите p и q (небольшие простые): ";
    cin >> p >> q;

    long long n, phi;
    int e, d;
    if (!generateRSA(p, q, n, phi, e, d))
    {
        cout << "Ошибка при генерации RSA (p,q не простые?)\n";
        return 0;
    }

    cout << "n=" << n << ", phi=" << phi << ", e=" << e << ", d=" << d << endl;

    cout << "Введите сообщение (M<n): ";
    long long M;
    cin >> M;

    long long C = modPow(M, e, n);
    cout << "Шифротекст: " << C << endl;

    long long Dec = modPow(C, d, n);
    cout << "Расшифровка: " << Dec << endl;

    return 0;
}