Diffie-Hellman - primitive racine mod - question de cryptographie

Question

Dans l'extrait ci-dessous, veuillez expliquer en commençant par la première boucle «pour» ce qui se passe et pourquoi. Pourquoi 0 est ajouté, pourquoi est-1 ajouté dans la deuxième boucle. Que se passe-t-il dans la déclaration "if" sous bigi. Enfin, expliquez la méthode modPow. Merci d'avance pour des réponses significatives.

public static boolean isPrimitive(BigInteger m, BigInteger n) { 

    BigInteger bigi, vectorint; 
    Vector<BigInteger> v = new Vector<BigInteger>(m.intValue()); 
    int i; 

    for (i=0;i<m.intValue();i++) 
     v.add(new BigInteger("0")); 

    for (i=1;i<m.intValue();i++) 
    { 
     bigi = new BigInteger("" + i); 

     if (m.gcd(bigi).intValue() == 1) 
      v.setElementAt(new BigInteger("1"), n.modPow(bigi,m).intValue()); 
    } 

    for (i=0;i<m.intValue();i++) 
    { 
     bigi = new BigInteger("" + i); 

     if (m.gcd(bigi).intValue() == 1) 
     { 
      vectorint = v.elementAt(bigi.intValue()); 
      if (vectorint.intValue() == 0) 
       i = m.intValue() + 1; 
     } 
    } 

    if (i == m.intValue() + 2) 
     return false; 
    else 
     return true; 

} 

Answer 1

• Traiter le vecteur sous forme de liste de booléens, avec une valeur booléenne pour chaque nombre de 0 à m. Lorsque vous le voyez de cette façon, il devient évident que chaque valeur est définie sur 0 pour l'initialiser à false, puis sur 1 pour la définir sur true.

• La dernière boucle for teste tous les booléens. Si l'un d'entre eux est 0 (indiquant false), la fonction renvoie false. Si tous sont vrais, la fonction renvoie true. Pour expliquer l'instruction if, vous devez expliquer ce qu'est un mod racine primitif n, qui est le point entier de la fonction. Je pense que si votre objectif est de comprendre ce programme, vous devez d'abord comprendre ce qu'il implémente. Si vous lisez Wikipedia's article dessus, vous verrez cela dans le premier paragraphe:

En arithmétique modulaire, une branche de la théorie des nombres , une racine primitive modulo n est un nombre g avec la propriété que tout nombre coprime à n est congruente à une puissance de g (mod n). En d'autres termes, si g est une racine primitive (mod n), alors pour tout entier a ayant gcd (a, n) = 1, il existe un entier k tel que gk ≡ a (mod n). k est appelé l'indice de a. C'est-à-dire que g est un générateur du groupe multiplicatif d'entiers modulo n.

• La fonction modPow met en œuvre modular exponentiation. Une fois que vous aurez compris comment trouver un mod racine primitif, vous le comprendrez.

Peut-être la dernière pièce du casse-tête pour vous est de savoir que deux chiffres sont coprime si leur plus grand commun diviseur est 1. Et si vous voyez ces contrôles dans l'algorithme que vous avez collé.

Lien bonus: This paper a un joli fond, y compris comment tester les racines primitives vers la fin.