231 Secretul Cifrului

[•domino]

Aici puteţi discuta despre problema Secretul Cifrului.

[•gogu]

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.

[•silviug]

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

[•gogu]

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.

[•silviug]

Exact!

[cristi8]

  
informatii foarte utile!
mersi silviu

[•gh09]

cum trebuie facuta criptarea? prin permutarea tuturor numerelor cu o anumita pozitie x spre dreapta sau spre stanga?

[•SebiSebi]

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)  (am verificat folosind un program). Imi poate spune cineva , va rog , care este a 3-a permutare ? Multumesc!

[•freak93]

Permutarea (1, 2, 3) mai este

[•SebiSebi]

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.

[•DxH5dIMHN]

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