// Hill Cipher

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

// Convert character to number (A=0, ..., Z=25)
int charToInt(char c) {
    return toupper(c) - 'A';
}

// Convert number to uppercase character
char intToChar(int n) {
    return 'A' + (n % 26);
}

// Modulo 26 (handles negative numbers too)
int mod26(int n) {
    return (n % 26 + 26) % 26;
}

// Multiply 3x3 matrix with 3x1 vector
vector<int> multiplyMatrix(const vector<vector<int>>& mat, const vector<int>& vec) {
    vector<int> res(3, 0);
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            res[i] = mod26(res[i] + mat[i][j] * vec[j]);
    return res;
}

// Calculate determinant of 3x3 matrix
int determinant(const vector<vector<int>>& m) {
    int det = m[0][0]*(m[1][1]*m[2][2] - m[1][2]*m[2][1]) -
              m[0][1]*(m[1][0]*m[2][2] - m[1][2]*m[2][0]) +
              m[0][2]*(m[1][0]*m[2][1] - m[1][1]*m[2][0]);
    return mod26(det);
}

// Find modular inverse of a number modulo 26
int modInverse(int det) {
    det = (det % 26 + 26) % 26; // Ensure positive mod
    for (int i = 1; i < 26; ++i) {
        if ((det * i) % 26 == 1) return i;
    }
    return -1; // No modular inverse exists

}

// Adjugate (cofactor transpose) of 3x3 matrix
vector<vector<int>> adjugate(const vector<vector<int>>& m) {
    vector<vector<int>> adj(3, vector<int>(3));

    adj[0][0] = mod26(m[1][1]*m[2][2] - m[1][2]*m[2][1]);
    adj[0][1] = mod26(-(m[0][1]*m[2][2] - m[0][2]*m[2][1]));
    adj[0][2] = mod26(m[0][1]*m[1][2] - m[0][2]*m[1][1]);

    adj[1][0] = mod26(-(m[1][0]*m[2][2] - m[1][2]*m[2][0]));
    adj[1][1] = mod26(m[0][0]*m[2][2] - m[0][2]*m[2][0]);
    adj[1][2] = mod26(-(m[0][0]*m[1][2] - m[0][2]*m[1][0]));

    adj[2][0] = mod26(m[1][0]*m[2][1] - m[1][1]*m[2][0]);
    adj[2][1] = mod26(-(m[0][0]*m[2][1] - m[0][1]*m[2][0]));
    adj[2][2] = mod26(m[0][0]*m[1][1] - m[0][1]*m[1][0]);

    // Transpose for adjugate
    swap(adj[0][1], adj[1][0]);
    swap(adj[0][2], adj[2][0]);
    swap(adj[1][2], adj[2][1]);

    return adj;
}

// Inverse of 3x3 matrix modulo 26
vector<vector<int>> inverseMatrix(const vector<vector<int>>& matrix) {
    int det = determinant(matrix);
    int detInv = modInverse(det);

    if (detInv == -1) {
        cout << "Matrix is not invertible under mod 26.\n";
        return {};
    }

    vector<vector<int>> adj = adjugate(matrix);
    vector<vector<int>> inv(3, vector<int>(3));
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            inv[i][j] = mod26(adj[i][j] * detInv);
    return inv;
}

// Encrypt plaintext using Hill Cipher
string encrypt(const string& plaintext, const vector<vector<int>>& key) {
    string cleanText = "";
    for (char c : plaintext)
        if (isalpha(c)) cleanText += toupper(c);

    // Pad with 'X' if not multiple of 3
    while (cleanText.size() % 3 != 0)
        cleanText += 'X';

    string cipher = "";
    for (size_t i = 0; i < cleanText.size(); i += 3) {
        vector<int> block = {
            charToInt(cleanText[i]),
            charToInt(cleanText[i+1]),
            charToInt(cleanText[i+2])
        };
        vector<int> res = multiplyMatrix(key, block);
        for (int val : res)
            cipher += intToChar(val);
    }

    return cipher;
}

// Decrypt cipher using Hill Cipher
string decrypt(const string& cipher, const vector<vector<int>>& key) {
    vector<vector<int>> invKey = inverseMatrix(key);
    if (invKey.empty()) return "";

    string plain = "";
    for (size_t i = 0; i < cipher.size(); i += 3) {
        vector<int> block = {
            charToInt(cipher[i]),
            charToInt(cipher[i+1]),
            charToInt(cipher[i+2])
        };
        vector<int> res = multiplyMatrix(invKey, block);
        for (int val : res)
            plain += intToChar(val);
    }

    return plain;
}

int main() {
    vector<vector<int>> key = {
        {6, 24, 1},
        {13, 16, 10},
        {20, 17, 15}
    }; // GYBNQKURP

    string text;
    cout << "Enter the plain text: ";
    getline(cin, text);

    string encrypted = encrypt(text, key);
    cout << "Encrypted: " << encrypted << endl;

    string decrypted = decrypt(encrypted, key);
    cout << "Decrypted: " << decrypted << endl;

    return 0;
}