3670 - Afin1 - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T11:56:01Z

Rezolvare

← Older revision		Revision as of 11:56, 29 December 2023
Line 64:		Line 64:

	return mesaj_decriptat		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		# Citire date de intrare
Line 75:		Line 84:
	# Scriere rezultat în fișier de ieșire		# Scriere rezultat în fișier de ieșire
	with open("afin1out.txt", "w") as f_out:		with open("afin1out.txt", "w") as f_out:
	if rezultat_decriptare == -1:		if verificare_rezultat_corect(a, b, mesaj_criptat, rezultat_decriptare):
	f_out.write("-1\n")		if rezultat_decriptare == -1:
			f_out.write("-1\n")
			else:
			f_out.write(f"{rezultat_decriptare}\n")
	else:		else:
	f_out.write(f"~~{rezultat_decriptare}~~\n")		f_out.write("Datele introduse nu corespund restrictiilor impuse.\n")



	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa: /* Rezolvare */

2023-12-27T10:16:13Z

Rezolvare

← Older revision		Revision as of 10:16, 27 December 2023
Line 37:		Line 37:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<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 = ""		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:		else:
	mesaj_decriptat += ~~caracter~~		mesaj_decriptat += litera

	return mesaj_decriptat		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>		</syntaxhighlight>

Mesarosdenisa at 10:14, 27 December 2023

2023-12-27T10:14:56Z

← Older revision		Revision as of 10:14, 27 December 2023
Line 1:		Line 1:
	== Enunt ==		== 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 (ax+b) mod 26 , unde x este codul literei. Pentru anumite perechi de numere a și b rezultatul expresiei (ax+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 '''(ax+b) mod 26''' , unde x este codul literei. Pentru anumite perechi de numere a și b rezultatul expresiei '''(ax+b) mod 26''' poate fi același pentru valori diferite ale lui x; p pereche a b cu această proprietate se consideră ineficientă.

	== Cerinta ==		== 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 ==		== 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 ==		== 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 ==		== Restrictii si precizari ==

	*1 ≤ lungimea mesajului ≤ 10000		*1 &les; lungimea mesajului &les; 10000

	== Exemplul 1 ==		== Exemplul 1 ==
	;~~Intrare~~		;afin1in.txt
	:17 20		:17 20
	:fekhfmbabfkkh		:fekhfmbabfkkh
	;~~Iesire~~		;afin1out.txt
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:twentyfifteen		:twentyfifteen

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

Mesarosdenisa: Pagină nouă: == 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 (ax+b) mod 26 , unde x este codul literei. Pentru anumite perechi de numere a și b rezultatul expresiei (ax+b) mod 26 poate fi același pentru valori diferite...

2023-12-12T16:06:16Z

Pagină nouă: == 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...

New page

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