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 afin1in.txt conține pe prima linie numerele a b iar pe a doua linie mesajul criptat.

Date de iesire

Fișierul de ieșire afin1out.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

afin1in.txt

17 20

fekhfmbabfkkh

afin1out.txt

Datele introduse corespund restrictiilor impuse

twentyfifteen

Exemplul 2

afin1in.txt

17 20

FEKhfmbabfkkh

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def este_ineficienta(a, b):

   for x in range(26):
       if (a * x + b) % 26 == x:
           return True
   return False

def decripteaza_mesaj(a, b, mesaj_criptat):

   mesaj_decriptat = ""
   a_invers = -1
   for i in range(26):
       if (a * i) % 26 == 1:
           a_invers = i
           break

   if a_invers == -1:
       return -1  # Perechea de chei este ineficientă

   for litera in mesaj_criptat:
       if litera.isalpha():
           cod_litera = ord(litera) - ord('a')
           x_decriptat = (a_invers * (cod_litera - b)) % 26
           litera_decriptata = chr(x_decriptat + ord('a'))
           mesaj_decriptat += litera_decriptata
       else:
           mesaj_decriptat += litera

   return mesaj_decriptat

def verificare_rezultat_corect(a, b, mesaj_criptat, rezultat_decriptare):

   if rezultat_decriptare == -1:
       return True  # Perechea de chei este considerată ineficientă

   if not (1 <= len(mesaj_criptat) <= 10000):
       return False

   return True

1. Citire date de intrare

with open("afin1in.txt", "r") as f:

   a, b = map(int, f.readline().split())
   mesaj_criptat = f.readline().strip()

1. Decriptare mesaj

rezultat_decriptare = decripteaza_mesaj(a, b, mesaj_criptat)

1. Scriere rezultat în fișier de ieșire

with open("afin1out.txt", "w") as f_out:

   if verificare_rezultat_corect(a, b, mesaj_criptat, rezultat_decriptare):
       if rezultat_decriptare == -1:
           f_out.write("-1\n")
       else:
           f_out.write(f"{rezultat_decriptare}\n")
   else:
       f_out.write("Datele introduse nu corespund restrictiilor impuse.\n")

</syntaxhighlight>