Obiectiv

            Dorim să generăm numere prime mari, cu un număr de cifre p dat. Spre exemplu pentru p=2 un număr peim format din 2 cifre este 11. Pentru un p mic, până la 5 putem genera numere prime relativ uşor. Dacă p=3 atunci pornim de la 100 şi mergem până la 999 şi pentru fiecare număr din această multime excluzând numerele pare, testăm dacă este prim sau nu. Dacă este prim îl tipărim şi oprim execuţia programului.

Pentru parcurgerea numerelor de la 10^p la 10^p+1-1 sărind peste cele pare avem nevoie de

operaţii, deci complexitatea algoritmului de parcurgere este O(10^p), deci exponenţială după numărul cifrelor.

Pentru testarea primalităţii unui număr n sunt necesari  paşi, şi cum n are p cifre avem aproximativ  paşi. Deci o complexitate exponenţială după numărul cifrelor.

Deci ordinul total de complexitate al algoritmului este O(10^p), practic pentru un număr cu 100 de cifre problema este nerezolvabilă cu acest algoritm.

Voi prezenta o metodă de generare de numere prime mari care se bazează pe noţiuni probabilistice. Vom spune că un număr n este prim cu o probabilitate p (mai mare sau mai mică).

Densitatea numerelor prime

            Numerele prime nu sunt “prea rare”. Spre exemplu să considerăm mulţimea de numere M={0,1,2,3,4,5,6,7,8,9}. Numerele prime din această mulţime sunt P={1,2,3,5,7} deci |P|=5 iar |M|=10, rezultă că probabilitatea ca alegând la întâmplare un număr din M acesta să fie prim este 1/2; deci dacă extragem la întâmplare două numere din M avem şanse mari ca măcar unul să fie prim. Vom putea lucra în continuare cu aceste două numere nu cu toate cele 10.

            Fie funcţia  - numită distribuţia numerelor prime.  are valoarea egală cu numărul numerelor prime mai mici sau egale cu n. De exemplu  pentru că numerele prime mai mici sau egale cu 7 sunt {1,2,3,5,7}.

            Graficul funcţiei  este:

Teorema numărului numerelor prime

            Această teoremă dă o aproximare a funcţiei de distribuţie a numerelor prime.

            Teorema 1 (Teorema numărului numerelor prime)

            Această aproximare este destul de bună, pentru n=10⁹  iar  eroarea relativa a acestei aproximări este mai mică de 6%.

            Putem folosi teorema numărului numerelor prime pentru a estima probabilitatea ca un întreg n ales la întâmplare să fie prim.

            În mulţimea M={1,…,n} avem  numere prime, rezultă că probabilitatea ca alegând la întâmplare un număr din M acesta să fie prim este numărul cazurilor favorabile împărţit la numărul cazurilor posibile, adică:

            Deci va trebui să examinăm  numere întregi de p cifre alese aleator pentru a găsi un număr prim de p cifre.

Testul de pseudoprimalitate

            Spunem ca n este pseudoprim cu baya a dacă n este compus si

            Teorema 2 (mica teoremă a lui Fermat)

            Dacă p este prim atunci

            Corolar 2.1

Dacă reuşim să găsim un a pentru care (1) să nu fie adevărată atunci n este cu siguranţă compus.

Vom verifica dacă un n satisface relaţia (1) pentru a=2. Dacă nu, atunci el este compus, altfel presupunem că n este prim. (de fapt n este pseudo prim relativ la baza 2).

Pentru a face testul trebuie să calculăm 2^n-1 (mod n). Am putea face un ciclu for de la 1 la n-1 şi să tot înmulţim rezultatul cu 2 şi apoi să reţinem restul împărţirii la n. Presupunând că fiecare operaţie din ciclul for se execută într-un timp constant ordinul de complexitate al algoritmului este O(n)=O(10^p) (am presuus că n are p cifre) deci exponenţial după numărul cifrelor.

Ridicarea la putere prin ridicări repetate la pătrat

            Ne propunem să calculăm a^b(mod n).

            Exemplu:

pentru a=3 b=5 n=7 avem

