Editing 3670 - Afin1

== Enunt ==

Cifrul Afin este un cifru unde fiecare literă este înlocuită cu o altă literă printr-o operație matematica. Fiecărei litere i se asociază un cod: a-0 , b-1 , c-2 , … z-25 . De asemenea, mai avem două numere a și b, numite chei. Fiecare literă se înlocuiește cu litera care are codul egal cu (a*x+b) mod 26 , unde x este codul literei. Pentru anumite perechi de numere a și b rezultatul expresiei (a*x+b) mod 26 poate fi același pentru valori diferite ale lui x; p pereche a b cu această proprietate se consideră ineficientă.

== Cerinta ==

Dându-se valoarea celor două chei și un mesaj criptat să se afișeze mesajul decriptat. Dacă a și b formează o pereche ineficientă atunci se afișează mesajul -1.

== Date de intrare ==

Fișierul de intrare afin1.txt conține pe prima linie numerele a b iar pe a doua linie mesajul criptat.

== Date de iesire ==

Fișierul de ieșire afin1.txt va conține pe prima linie mesajul decriptat sau numarul -1 daca a si b formeaza o pereche ineficienta.

== Restrictii si precizari ==

*1 ≤ lungimea mesajului ≤ 10000

== Exemplul 1 ==
;Intrare
:17 20
:fekhfmbabfkkh
;Iesire
;Datele introduse corespund restrictiilor impuse
:twentyfifteen

== Exemplul 2 ==
;Intrare
:17 20
:FEKhfmbabfkkh
;Iesire
;Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def euclid_extendat(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = euclid_extendat(b % a, a)
        return gcd, y - (b // a) * x, x

def invers_modular(a, m):
    gcd, x, _ = euclid_extendat(a, m)
    if gcd != 1:
        raise ValueError("Invers modular nu exista.")
    else:
        return x % m

def cifru_afin_decriptare(a, b, mesaj_criptat):
    mesaj_decriptat = ""
    m = 26  # Numărul de litere în alfabet

    # Verificăm dacă perechea (a, b) este ineficientă
    for x1 in range(m):
        for x2 in range(m):
            if (a * x1 + b) % m == (a * x2 + b) % m and x1 != x2:
                return -1

    a_invers = invers_modular(a, m)

    for caracter in mesaj_criptat:
        if caracter.isalpha():
            if caracter.isupper():
                cod = (a_invers * (ord(caracter) - ord('A') - b)) % m
                mesaj_decriptat += chr(cod + ord('A'))
            else:
                cod = (a_invers * (ord(caracter) - ord('a') - b)) % m
                mesaj_decriptat += chr(cod + ord('a'))
        else:
            mesaj_decriptat += caracter

    return mesaj_decriptat

def main():
    with open("afin1.txt", "r") as fisier:
        a, b = map(int, fisier.readline().split())
        mesaj_criptat = fisier.readline().strip()

    rezultat = cifru_afin_decriptare(a, b, mesaj_criptat)

    with open("afin1.txt", "w") as fisier_out:
        fisier_out.write(str(rezultat))

if __name__ == "__main__":
    main()

</syntaxhighlight>