3670 - Afin1: Difference between revisions

Revision as of 10:16, 27 December 2023

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

Citire date de intrare

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

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

Decriptare mesaj

rezultat_decriptare = decripteaza_mesaj(a, b, mesaj_criptat)

Scriere rezultat în fișier de ieșire

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

   if rezultat_decriptare == -1:
       f_out.write("-1\n")
   else:
       f_out.write(f"{rezultat_decriptare}\n")

</syntaxhighlight>

@@ Line 37: / Line 37: @@
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-def euclid_extendat(a, b):
+def este_ineficienta(a, b):
-     if a == 0:
+     for x in range(26):
-        return b, 0, 1
+        if (a * x + b) % 26 == x:
-     else:
+            return True
-        gcd, x, y = euclid_extendat(b % a, a)
+     return False
-        return gcd, y - (b // a) * x, x
-def invers_modular(a, m):
+def decripteaza_mesaj(a, b, mesaj_criptat):
-    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
+     a_invers = -1
+    for i in range(26):
+        if (a * i) % 26 == 1:
+            a_invers = i
+            break
-     # Verificăm dacă perechea (a, b) este ineficientă
+     if a_invers == -1:
-    for x1 in range(m):
+        return -1  # Perechea de chei este ineficientă
-        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 litera in mesaj_criptat:
+         if litera.isalpha():
-     for caracter in mesaj_criptat:
+             cod_litera = ord(litera) - ord('a')
-         if caracter.isalpha():
+             x_decriptat = (a_invers * (cod_litera - b)) % 26
-             if caracter.isupper():
+            litera_decriptata = chr(x_decriptat + ord('a'))
-                cod = (a_invers * (ord(caracter) - ord('A') - b)) % m
+            mesaj_decriptat += litera_decriptata
-                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
+             mesaj_decriptat += litera
      return mesaj_decriptat
-def main():
+# Citire date de intrare
-    with open("afin1.txt", "r") as fisier:
+with open("afin1in.txt", "r") as f:
-        a, b = map(int, fisier.readline().split())
+    a, b = map(int, f.readline().split())
-        mesaj_criptat = fisier.readline().strip()
+    mesaj_criptat = f.readline().strip()
-    rezultat = cifru_afin_decriptare(a, b, mesaj_criptat)
+# Decriptare mesaj
+rezultat_decriptare = decripteaza_mesaj(a, b, mesaj_criptat)
-    with open("afin1.txt", "w") as fisier_out:
+# Scriere rezultat în fișier de ieșire
-         fisier_out.write(str(rezultat))
+with open("afin1out.txt", "w") as f_out:
+    if rezultat_decriptare == -1:
+         f_out.write("-1\n")
+    else:
+        f_out.write(f"{rezultat_decriptare}\n")
-if __name__ == "__main__":
-    main()
 </syntaxhighlight>