Comment calculer le module des grands nombres ?

Question

Comment calculer le module de 5^55 modulus 221 sans trop utiliser de calculatrice ?

Je suppose qu'il existe des principes simples en théorie des nombres dans la cryptographie pour calculer de telles choses.

Answer 1

Ok, donc vous voulez calculer a^b mod m . Nous allons d'abord adopter une approche naïve, puis nous verrons comment l'affiner.

Premièrement, réduire a mod m . C'est-à-dire, trouver un nombre a1 de sorte que 0 <= a1 < m et a = a1 mod m . Puis, de façon répétée dans une boucle, multipliez par a1 et réduire encore mod m . Ainsi, en pseudo-code :

a1 = a reduced mod m
p = 1
for(int i = 1; i <= b; i++) {
    p *= a1
    p = p reduced mod m
}

En faisant cela, nous évitons les nombres plus grands que m^2 . C'est la clé. La raison pour laquelle nous évitons les nombres plus grands que m^2 c'est parce qu'à chaque étape 0 <= p < m et 0 <= a1 < m .

À titre d'exemple, calculons 5^55 mod 221 . Premièrement, 5 est déjà réduit mod 221 .

1. 1 * 5 = 5 mod 221
2. 5 * 5 = 25 mod 221
3. 25 * 5 = 125 mod 221
4. 125 * 5 = 183 mod 221
5. 183 * 5 = 31 mod 221
6. 31 * 5 = 155 mod 221
7. 155 * 5 = 112 mod 221
8. 112 * 5 = 118 mod 221
9. 118 * 5 = 148 mod 221
10. 148 * 5 = 77 mod 221
11. 77 * 5 = 164 mod 221
12. 164 * 5 = 157 mod 221
13. 157 * 5 = 122 mod 221
14. 122 * 5 = 168 mod 221
15. 168 * 5 = 177 mod 221
16. 177 * 5 = 1 mod 221
17. 1 * 5 = 5 mod 221
18. 5 * 5 = 25 mod 221
19. 25 * 5 = 125 mod 221
20. 125 * 5 = 183 mod 221
21. 183 * 5 = 31 mod 221
22. 31 * 5 = 155 mod 221
23. 155 * 5 = 112 mod 221
24. 112 * 5 = 118 mod 221
25. 118 * 5 = 148 mod 221
26. 148 * 5 = 77 mod 221
27. 77 * 5 = 164 mod 221
28. 164 * 5 = 157 mod 221
29. 157 * 5 = 122 mod 221
30. 122 * 5 = 168 mod 221
31. 168 * 5 = 177 mod 221
32. 177 * 5 = 1 mod 221
33. 1 * 5 = 5 mod 221
34. 5 * 5 = 25 mod 221
35. 25 * 5 = 125 mod 221
36. 125 * 5 = 183 mod 221
37. 183 * 5 = 31 mod 221
38. 31 * 5 = 155 mod 221
39. 155 * 5 = 112 mod 221
40. 112 * 5 = 118 mod 221
41. 118 * 5 = 148 mod 221
42. 148 * 5 = 77 mod 221
43. 77 * 5 = 164 mod 221
44. 164 * 5 = 157 mod 221
45. 157 * 5 = 122 mod 221
46. 122 * 5 = 168 mod 221
47. 168 * 5 = 177 mod 221
48. 177 * 5 = 1 mod 221
49. 1 * 5 = 5 mod 221
50. 5 * 5 = 25 mod 221
51. 25 * 5 = 125 mod 221
52. 125 * 5 = 183 mod 221
53. 183 * 5 = 31 mod 221
54. 31 * 5 = 155 mod 221
55. 155 * 5 = 112 mod 221

Par conséquent, 5^55 = 112 mod 221 .

Maintenant, nous pouvons améliorer cela en utilisant exponentiation par la quadrature du cercle c'est la fameuse astuce qui permet de réduire l'exponentiation à une simple question de log b multiplications au lieu de b . Notez qu'avec l'algorithme que j'ai décrit plus haut, l'amélioration de l'exponentiation par l'élévation au carré, on se retrouve avec le méthode binaire de droite à gauche .

a1 = a reduced mod m
p = 1
while (b > 0) {
     if (b is odd) {
         p *= a1
         p = p reduced mod m
     }
     b /= 2
     a1 = (a1 * a1) reduced mod m
}

Ainsi, puisque 55 = 110111 en binaire

