def egcd(a, b) -> tuple[int, int, int]:
    """Erweiterter Euklidischer Algorithmus

    :param a: Ganzzahl A
    :type a: int
    :param b: Ganzzahl B
    :type b: int
    :return: (ggT(a,b), a_p, b_p) mit a_p * a + b_p * b = ggT(a,b)
    :rtype: tuple[int, int, int]
    """
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)


def encrypt(m : int, p : int, q : int) -> int:
    """Verschlüsselungsfunktion

    :param m: Klartextzahl m
    :type m: int
    :param p: Primzahl p
    :type p: int
    :param q: Primzahl q
    :type q: int
    :return: quadratischer Rest von m^2 mod pq als Geheimtext
    :rtype: int
    """
    n = p * q
    return (m**2) % n

def decrypt(c : int, p : int, q : int) -> tuple[int, int, int, int]:
    """Entschlüsselungsfunktion

    :param c: Geheimtext
    :type c: int
    :param p: Primzahl p
    :type p: int
    :param q: Primzahl q
    :type q: int
    :return: Mögliche 4 Lösungen
    :rtype: tuple[int, int, int, int]
    """
    # mögliche Wurzeln modulo p,q bestimmen
    m_p = c**((p + 1)//4) % p
    m_q = c**((q + 1)//4) % q
    n = p * q

    #y_p, y_q ermitteln
    d, y_p, y_q = egcd(p, q)

    # Chinesischer Restsatz
    r_1 = (y_p * p * m_q + y_q * q * m_p) % n
    r_2 = n - r_1
    r_3 = (y_p * p * m_q - y_q * q * m_p) % n
    r_4 = n - r_3

    # Mögliche Lösungen zurückgeben
    return (r_1, r_2, r_3, r_4)

def encode(s : str) -> int:
    """Kodiert einen Buchstaben nach lateinischem Alphabet a->0, b->1, z->25

    :param s: Buchstabe
    :type s: str
    :return: kodierter Buchstabe
    :rtype: int
    """
    return ord(s.lower()) - 97

def decode(i : int) -> str:
    """Dekodiert einen Buchstaben nach lateinischem Alphabet 0->a, 1->b, 25->z

    :param i: Ganzzahl (bestenfalls 0 <= i <= 25)
    :type i: int
    :return: dekodierter Buchstabe
    :rtype: str
    """
    return chr(i + 97)