Teste de primalitate Algoritmi de factorizarecriptografie/note_curs... · Teste deterministice: dac...

Teste de primalitate Algoritmi de factorizare

Teste de primalitateAlgoritmi de factorizare

Anul II

Februarie 2019


Teste de primalitate

Un test de primalitate este un criteriu pe care trebuie sa-l satisfacaun numar natural n pentru a fi un numar prim.In general, daca numarul n trece un test de primalitate, el ar puteafi prim. Daca n nu trece un test de primalitate, atunci cu sigurantael nu este prim.Testele de primalitate pot fi:

Teste deterministice: daca n trece testul, atunci cu sigurantaeste un numar prim.

Teste probabilistice: daca n trece testul, atuci probabil n esteun numar prim, cu o probabilitate p; probabilitatea ca n sa fieprim devine cu atat mai mare cu cat el trece testul de maimulte ori.


Teste de primalitate

Teste conditionate: adevarul afirmatiei “un numar n caretrece testul este prim” depinde de demonstrarea unui enuntmatematic despre care se presupune ca e adevarat, dar nu estedemonstrat.

Teste neconditionate: adevarul afirmatiei se bazeaza peenunturi si teorii matematice demonstrate.

Teste care functioneaza ın timp polinomial.

Teste care functioneaza ın timp subexponential.

Teste care functioneaza ın timp exponential.


1. Impartirea succesiva

Teorema

Orice numar natural compus n are cel putin un divizor prim maimic decat

√n.

Se imparte succesiv numarul n la toate numerele prime (sau latoate numerele impare) mai mici sau egale cu

√n.

Daca la fiecare impartire restul este diferit de 0, atunci numarul neste prim.

Exemplu

n = 17117⇒ [√n] = 130

Π([√n]) = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,

61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127}

Niciunul din elementele lui Π([√n]) nu divide n, deci n este prim.


1. Impartirea succesiva

Este un test deterministic, neconditionat, care functioneaza ın timpexponential, deci ineficient.

Definitie

Pentru n ∈ N, n > 0, π(n) este numarul numerelor prime mai micidecat n.

π(n) = #Π(n)

Teorema

(i) Daca n ≥ 17, π(n) > n/ ln n.(ii) Daca n > 1, π(n) < 1, 25506(n/ ln n).

Pentru a decide daca n este prim, numarul ımpartirilor este deordinul lui n/ ln n. Pentru RSA, avem nevoie de numere prime decel putin 75 de cifre, deci numarul ımpartirilor necesare ıntr-unasemenea test este de aproximativ 36 · 1034!!!


2. Testul Fermat

Este un test probabilistic, neconditionat, ın timp polinomial, carese bazeaza pe Teorema lui Fermat:

Teorema

Presupunem ca n este un numar prim. Atunci oricare ar fi numarulnatural b ∈ {1, 2, . . . , n − 1},

bn−1 ≡ 1 (mod n) (∗)


2. Testul Fermat

Exemplu

Incercam sa aflam daca n = 91 este numar prim. Alegem b = 3 sicalculam

390 ≡ 1 (mod 91).

Deci este posibil ca 91 sa fie numar prim.Facem testul si pentru b = 2 si obtinem

290 ≡ 64 (mod 91)

deci 91 sigur nu este numar prim.

Daca n satisface (∗) pentru un anumit numar b, atunci n senumeste pseudoprim ın raport cu b. Este posibil ca n sa nu fieprim, dar congruenta (∗) sa fie totusi adevarata.


2. Testul Fermat

Teorema

(i) Daca n este pseudoprim ın raport cu numerele b1 si b2, atuncieste pseudoprim si ın raport cu b1b2.(ii) Daca n nu trece testul (∗) pentru un b ∈ {1, 2, . . . , n − 1},atunci n nu trece testul (∗) pentru cel putin jumatate din valorileposibile ale lui b.

Deci, sau n trece testul pentru toate numereleb ∈ {1, 2, . . . , n − 1}, sau avem cel putin 50% sanse sa nimerimpeste o valoare a lui b pentru care n nu trece testul.Problema: exista numere n care nu sunt prime, dar trec testul (∗)pentru toate valorile b ∈ {1, 2, . . . , n − 1}: numerele Carmichael.

Exemplu

561 = 3 · 11 · 17


3. Testul Solovay-Strassen

Este un test probabilistic, neconditionat, ın timp polinomial. Fieb ∈ N, p un numar prim, n = pa11 . . . parr . Notam:(

b

p

)=

0 daca p|b1 daca (b mod p) este patrat perfect−1 ın rest(

b

n

)=

