#include <iostream>
#include <string>
#include <random>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;

#define mylongtype boost::multiprecision::cpp_int //long long //boost::multiprecision::cpp_int
#define str wstring

vector<bool> toBinVec(mylongtype number)
{
    vector<bool> numBin;

    bool modulo = 0;
    mylongtype n2 = number;

    if (number == 0)
    {
        numBin.push_back(0);
    } else {
        while (true)
        {
            //modulo = n2 % 2;
            if (n2 % 2 == 1)
                modulo = 1;
            else
                modulo = 0;

            n2 = (n2 - modulo) / 2;
            numBin.insert(numBin.cbegin(), modulo);

            if (n2 == 0 && modulo == 1)
                break;
        }
    }

    return numBin;
}

mylongtype fastpowmod(mylongtype base_, mylongtype pow_, mylongtype mod_)
{
    mylongtype result = 1;
    vector<bool> binpow = toBinVec(pow_);

    for (vector<bool>::iterator it = binpow.begin(); it != binpow.end(); it++)
    {
        result = result * result;

        if (*it == 1)
            result *= base_;

        result %= mod_;
    }

    return result;
}

mylongtype euclideanAlg(mylongtype a, mylongtype b)
{
    mylongtype min = std::min(a, b);
    mylongtype max = std::max(a, b);

    mylongtype modulo = 1;
    while (modulo != 0)
    {
        modulo = max % min;
        //std::cout << max << "/" << min << " = " << max/min << " (modulo " << modulo << ")\n";
        max = min;
        min = modulo;
    }

    return max;
}

const wstring alphabet = L"абвгдеёжзийклмнопрстуфхцчшщъыьэюя";

string codeAlphabet(wchar_t letter)
{
    for (unsigned int i = 1; i <= alphabet.length(); i++)
    {
        if (letter == alphabet[i-1])
        {
            string ret;
            if (i < 10)
            {
                ret = std::to_string(0);
            }

            ret.append(to_string(i));

            return ret;
        }
    }

    return 0;
}

std::wstring StringToWstring(const std::string & source)
{
    std::wstring target(source.size()+1, L' ');
    std::size_t newLength=std::mbstowcs(&target[0], source.c_str(), target.size());
    target.resize(newLength);
    return target;
}

string codeText(string text)
{
    string result;
    wstring text2 = StringToWstring(text);
    for (uint i = 0; i < text.length(); i++)
    {
        string code = codeAlphabet(text2[i]);

        if (i == 0 && code[0] == '0') //avoid leading zero
        {
            result += code[1];
        } else {
            result.append(code);
        }

        cout << i << " " << text[i] << " " << code << " | " << result << endl;
    }

    return result;
}

void eulerAlgMatrix(mylongtype a, mylongtype b, mylongtype &x, mylongtype &y)
{
    mylongtype q;
    mylongtype r;

    mylongtype e11 = 1, e12 = 0,
               e21 = 0, e22 = 1;
    while (true)
    {
        q = a / b;
        r = a % b;

//        wcout << "q=" << q << " , r=" << r << '\n';

        if (r == 0)
        {
            x = e12;
            y = e22;
            break;
        } else {
            mylongtype te12 = e11 * 1 + e12 * -q;
            mylongtype te22 = e21 * 1 + e22 * -q;

            e11 = e12; e12 = te12;
            e21 = e22; e22 = te22;

            a = b;
            b = r;

//            wcout << "E:\n";
//            wcout << e11 << " " << e12 << "\n";
//            wcout << e21 << " " << e22 << "\n";
        }
    }
}

int main()
{
    setlocale(LC_CTYPE, "");

    string text = "динозавр";
    mylongtype p = 77733343;
    mylongtype q = 98764579;



    mylongtype m = p * q;
    mylongtype phi_m = (p - 1) * (q - 1);

    //code source text
    mylongtype num_text = stoll(codeText(text)) % m;

    cout << text << " ---> " << num_text << "\n";

    //choose encrypt key
    //random_device rd;
    //mt19937 generator(rd());
    mt19937 generator;
    uniform_int_distribution<int> distribution(pow(10, 3), pow(10, 4));

    int enc_key = distribution(generator);
    while (euclideanAlg(enc_key, phi_m) != 1)
        enc_key = distribution(generator);

    cout << "e=" << enc_key << ", (e, phi(m))=" << euclideanAlg(enc_key, phi_m) << "\n";

    mylongtype enc_num_text = fastpowmod(num_text, enc_key, m);
    cout << "Encrypted message: " << enc_num_text << "\n";


    mylongtype a = 0; mylongtype b = 0;
    eulerAlgMatrix(enc_key, phi_m, a, b);
    if (a < 0)
        a += m;

    mylongtype dec_key = a;

    cout << "d=" << dec_key << "\n";
    cout << "e * d = " << enc_key * dec_key % m << " mod m\n";


    mylongtype dec_enc_num_text = fastpowmod(enc_num_text, dec_key, m);
    cout << dec_enc_num_text << "\n";
}