|
Titlul: 231 Secretul Cifrului Scris de: Mircea Pasoi din Aprilie 09, 2006, 00:52:26 Aici puteţi discuta despre problema Secretul Cifrului (http://infoarena.ro/problema/cifru).
Titlul: Re: 231 Secretul Cifrului Scris de: Gogu Marian din Aprilie 10, 2006, 17:44:36 Am redus complexitatea de la O(N*N) la O(N*D), unde D este numarul de divizori ai lui K, dar a trebuit sa includ un vector de 2000 de constante in sursa.
Imi poate spune cineva cum as putea precalcula inteligent toti inversii modulari fata de un numar prim? Vad ca se dau multe probleme unde se afiseaza rezultatul modulo un numar prim si as vrea sa pot face si o impartire la nevoie. Titlul: Raspuns: 231 Secretul Cifrului Scris de: Silviu-Ionut Ganceanu din Aprilie 10, 2006, 20:46:23 Poti calcula inversul modular al unui numar in log(P) unde P este numarul prim fata de care faci modulo. Deci iese P log P pentru toate numerele mai mici ca P. Este suficient ? (Sper sa fi inteles ce vrei).
Pentru a calcula inversul modular al unui numar x fata de un numar prim ai doua posibilitati: 1) x^(P - 1) % P = 1 -> x^(P-2) * x = 1 -> x^(-1) = x^(P - 2) 2) Folosesti Euclid Extins pentru perechea (x, P) care are GCD = 1. Rezulta doua numere a si b (calculate de Euclid Extins) astfel incat a * x + b * P = 1 -> a * x = 1 (mod P) si a (cu cateva modificari) este inversul pe care il cauti. Metoda merge si pentru P neprim atata timp cat GCD(x, P) = 1 - conditie necesara existentei inversului de altfel. Citeste Cormen la capitolul de Teoria numerelor pentru mai multe detalii. Daca stiai lucrurile astea, imi pare rau ca te-am batut la cap :) Poate sunt folositoare altcuiva. Silviu Titlul: Re: 231 Secretul Cifrului Scris de: Gogu Marian din Aprilie 10, 2006, 22:32:06 Multumesc mult!
Sunt chestii foarte utile. Parca prima metoda e mai comod de implementat dar a doua cred ca se poate aplica pentru mai multe probleme. Titlul: Raspuns: 231 Secretul Cifrului Scris de: Silviu-Ionut Ganceanu din Aprilie 11, 2006, 00:35:15 Exact! ;)
Titlul: Raspuns: 231 Secretul Cifrului Scris de: cristi8 din Aprilie 11, 2006, 14:06:20 :shock:
informatii foarte utile! :thumbup: mersi silviu Titlul: Răspuns: 231 Secretul Cifrului Scris de: chisinau gheorghita din Februarie 01, 2009, 15:57:44 cum trebuie facuta criptarea? prin permutarea tuturor numerelor cu o anumita pozitie x spre dreapta sau spre stanga?
Titlul: Răspuns: 231 Secretul Cifrului Scris de: Pirtoaca George Sebastian din Noiembrie 20, 2012, 17:34:24 Salut!
Daca nu am inteles gresit, problema se reduce la determinarea P(n) astfel incat P^k=e. Eu nu gasesc decat 2 permutari (2,3,1) si (3,1,2) :-k (am verificat folosind un program). Imi poate spune cineva , va rog , care este a 3-a permutare ? Multumesc! Titlul: Răspuns: 231 Secretul Cifrului Scris de: Adrian Budau din Noiembrie 20, 2012, 18:52:47 Permutarea (1, 2, 3) mai este
Titlul: Răspuns: 231 Secretul Cifrului Scris de: Pirtoaca George Sebastian din Noiembrie 20, 2012, 19:18:46 Multumesc! Eu nu am luat-o in considerare deoarece m-am gandit ca permutarea trebuie sa fie identica cu prima numai si numai dupa k criptari.
Titlul: Răspuns: 231 Secretul Cifrului Scris de: Soucup Nicolae Silviu din Noiembrie 24, 2012, 19:05:40 @gh09, @SebiSebi: Indiferent daca faci shift circular stanga sau dreapta, pentru N=3 si K=3 exista 3 solutii: (2,3,1) (3,1,2) (1,2,3) - (3,1,2) (2,3,1) (1,2,3) - (1,2,3) (1,2,3) (1,2,3) - (daca N este numar prim atunci K=N sau oricare dintre multiplii lui N)
|