1. 1 * 5 = 5 mod 221 ( 5 est 5^1 mod 221 )
2. 5 * 25 = 125 mod 221 ( 25 est 5^2 mod 221 )
3. 125 * 183 = 112 mod 221 ( 183 est 5^4 mod 221 )
4. 112 * 1 = 112 mod 221 ( 1 est 5^16 mod 221 )
5. 112 * 1 = 112 mod 221 ( 1 est 5^32 mod 221 )

La réponse est donc 5^55 = 112 mod 221 . La raison pour laquelle cela fonctionne est que

55 = 1 + 2 + 4 + 16 + 32

de sorte que

5^55 = 5^(1 + 2 + 4 + 16 + 32) mod 221
     = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221
     = 5 * 25 * 183 * 1 * 1 mod 221
     = 22875 mod 221
     = 112 mod 221

Dans l'étape où nous calculons 5^1 mod 221 , 5^2 mod 221 etc. on note que 5^(2^k) = 5^(2^(k-1)) * 5^(2^(k-1)) parce que 2^k = 2^(k-1) + 2^(k-1) de sorte que nous pouvons d'abord calculer 5^1 et réduire mod 221 puis on l'élève au carré et on réduit mod 221 pour obtenir 5^2 mod 221 etc.

L'algorithme ci-dessus formalise cette idée.

Answer 2

Pour ajouter à la réponse de Jason :

Vous pouvez accélérer le processus (ce qui peut être utile pour les très grands exposants) en utilisant l'expansion binaire de l'exposant. Calculez d'abord 5, 5^2, 5^4, 5^8 mod 221 - vous le faites en répétant l'élévation au carré :

 5^1 = 5(mod 221)
 5^2 = 5^2 (mod 221) = 25(mod 221)
 5^4 = (5^2)^2 = 25^2(mod 221) = 625 (mod 221) = 183(mod221)
 5^8 = (5^4)^2 = 183^2(mod 221) = 33489 (mod 221) = 118(mod 221)
5^16 = (5^8)^2 = 118^2(mod 221) = 13924 (mod 221) = 1(mod 221)
5^32 = (5^16)^2 = 1^2(mod 221) = 1(mod 221)

Nous pouvons maintenant écrire

55 = 1 + 2 + 4 + 16 + 32

so 5^55 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 
        = 5   * 25  * 625 * 1    * 1 (mod 221)
        = 125 * 625 (mod 221)
        = 125 * 183 (mod 183) - because 625 = 183 (mod 221)
        = 22875 ( mod 221)
        = 112 (mod 221)

Vous pouvez voir comment, pour de très grands exposants, cela sera beaucoup plus rapide (je crois que c'est log par opposition à linéaire dans b, mais je ne suis pas certain).

Answer 3

/* The algorithm is from the book "Discrete Mathematics and Its
   Applications 5th Edition" by Kenneth H. Rosen.
   (base^exp)%mod
*/

int modular(int base, unsigned int exp, unsigned int mod)
{
    int x = 1;
    int power = base % mod;

    for (int i = 0; i < sizeof(int) * 8; i++) {
        int least_sig_bit = 0x00000001 & (exp >> i);
        if (least_sig_bit)
            x = (x * power) % mod;
        power = (power * power) % mod;
    }

    return x;
}

Answer 4

Théorème du reste de la Chine vient à l'esprit comme point de départ car 221 = 13 * 17. Donc, décomposer cela en 2 parties qui sont combinées à la fin, une pour le mod 13 et une pour le mod 17. Deuxièmement, je crois qu'il existe une preuve de a^(p-1) = 1 mod p pour tous les a non nuls, ce qui aide également à réduire votre problème puisque 5^55 devient 5^3 pour le cas mod 13 puisque 13*4=52. Si vous regardez sous le sujet "Finite Fields" vous pouvez trouver quelques bons résultats sur la façon de résoudre ce problème.

EDIT : La raison pour laquelle je mentionne les facteurs est que cela crée un moyen de factoriser le zéro en éléments non nuls. Si vous essayez quelque chose comme 13^2 * 17^4 mod 221, la réponse est zéro puisque 13*17=221. Beaucoup de grands nombres ne seront pas des nombres premiers, bien qu'il y ait des moyens de trouver de grands nombres premiers car ils sont beaucoup utilisés en cryptographie et dans d'autres domaines des mathématiques.

Answer 5

Ce que vous recherchez est l'exponentiation modulaire, plus précisément l'exponentiation binaire modulaire. Ce lien wikipédia a un pseudo-code.