observăm că putem calcula  astfel :

            La fiecare pas vom împărţii puterea b la 2, dacă restul împărţirii este 1 atunci rezultatul va fi egal cu a înmulţit cu rezultatul ridicării lui a la puterea b-1, iar dacă restul este 0 atunci rezultatul va fi egal cu produsul , iar dacă b este egal cu 0 atunci rezultatul va fi 1.

            Deci formula recursivă poate fi scrisă astfel:

unde .

            Dezavantajul acestei formule este că unele calcule se fac de 2 ori. Această formulă recursivă de calcul este echivalentă cu următorul algoritm:

     Functia exp_mod(a,b,n)

       {calculeaza a la puterea b modulo n}

       dß1;

       fie <b_k,b_k-1,...,b₀> reprezentarea binara a lui b;

       pentru ißk,0,-1 executa

         dß(d*d)mod n;

         daca b_i=1 atunci

           dß(d*a)mod n;

         sfd;

       sfpt;

       expßd;

     sfexp;

            Acest algoritm are ordinul de complexitate O(ln(b)). Având în vedere că pe postul lui b în testul de pseudoprimalitate se află n-1 avem ordinul de complexitate O(ln(n-1)) deci O(ln(10^p))=O(p), adică liniar în raport cu cifrele exponentului.

            Testul de pseudoprimalitate îl putem descrie într-un algoritm astfel:

     Functia pseudoprim(n)

       {verifica daca n este pseudoprim relativ la baza 2}

       daca exp(2,n-1,n)=1 atunci

         pseudoprimßcompus; {rezultat definitiv}

       altfel

         pseudoprimßprim; {speram}

       sfd;

     sfpseudoprim

            Dacă funcţia întoarce “prim” s-ar putea să greşească. Cât de des poate să apară această greşeală? Există numai 22 de valori ale lui n mai mici decât 10000 pt care ea este eronată. Se poate arăta că dacă numărul cifrelor lui n tinde la infinit atunci eroarea acestei funcţii tinde la 0.

            Am putea schimba baza, în loc de 2 să punem 3 (de exemplu), astfel am elimina câteva numere din cele 22. Din nefericire însă există numere pentru care oricum am alege baza ele scapă de testul de pseudoprimalitate chiar dacă nu sunt prime. Aceste numere se numesc numere Carmichael. Primele 3 numere Carmichael sunt: 561, 1105, 1729.

Testul aleator de primalitate al lui Miller-Rabin

            Acest test se bazează pe următorul rezultat:

            Teorema 3

            Dacă p este un număr prim impar şi e>0 atunci ecuaţia:

are numai soluţiile x=1 şi x=-1.

            Un număr x este o rădăcină netrivială a ecuaţiei (2) dacă verifică relaţia (2) şi x nu este egal cu 1 sau -1.

            Testul de numar prim al lui Miller-Rabin îmbunătăţeşte testul de pseudoprimalitate prin două modificări:

1)                  Încearcă să aleagă diferite valori ale bazei a spre deosebire de testul de pseudoprimalitate care are o sigură valoare pentru a.

2)                  În timp ce calculează fiecare exponenţiere modulară, stabileşte dacă nu cumva a fost găsită o rădăcină netrivială a ecuaţiei (2). Dacă aşa ceva se întâmplă atunci returnează compus.

Vom utiliza o funcţie auxiliară Test, astfel încât Test(a,n) este adevărat dacă şi numai dacă a şi n satisfac relaţia (2). Această funcţie este similară testului de pseudoprimalitate dar este mult mai eficientă.

