#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 모듈러 연산에서 음수가 나올 경우 양수로 보정해주는 함수
int mod26(int a) {
    return (a % 26 + 26) % 26;
}

// 모듈로 26에 대한 곱셈의 역원 구하기 (주어진 det에 대해 det * x ≡ 1 (mod 26) 인 x 찾기)
int modInverse(int a, int m = 26) {
    a = mod26(a);
    for (int x = 1; x < m; x++) {
        if ((a * x) % m == 1)
            return x;
    }
    return -1; // 역원이 존재하지 않는 경우 (키로 사용할 수 없음)
}

// 2x2 행렬의 역행렬 구하기 (모듈로 26 기준)
bool getInverseMatrix(int key[2][2], int invKey[2][2]) {
    // 행렬식(Determinant) 계산: ad - bc
    int det = key[0][0] * key[1][1] - key[0][1] * key[1][0];
    int detInv = modInverse(det, 26);
    
    if (detInv == -1) {
        return false; // 행렬식의 역원이 없으면 복호화 불가능
    }
    
    // 수반행렬을 이용한 역행렬 계산 (mod 26 적용)
    invKey[0][0] = mod26(key[1][1] * detInv);
    invKey[0][1] = mod26(-key[0][1] * detInv);
    invKey[1][0] = mod26(-key[1][0] * detInv);
    invKey[1][1] = mod26(key[0][0] * detInv);
    
    return true;
}

// 힐 암호 핵심 연산 (암호화/복호화 공용)
string processHillCipher(string text, int key[2][2]) {
    string result = "";
    
    // 2글자씩 쌍을 지어 행렬 곱셈 수행
    for (size_t i = 0; i < text.length(); i += 2) {
        int p1 = text[i] - 'A';
        int p2 = text[i+1] - 'A';
        
        int c1 = mod26(key[0][0] * p1 + key[0][1] * p2);
        int c2 = mod26(key[1][0] * p1 + key[1][1] * p2);
        
        result += (c1 + 'A');
        result += (c2 + 'A');
    }
    return result;
}

int main() {
    // 1. 사용할 키 행렬 정의 (역행렬이 존재하는지 확인 필요)
    // 예시 키: [[5, 8], [17, 3]] -> det = 15 - 136 = -121 ≡ 9 (mod 26). 9의 역원은 3으로 존재함.
    int key[2][2] = {
        {5, 8},
        {17, 3}
    };
    
    int invKey[2][2];
    if (!getInverseMatrix(key, invKey)) {
        cout << "오류: 선택한 키 행렬은 역행렬이 존재하지 않아 복호화할 수 없습니다!" << endl;
        return 1;
    }
    
    // 2. 평문 입력
    string plaintext = "yaho";
    cout << "원래 평문: " << plaintext << endl;
    
    // 글자 수가 홀수이면 X를 붙여 짝수로 맞춤
    if (plaintext.length() % 2 != 0) {
        plaintext += 'X';
    }
    
    // 3. 암호화 진행
    string ciphertext = processHillCipher(plaintext, key);
    cout << "암호화된 텍스트: " << ciphertext << endl;
    
    // 4. 복호화 진행 (역행렬 사용)
    string decryptedText = processHillCipher(ciphertext, invKey);
    cout << "복호화된 텍스트: " << decryptedText << endl;
    
    return 0;
}