Algoritmul Nechaev-Polliga-Hellman
Un algoritm de căutare pentru găsirea logaritmului discret
Problema logaritmului discret. la valorile date ale parametrilor a. b și p. p este un număr prime, 1 Definiția. Logaritmul discret al numărului b pentru baza a modulo p este gradul în care urmează să fie ridicat numărul a. pentru a obține numărul b: Un alt nume pentru logaritmul discret al lui l este indicele b la baza a modulo p. Definiția. Cel mai mic grad la care trebuie să construim numărul a modulo p. pentru a obține 1. se numește ordinea numărului a. Denumirea este ord. Aprobarea. Fie p un număr prime. Ordinea maximă a unui număr modulo p este p - 1. Aprobarea. Fie p un număr prime, parametrii a. b satisfac inegalitățile 1 1. Calculați valorile unui k mod p pentru k = 1, 2, 3, ... înainte de egalitate b = a k mod p. 2. Valoarea k. la care se face comparația b = a k mod p. este un logaritm discret. Algoritmul treptelor mari - mici (Shenks) Fie n ordinea unui a. 1. Calculăm m: = én ù, unde én ù rotunjire cu exces. 2. Construim o masă de perechi (j A j) pentru j = 0, 1, 2. m -1. 3. Calculați t: = a - m. rezolvarea comparației a m × t = 1 mod p. 5. Buclele prin i de la 0 la m - 1 verificăm dacă g este a doua componentă din Tabelul 2 dacă g = a j. apoi am setat x = m × i + j Fie n ordinea unui a. 1. Numărul n este reprezentat ca n = q × r. q este un număr prime. 3. Folosind algoritmul de pași mari-mici, găsim y. rezolvarea comparației 4. Calculați t: = a - y. rezolvarea comparației a y x t = 1 mod p. 6. Folosind algoritmul de pași mari-mici, găsim z. rezolvarea comparației 1. Dați definiția logaritmului discret. 2. Definiți ordinea numărului. 3. Formulează condițiile pentru existența unui logaritm discret. 4. Descrieți algoritmul exhaustiv al logaritmului discret. 5. Descrieți algoritmul pentru pașii mari-mici. 6. Descrieți algoritmul Nechaev-Pollig-Hellman. 7. În ce algoritmi criptografici este necesară rezolvarea problemei logaritmului discret? Definiția. Grupul (G, *) constă din setul G pe care este definită operația binară *. satisface trei axiome: Definiția. Se spune că un grup (G, *) este comutativ (abelian) dacă pentru orice element a. b. și c în G egalitatea Dacă operația de multiplicare este definită ca o operație binară, atunci grupul se numește multiplicativ, elementul element este e = 1, elementul invers este marcat cu -1 sau 1 / a. Dacă operația de adăugare + este definită ca o operație binară, atunci grupul se numește aditiv, elementul element este e = 0, elementul invers este marcat cu -a. Din axiomele grupului, se poate deduce că în grup există doar un element unic. Se poate dovedi, de asemenea, unicitatea elementului invers pentru fiecare element al grupului. Definiția. Un grup (G, *) se spune ca este finit daca numarul elementelor lui G este finit. În acest caz, numărul elementelor setului G se numește ordinea grupului (G, *). Transformările mutuale unice de valoare ale oricărui set formează un grup cu privire la funcționarea multiplicării transformărilor. 1. Setul tuturor numerelor reale non-zero în ceea ce privește funcționarea multiplicării este "grupul multiplicativ de numere reale" R *. 2. Setul tuturor numerelor întregi față de operația de adăugare este un "grup aditiv de numere întregi" Z. 3. Setul tuturor vectorilor din spațiul R n cu privire la adăugarea de vectori. 4. Setul tuturor polinomilor cu coeficienți reali în ceea ce privește adaosul de polinoame. Grupurile din Exemplele 1-4 au infinit mai multe elemente. Fie n un număr natural. Introducem modul de operare comparativ pe setul de numere întregi Z. un modn. o ÎZ. Modulul de operare de comparare împarte setul Z în clase de echivalență corespunzătoare restului divizării numerelor întregi cu n. 0, 1, 2, .... n-1. Setul de clase de echivalență modn formează setul Zn. Toate operațiile aritmetice <+, –, ´.> în Zn se efectuează modulo. Un exemplu. Luați în considerare setul Z25 = <0, 1, 2,…, 24>. Pentru elementele acestui set, avem 13 + 16 = 4, 13 '4 = 2, 13 - 16 = 22, 15. 2 =? Definiția. Să presupunem că a ÎZn. Elementul inversiv multiplicativ al unui element a peste modn este un element a - 1 astfel încât un 'a - 1 = 1 modn. Un element a este declarat a fi inversibil în modn. dacă există un invers pentru el. Divizarea în Zn este definită ca înmulțirea prin elementul invers a. b = a 'b - 1. dacă divizorul b este inversabil. Un exemplu. În setul Z25 2 - 1 = 13, deoarece o comparație de 2 x = 1 mod25 dă soluția x = 13. Prin urmare, 15 2 = 15 '2 - 1 = 15' 13 = 195 = 20 mod25. Un exemplu. Elemente inversibile în Z9. 1, 2, 4, 5, 7, 8. Pentru a determina 5 -1, rezolvăm congruența 5 x = 1 mod 9, care dă soluția x = 2. Prin urmare, 5 -1 = 2. Setul Zn cu modn de operare de adunare formează un grup aditiv finit de ordin n. Introducem setul Zn *. definită ca un subset de Zn. constând doar din elemente reversibile Setul Zn * cu modul de operare de multiplicare formează un grup multiplicativ finit de ordin j (n). Definiția. Să presupunem că a Î Zn *. Ordinea elementului grupului este cea mai mică putere a lui t. în care doriți să construiți un element pentru a obține 1: Notatia t = ord (a). Definiția. Dacă ord (a) = j (n) pentru a Î Zn *. atunci un element a este numit un generator sau un element primitiv al grupului. Dacă există un element generator în grup, atunci grupul este numit ciclic. Aprobarea. Fiecare grup ciclic este abelian. Proprietățile generatoarelor de elemente (primitive) ale grupului multiplicativ Zn * 1. Grupul Zn * are un element generator dacă și numai dacă 4. Dacă Zn * este un grup ciclic, atunci numărul de generatori ai grupului este j (j (n)). 5. Element a Î Zn * este elementul generator al grupului dacă și numai dacă pentru orice divizor prim p al numărului j (n). În grupul Z21 * j (21) = (3 - 1) (7 - 1) = 12 elemente: 1,2,4,5,8,10,11,13,16,17,19,20. Fiecare element are un caracter invers, de exemplu, 2 - 1 = 11, 10 - 1 = 19. Grupul nu este ciclic. Ord (1) = 1, ordin (8,13,20) = 2, ord (4,16) = 3, ord (2,5,10,11,17,19) = 6. Elementele de formare sunt 2, 6, 7, 11: Dacă un anumit subset H al lui G formează un grup cu privire la operația * definită în G, atunci (H, *) se numește un subgrup de (G, *). De exemplu, subgrupul de întregi impare este un subgrup al grupului aditiv de întregi Z, și subsetul de numere impare nu fie un subgrup al acestui grup (plus în Z nu specifică operația la acel subset, ca suma a două numere impare este un număr par). Aprobarea. Pentru ca subsetul H să formeze un subgrup al grupului (G, *), este necesar și suficient ca următoarele două condiții să fie îndeplinite: 1. Rezultatul operației * (definită în G) asupra oricăror două elemente h1. h2 din subsetul H este, de asemenea, un element de H (h1 * h2 Î H). 2. Dacă h Î H, atunci elementul invers h -1 aparține lui H (h -1 Î H). Cele mai simple așa-numite subgrupe ciclice pe care le posedă orice grup G sunt simple. Cu fiecare element a Î G poate fi asociat cu subgrupul ciclic "generat", care, în esență, este cel mai mic dintre subgrupele care conțin acest element. Introducem conceptul de grad a i de a. presupunând că un i = a i - 1 * a. a 0 = e. Cu această definiție a gradului, regulile acțiunilor cu grade sunt îndeplinite: pentru orice număr întreg k și m Deoarece operațiunea de ridicare a unui element al unui grup nu conduce la puterea grupului, toate puterile elementului aparțin unui anumit subgrup al grupului. Aprobarea. Fie grupul (G, *) elementul a. Apoi, toate puterile a i ale elementului formează o subgrupă ciclică generată de elementul a. Definiția. Cel mai mic grad de t. pentru care un t = e este numit ordinea elementului a al grupului (G, *). ord (a) = t. Aprobarea. Subgrupul ciclic generat de un element a ordinii t. are ordinul t. Aprobarea. Ordinea oricărui element al grupului împarte ordinea grupului. Aprobarea. (Teorema Lagrange) Ordinea oricărui subgrup al unui grup finit este un divizor al ordinii grupului. Care au fost aprobate. Dacă ord (a) = t. atunci elementul a k este de ordinul t / GCD (t.k). Un exemplu. În grupul Z29 * ordin (24) = 14. 24 10 = 20, ord (20) = 14 / GCD (14, 10) = 7. Aprobarea. Dacă (G, *) este un grup ciclic de ordin n. d este divizorul lui n. atunci grupul (G, *) are exact j (d) elemente de ordin d. Definiția. Două grupuri (A, *) și (G, ·) se consideră a fi izomorfe dacă există o corespondență unu-la-f. A ® G între elementele seturilor A și G, păstrând acțiunea operațiunilor. pentru orice elemente a. b Î A, egalitatea f (a * b) = f (a) · f (b) Î G. Un exemplu. Grupul multiplicator de numere reale pozitive este (R +. '). Grupul aditiv de numere reale este (R. +). O corespondență unu-la-unu este log. R + R păstrează acțiunea operațiunilor în grupuri. log (x y) = log (x) + log (y). În consecință, grupările (R +. ') Și (R. +) sunt izomorfe. 1. Dați definiția grupului. 2. Definiți ordinea grupului. 3. Care este ordinea elementului grupului? 4. Care grup se numește comutativ? 5. Definirea grupului ciclic. 6. Definiți subgrupa. 7. Definiți subgrupul ciclic. 8. Care element al grupului este numit generator? 9. Care sunt proprietățile generatoarelor grupului Zn *? 10. Menționați teorema Lagrange. 11. Ce grupe sunt numite izomorfe?
Articole similare
Trimiteți-le prietenilor: