3670 - Afin1: Difference between revisions

Latest revision as of 11:56, 29 December 2023

Enunt[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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

Date de iesire[edit | edit source]

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[edit | edit source]

1 ⩽ lungimea mesajului ⩽ 10000

Exemplul 1[edit | edit source]

afin1in.txt: 17 20; fekhfmbabfkkh
afin1out.txt: Datele introduse corespund restrictiilor impuse; twentyfifteen

Exemplul 2[edit | edit source]

afin1in.txt: 17 20; FEKhfmbabfkkh

Datele introduse nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<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

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 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>

@@ Line 1: / Line 1: @@
 == 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ă.
+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.
+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.
+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 afin1.txt va conține pe prima linie mesajul decriptat sau numarul -1 daca a si b formeaza o pereche ineficienta.
+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
+*1 &les; lungimea mesajului &les; 10000
 == Exemplul 1 ==
-;Intrare
+;afin1in.txt
 :17 20
 :fekhfmbabfkkh
-;Iesire
+;afin1out.txt
-;Datele introduse corespund restrictiilor impuse
+:Datele introduse corespund restrictiilor impuse
 :twentyfifteen
 == Exemplul 2 ==
-;Intrare
+;afin1in.txt
 :17 20
 :FEKhfmbabfkkh
-;Iesire
-;Datele introduse nu corespund restrictiilor impuse
+:Datele introduse nu corespund restrictiilor impuse
 == 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):
-    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):
+def decripteaza_mesaj(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():
+def verificare_rezultat_corect(a, b, mesaj_criptat, rezultat_decriptare):
-     with open("afin1.txt", "r") as fisier:
+     if rezultat_decriptare == -1:
-         a, b = map(int, fisier.readline().split())
+         return True  # Perechea de chei este considerată ineficientă
-        mesaj_criptat = fisier.readline().strip()
-     rezultat = cifru_afin_decriptare(a, b, mesaj_criptat)
+     if not (1 <= len(mesaj_criptat) <= 10000):
+        return False
+    return True
+# 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 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")
-    with open("afin1.txt", "w") as fisier_out:
-        fisier_out.write(str(rezultat))
-if __name__ == "__main__":
-    main()
 </syntaxhighlight>