Voi prezenta mai întâi funcţia Test şi apoi voi explica algoritmul.

     Functia Test(a,n)

       {returneaza adevarat daca a ridicat la puterea

  n-1 modulo n este egal cu 1 si fals altfel}

       fie <b_k,b_k-1,...,b₀> reprezentarea binara a lui n-1;

       dß1;

       pentru ißk,0,-1 executa

         xßd;

         dß(d*d)mod n;

         daca d=1 si x<>1 si x<>n-1 atunci

           Testßadevarat;{caz 1}

         sfd

         daca b_i=1 atunci

           dß(d*a)mod n;

         sfd;

       sfpt;

       daca d<>1 atunci

         Testßadevarat;{caz 2}

       Sfd;

       Testßfals;

     sfTest;

            Funcţia Test se bazează pe algoritmul de exponenţiere modulară. Dacă funcţia Test returnează adevărat în caz 2 atunci am găsit că  deci conform teoremei lui Fermat n nu este prim pentru că am găsit un p=d care nu verifică relaţia (1). Dacă funcţia Test returnează adevarat în caz 1 atunci s-a descoperit x o rădăcină netrivială a ecuaţiei (2) deci conform teoremei 3 numărul n nu este prim.

            Dacă Test returnează adevărat atunci n nu este prim altfel s-ar putea ca n să fie prim cu o probabilitate destul de mare.

            Voi prezenta acum algoritmul lui Miller-Rabin care utilizează funcţia Test pentru verificarea faptului că n nu este prim.

     Functia Miller_Rabin(n,s)

       {testeaza daca n este prim prin alegerea la

  intamplare a s numere intre 1 si n-1 care sa

  fie baza in apelul functiei Test}

       pentru jß1,s executa

         aßRandom(1,n-1);{alege un numar intre 1 si n-1}

         daca Test(a,n)=adevarat atunci

           Miller_Rabinßcompus;{sigur}

         Sfd;

       Sfpt;

       Miller_Rabinßprim;{aproape sigur}

     SfMiller_Rabin;

            Dacă din s încercări nu se găseşte nici o bază cu care n să fie pseudoprim şi nu se găseşte nici o soluţie a ecuaţiei (2) atunci algoritmul presupune că că n este prim. Cu cât s este mai mare cu atât avem o siguranţă mai mare a faptului că n este prim.

            Dacă n este un număr cu p cifre atunci complexitatea algoritmului este O(s*p).

Cât de sigur este algoritmul lui Miller-Rabin ?

            Dacă algoritmul returnează compus atunci suntem siguri ca n nu este prim, iar dacă returnează prim atunci există o mică şansă de eroare. Spre deosebire de testul de pseudoprimalitate eroarea nu depinde de n, nu există intrări defavorabile pentru acest subalgoritm. Rata de eroare depinde de dimensiunea lui s şi de “norocul” avut la alegerea bazei a.

            Teorema 4

            Pentru orice întreg impar n>2 şi orice intreg s >0 probabilitatea ca Miller_Rabin(n,s) să greşească este cel mult 2^-s.

            Astfel, s=50 ar trebui să fie suficient pentru aproape orice aplicaţie imaginabilă.

Algoritmul de generare industrială de numere prime

            Pentru a genera un număr prim de p cifre am spus că avem nevoie de ln(n) numere.

     Functia genereaza(p,s)

       {returneaza un numar prim de p cifre cu

  o probabilitate de 2^-s

  returneaza -1 daca nu reuseste sa genereze un

  astfel de numar}

  nßRandom(p);{returneaza un numar aleator de p cifre}

  pentru iß1,ln(n) executa

    daca Miller_Rabin(n,s)=prim atunci

      genereazaßn;

    sfd;

    nßn+1;

    daca n are p+1 cifre atunci

      nß10^p;

    sfd;

  sfpt;

  genereazaß-1;

     Sfgenereaza;

            Complexitatea acestui algoritm este O(s*p²), deci polinomială în raport cu numărul cifrelor numărului care se doreste a fi generat spre deosebire de testul de forţă brută care are o complexitate exponenţială în raport cu numprul cifrelor numărului care se doreşte a fi generat.

Program de generare demonstrativ

Programul genereaza un număr prim aleator de p cifre cu probabilitatea 1-.2^-s. Dacă nu va reuşii generarea unui astfel de număr atunci va returna un mesaj de eroare.

descarcă sursele programului

descarcă întreg referatul în format doc

Bibliografie

1)      Introducere în algoritmi de Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest

2)     Curs de Algebră Computaţională Universitatea Babeş Bolyai Cluj-Napoca Facultatea de Matematică si Informatică secţia Informatică anul 2 semestrul 2 de Lect. Dr. SACAREA Cristian

3)      mathworld.wolfram.com

4)      www.free-definition.com