Algoritmul Miller-Rabin

[vladiii]

In primul rand, daca gasiti vreo eroare in codul scris de mine sau vreo greseala de algoritm, va rog sa o mentionati, pentru ca nici eu nu sunt 100% sigur de codul pe care l-am facut.

Ok, ce este Algoritmul Miller-Rabin ? Numele sau intreg este: "Testul de primalitate al numerelor Miller-Rabin". Practic verifica daca un numar este prim sau nu. Insa, nu degeaba se numeste test, pentru ca probabilitatea ca raspunsul returnat de program nu este maxima (pow(4,-k)).

Si poate va intrebati, de ce sa folosesc acest algoritm, cand pot sa impart numarul la toate numerele mai mici decat sqrt(numar) ? Pai da, dar acesta este mult mai rapid si are o complexitate mai mica

Va prezint in continuare codul scris de mine in C (astept imbunatatiri sau corectari):

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <conio.h>
#include <math.h>
int main()
{
    long numar, s=0, a=0, r, d=0, k, aux1=0, aux2=0, i=0, aux3=0, aux4=0;
    div_t aux5;
    printf("Introdu numarul: ");
    scanf("%d", &numar);
    printf("\nIntrodu un numar k(probabilitatea este 4 la puterea -k): ");
    scanf("%d", &k);
    aux1=numar-1;
    while(aux1%2 !=1) {
          if(aux1%2==0) { 
                 s++; }
          aux1=aux1/2; }
    printf("%ld", (int)pow(2,s));
    aux4=(long)pow(2,s);
    aux5=div(numar-1,aux4);
    d=aux5.quot;
    printf("\nPuterea lui 2 este: %ld iar restul este: %ld", s, (long)d); 
    if(numar==2 || numar==3 || numar==5 || numar==7 || numar==11) {
                printf("\nNumarul este prim"); }
    else if(numar=4 || numar==6 || numar==8 || numar==9 || numar==10) {
                printf("\nNumarul nu este prim/ este compus"); }
    else {
    srand(time(NULL));
    for(i=0;i<k;i++) {
        a=rand() %(numar-1)+1;
        aux2=(long)pow(a,d)%numar;
        for(r=0;r<=s-1;r++) {
            if(aux2 !=1 & (long)pow(a,pow(2,r)*d)%numar !=numar-1) {
                        aux3=1; } } }
    if(aux3==1) { printf("\nNumarul este prim"); }
    else { printf("\nNumarul nu este prim/ este compus"); } }
    getch();
    return 0;
}

Sper sa va fie de folos la ceva (si ma repet, postati eventualele greseli de algoritm .

P.S. Pentru un "accuracy" mai bun puteti sa generati toate numerele A din intervalul [1, numar-1], insa asta va ingreuna timpul de executie (eu am ales numere random).

Bibliografie:

[url]http://en.wikipedia.org/wiki/Miller-Rabin_primality_test[/url]
+
[url]http://vladii.wordpress.com[/url]

[Black Pitbull-]

Mam esti obsedat de asta .... e si la u pe blog si aici ... pune si pe youtube