Rabin Miller Algorithm

Question

J'essaie de comprendre l'algorithme de Rabin Miller, mais je suis confus au sujet d'une petite partie. S'il vous plaît, aidez à le comprendre. Nous avons calculé 's' en 2^d * s, puis nous prenons un entier aléatoire 'a' et en calculant a^s% p, s'il est égal à 1, alors p est Prime probable. Sinon, si pour tout 'r' a^(r * s)% p = -1 Alors nous aurons 1 dans la prochaine équation, donc p est premier. Première itération si x = 1; Ensuite, nous le vérifions dans l'instruction if, mais après la première itération, quelle est la signification de if, je ne comprends pas. S'il vous plaît aider ...

Confondre Partie:

if(mod!=p-1 && temp%2==0){ 
       return false; 
      } 

Origingal Miller Mise en œuvre:

bool Miller(long long p,int iteration){ 
    if(p<2){ 
     return false; 
    } 
    if(p!=2 && p%2==0){ 
     return false; 
    } 
    long long s=p-1; 
    while(s%2==0){ 
     s/=2; 
    } 
    for(int i=0;i<iteration;i++){ 
     long long a=rand()%(p-1)+1,temp=s; 
     long long mod=modulo(a,temp,p); 
     while(temp!=p-1 && mod!=1 && mod!=p-1){ 
      mod=mulmod(mod,mod,p); 
      temp *= 2; 
     } 
     if(mod!=p-1 && temp%2==0){ 
      return false; 
     } 
    } 
    return true; 
} 

Answer 1

La définition d'un témoin M-R est a telle que a**s != 1 (modulo p) et a**(2**r * s) != -1 (modulo p) pour tous r. La boucle expire lorsque mod, qui a la valeur a**(2**r * s), satisfait mod == 1 (modulo p) ou mod == -1 (modulo p).

Si mod == 1 (modulo p), la deuxième propriété d'être un témoin M-R est satisfaite, parce que chaque valeur de a**(2**r * s) jusqu'à présent n'est pas conforme à -1 (mod p), et aucune des valeurs futures est en harmonie, car ils sont tous 1 (mod p). Etant donné que la deuxième propriété est valide, la première propriété, a**s != 1 (modulo p), contient si et seulement si le corps de la boucle s'exécute au moins une fois. Initialement, temp == s, qui est au plus (p - 1)/2, et mod != p - 1 par la deuxième propriété. Nous avons temp % 2 == 0 si et seulement si le corps de la boucle s'exécute au moins une fois.