z11.3.cpp

#include <iostream>
#include "string.h"
#include "array.h"
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;
}

long long modPow(long long base, long long exp, long long m)
{
    long long result = 1;
    base %= m;
    while(exp > 0)
    {
        if (exp & 1) result = (result * base) % m;
        base = (base * base) % m;
        exp >>= 1;
    }
    return result;
}

int modInverse(int e, int phi)
{
    for(int x = 1; x < phi; x++)
    {
        if(((long long)e * x) % phi == 1) return x;
    }
    return -1;
}

int main()
{
    // Ввод p, q
    cout << "Введите p, q (простые): ";
    int 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++;
    }
    // d
    int d = modInverse(e, phi);

    // Вывод
    String info = "n=";
    info = info + to_string(n).c_str();
    info = info + ", phi=";
    info = info + to_string(phi).c_str();
    info = info + ", e=";
    info = info + to_string(e).c_str();
    info = info + ", d=";
    info = info + to_string(d).c_str();
    cout << info << endl;

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

    long long C = modPow(M, e, n);
    long long Dec = modPow(C, d, n);

    cout << "Шифротекст: " << C << endl;
    cout << "Расшифрованное: " << Dec << endl;

    return 0;
}