- cmmdc/inversul mod
- Euclid
-
Functia Euclid(a,b)
if b = 0 return a
return(Euclid(b; a(modb)))
end Euclid. - Euclid extins
- Functia Euclid-Extins(a,b)
if b = 0 return (a; 1; 0)
a = bk + r.
(d; x; y) = Euclid-Extins(b; r)
return(d; y; x - ky )
end Euclid-Extins
- Euclid extins aplicat intregilor pe n biti ruleaza in O(n3)
- Euclid extins aplicat polinoamelor de grad n, peste orice camp, ruleaza in O(n2)
- congruente liniare de o variabila
transformarile in ambele sensuri intre reprezentarile x mod N si x ≡ ai mod pi unde cmmdc(pi, pj) = 1 ptr i ≠ j , i, j ∈ {1, 2, ..., r} si Πi=1r pi ( din teorema chineza a resturilor) - de la x mod N catre x ≡ ai mod pi este trivial
- de la x ≡ ai mod pi catre x mod N
- N = Πi=1r pi
- Ni = n / pi
- NiNi-1 ≡ 1 ( mod pi ); Ni-1 se calculeaza prin Euclid extins
- x = Σi=1r aiNiN-1i
ruleaza in O(n3)
- teste primalitate
- testul Miller-Rabin
se testeaza numarul n ∈ N cu n -1 = 2s t, unde t este impar si s ≧ 1; se alege aleator a- se calculeaza u0 = at ( mod n)
- se calculeaza ui+1 = u2i ( mod n)
se declara n probabil prim daca u0 = 1 sau ∃ i ai ui = -1
Testul Miller-Rabin repetat de k ori declara intotdeauna un prim ca probabil prim. Un numar compozit este declarat probabil prim cu o probabilitate de cel mutl 2-k
ruleaza in O(k n3)
- descompunerea in factori primi
- metoda ρ a lui Pollard
- se alege x0 ∈ Zn
- se defineste secventa cu relatia de recurenta xi+1 = xi+12 + 1 mod n
- se calculeaza cmmdc(x2i - xi , n) si se opreste calculul daca d > 1
- se testeaza primalitatea factorului gasit anterior
din practica, O(n1/4)
- logaritmul discret
- logaritmul discret al lui y in baza g modulo p este x ai gx ≡ y mod p unde p este prim si g ∈ Up
- algoritmul pas pitic/pas gigant
- se calculeaza a ca parte intreaga din p1/2
- se construieste lista: 1, ga, g2a, g3a, ,,,, ga2
- se construieste lista y, yg, yg2, yg3, ..., , yga-1
- se cauta numarul z care apare in ambele liste
z ≡ ygk ≡ gla mod p
y ≡ gla-k ≡ gx mod p
x ≡ la-k mod ( p - 1 )
ruleaza in O( (log p)2 p1/2)
Algoritmi avansati, Johan Hastad
# posted by Sorin Badescu @ 2:04 PM