(b

p1

)a1

. . .

(b

pr

)ar

Teorema (Criteriul lui Euler)

Daca n este un numar prim, atunci, oricare ar fi b ∈ Zn,

bn−12 ≡

(b

n

)(mod n) (∗∗)

Daca n satisface testul (∗∗), atunci n se numeste pseudoprim Eulerın raport cu b.



Propozitie

Daca n este pseudoprim Euler ın raport cu b, atunci n estepseudoprim ın raport cu b.

Exemplu

n = 91 este pseudoprim ın raport cu b = 3, dar nu este pseudoprimEuler (345 = 27 (mod 91)).

Teorema

Daca n este compus, atunci congruenta (∗∗) nu este adevaratapentru cel putin jumatate din valorile b ∈ {1, 2, . . . , n − 1}.



1 Se alege numarul natural k > 0 sib1, . . . , bk ∈ {1, 2, . . . , n − 1}.

2 i := 1

3 Se calculeaza cei doi membri ai congruentei (∗∗) pentru n sibi (timp de calcul: O(log3 n)).

4 Daca congruenta (∗∗) nu este verificata, atunci n estecompus.

5 Daca congruenta (∗∗) este verificata, atunci i := i + 1.

daca i ≤ k , atunci mergi la pasul 3.daca i > k , atunci n este numar prim, cu o probabilitate de cel

putin 1− 12k

= 2k−12k

(∼ probabilitatea ca n sa fie compus este de cel mult 12k

).


4. Testul Miller-Rabin

Este un test probabilistic, neconditionat, ın timp polinomial (1980).Fie n un numar impar si fie

s = max{α ∈ N | 2α|(n − 1)}.

Decin − 1 = 2st

cu t impar.Fie b ∈ {1, 2, . . . , n − 1}.Daca n este numar prim, atunci (Teorema lui Fermat)

bn−1 ≡ 1 (mod n).

Notandb2

s−1t ≡ a (mod n)

obtinema2 ≡ 1 (mod n).



Daca n este prim, atunci a = ±1 (deoarece in acest caz ecuatiaa2 ≡ 1 (mod n) are doar solutiile ±1).

Teorema

Daca n este numar prim si b ∈ Zn, b 6= 0, atunci una dinurmatoarele afirmatii este adevarata:(i) sau bt ≡ 1 (mod n),(ii) sau exista r ∈ {0, . . . , s − 1} astfel ıncat

b2r t ≡ −1 (mod n).



In practica, se calculeaza succesiv

bt , b2t , b4t , . . .

pana se obtine valoarea 1. Daca n este prim, atunci ultima valoarediferita de 1 trebuie sa fie −1.

Exemplu

Fie n = 561, b = 2. Atunci

n − 1 = 2435

Obtinem succesiv:235 ≡ 263 (mod 561)22·35 ≡ 2632 ≡ 166 (mod 561)22

2·35 ≡ 1662 ≡ 67 (mod 561)22

3·35 ≡ 672 ≡ 1 (mod 561).Cum ultima valoare obtinuta ınainte de a obtine 1 este 67 6= −1,561 nu este prim.



Daca bt ≡ 1 (mod n) sau exista r ∈ {1, 2, . . . , s − 1} astfel incatb2

r t ≡ −1 (mod n), atunci n se numeste pseudoprim tare in raportcu b.

Propozitie

Daca n este pseudoprim tare in raport cu b, atunci estepseudoprim Euler in raport cu b.

Teorema

Daca n este compus, probabilitatea ca n sa fie pseudoprim tare inraport cu un numar b ales aleatoriu este de cel mult 25%.

Deci, daca n trece testul Miller-Rabin pentru k valori ale lui b,probabilitatea ca n sa fie prim este cel putin 4k−1

4k(∼ probabilitatea

ca n sa fie compus este cel mult 14k

).


Alegerea aleatorie a numerelor prime

In numeroase criptosisteme cu cheie publica, avem nevoie saalegem aleatoriu numere prime cu un numar fix de biti, k .(1) Alegem un numar impar n care are k biti: se da primului siultimului bit valoarea 1, iar ceilalti biti sunt alesi la ıntamplare.(2) Se aplica o combinatie a ımpartirii succesive cu testulMiller-Rabin:- se ımparte n la toate numerele prime impare mai mici decat ovaloare prestabilita B (de obicei B = 106); daca la un moment datse obtine restul 0, n este compus, se alege o alta valoare pentru nsi se reıncepe algoritmul;- daca de fiecare data restul este diferit de 0, se aplica testulMiller-Rabin de l ori.Daca l = 3 si k > 1000, aceasta combinatie asigura ca un numar ncare trece testul este prim, cu o probabilitate de eroare de celmult 1

