Untitled

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

def affine_decrypt(ciphertext, a, b):
    plaintext = ''
    m = 26

    # Перевіряємо, що a і m взаємно прості
    if math.gcd(a, m) != 1:
        raise Exception('Key "a" is not coprime with 26')

    a_inv = modinv(a, m)

    for char in ciphertext:
        if char.isalpha():
            char_index = ord(char) - ord('A')
            decrypted_char_index = (a_inv * (char_index - b)) % m
            decrypted_char = chr(decrypted_char_index + ord('A'))
            plaintext += decrypted_char
        else:
            plaintext += char

    return plaintext

import math

ciphertext = "OSTGTLHZGDCTXJXOSTDQXNTGOHDIIDFGYGHUITZXJOJXXFZZTCFYJQDXJQBITNJGCDZDQZDQJXOSTHQIVGTDITQTZVNGTZDQKGHZOSTXLTTDQCOSTGHHOLDFXTHKSFTGDKGGHKYGYTTCOSTGHHOLDFXTHKSFTGDKGGHKYGYTTCGXTLDQTMFTDKGKGWTGNHGRJXDUHIJXSTCKHGTTWTG"
for a in range(1, 26):
    for b in range(1, 26):
        try:
            decrypted_text = affine_decrypt(ciphertext, a, b)
            print(f"Key: a={a}, b={b}\nDecrypted Text: {decrypted_text}\n")
        except Exception as e:
            pass  # Пропускаємо комбінації, де a не взаємно проста з m