z11.1.cpp

#include <iostream>
using namespace std;

// Быстрая проверка простоты (для маленьких p, q)
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;
}

// Быстрое возведение в степень по модулю
long long modPow(long long base, long long exp, long long m)
{
    long long result = 1;
    base = base % m;
    while (exp > 0)
    {
        if (exp & 1)  // если exp нечетно
            result = (result * base) % m;
        base = (base * base) % m;
        exp >>= 1;
    }
    return result;
}

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

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

    if (!isPrime(p) || !isPrime(q))
    {
        cout << "p или q не простые\n";
        return 0;
    }

    long long n = (long long)p * q;
    long long phi = (long long)(p - 1) * (q - 1);

    // Выбираем e
    int e = 2;
    while (e < phi)
    {
        if (gcd(e, phi) == 1) break;
        e++;
    }

    int d = modInverse(e, phi);

    cout << "n = " << n << ", phi(n) = " << phi << endl;
    cout << "Открытая экспонента e = " << e << endl;
    cout << "Закрытая экспонента d = " << d << endl;

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

    long long C = modPow(M, e, n);
    cout << "Зашифровано: " << C << endl;

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

    return 0;
}