280.


Alte teste de primalitate

5. Testul Miller (1975)Test deterministic, in timp polinomial, conditionat: presupuneca Ipoteza Riemann Generalizata este adevarata.

6. Testul Adleman-Pommerance-Rumely (1983)Test deterministic, neconditionat, in timp subexponential:Tim O((log n)log log log n).

7. Testele Goldwasser-Kilian (1986), Atkin (1986)Adleman-Huang (1992)Teste probabilistice, neconditionate, in timp polinomial. Au labaza teoria curbelor eliptice.


8. Testul Agrawal-Kayal-Saxena (2002)

Este un test deterministic, neconditionat, in timp polinomial:O((log n)7,5).

Teorema

Fie n ∈ N, n ≥ 2, a ∈ N, (a, n) = 1. Atunci n este prim daca sinumai daca

(X + a)n ≡ X n + a (mod n) (∗ ∗ ∗)

Problema: timp exponential pentru a testa toti coeficientii. Sereduce numarul coeficientilor evaluand cei doi membri aicongruentei (∗ ∗ ∗) modulo un polinom de forma X r − 1, pentru rconvenabil si suficient de mic.Valoarea lui r si numarul valorilor lui a necesare sunt marginite deun polinom in log n.


8. Testul Agrawal-Kayal-Saxena (2002)

Input: n ∈ N, n > 1.

1 If (n = ab for some a ∈ N and b > 1) then Output:COMPOSITE

2 Find the smallest r ∈ N such that or (n) > 4 log2 n (or (n) =ordinul lui n modulo r; daca n este compus, exista un astfel der mai mic decat 16 log5 n)

3 If 1 < (a, n) < n for some a ≤ r , Output: COMPOSITE

4 If n ≤ r , Output:PRIME

5 For a = 1 to⌊

2√φ(r) log n

⌋do

if (X + a)n 6= X n + a (mod X r − 1, n),Output: COMPOSITE

6 Output:PRIME


Algoritmi de factorizare

1. Algoritmul lui Lehman (metoda Fermat)Exista o corespondenta bijectiva intre factorizarile n = a · b siscrierile n = t2 − s2

Daca a si b au valori apropiate, atunci s = a−b2 este mic, iar t

este putin mai mare decat√n. Se poate cauta t incepand cu

[√n + 1].

Exemplu

n = 200819; [√n] = 448, [

√n + 1] = 449

Pentru t = 449, 4492 − 200819 = 782 nu este patrat perfect.Pentru t = 450, 4502 − 200819 = 1681 = 412, deci

200819 = 4502 − 412 , n = 491 · 409

Timp: O(ec√ln n·ln ln n)



2. Algoritmul QS (Quadratic Sieve, Ciurul patratic)O generalizare a Metodei Fermat.

Idee: caut x 6= ±y astfel ıncat

x2 ≡ y2 (mod n).

Fie m = [√n] si

F (X ) = (X + m)2 − n

Pentru X ∈ [−α, α] ∩ Z, calculam si descompunem in factori primiF (X ).Alegem apoi X1, . . . ,Xk astfel incat

F (X1) . . .F (Xk) = pa11 . . . parr

cu toti exponentii ai pari. Atunci

((X1 + m) . . . (Xk + m))2 ≡ (pa1/21 . . . p

ar/2r )2 (mod n).



Exemplu

Fie n = 7429. Atunci m = 86 si

F (X ) = (X + 86)2 − 7429.

AvemF (−3) = 832 − 7429 = −540 = −1 · 22 · 32 · 5F (1) = 872 − 7429 = 140 = 22 · 5 · 7F (2) = 882 − 7429 = 315 = 32 · 5 · 7.Atunci

(87 · 88)2 ≡ (2 · 3 · 5 · 7)2 (mod 7429)

deci, pentru x = 87 · 88 (mod 7429) = 227 siy = 2 · 3 · 5 · 7 (mod 7429) = 210, x2 − y2 = 7429, decix − y = 17 este un divizor al lui 7429.



3. Metoda ”rho” (Pollard)

4. Metoda fractiilor continue

5. Algoritmi ce folosesc teoria curbelor eliptice (Pollard,Lenstra)

Teste de primalitate Algoritmi de factorizarecriptografie/note_curs... · Teste deterministice: dac...

Documents

Transcript of Teste de primalitate Algoritmi de factorizarecriptografie/note_curs... · Teste deterministice: dac...