Calculer modulo grand nombre

[invite13a949b5]

Salut, j'aimerais savoir comment faire pour faire le modulo de grand nombre.
Je sais qu'on peu décomposer les exposant, avec des multiplications et des additions . (exemple : 10 ^100 = 10^10 * 10*90) .
Je recherche un exemple très simple pour expliquer les modulo de grand nombre , l'exemple peu être avec des nombres assez petit , je l'adapterai .
Merci
-----

[invite1237a629]

Salut,

Essaie ça : http://forums.futura-sciences.com/post1452111-3.html

[invite13a949b5]

Merci , j'ai déjà lu ce topic mais j'ai du mal à comprendre, se serait possible d'avoir un exemple très simple (surtout que je devrai expliqué à des gens ).
Merci

[invitebe6c366e]

On a que si p est un premier et a est un entier positif tel que p ne divise pas a, alors (mod p)
Par exemple, si a=2 et p=7
(mod 7)

[A voir en vidéo sur Futura]

[invite13a949b5]

Merci de ton exemple, mais en fait l'exemple que je devrais expliquer serais plutôt : 2^15 mod 22 , simplifier cela pour trouver facilement la réponse .

[inviteb250fe1a]

Merci de ton exemple, mais en fait l'exemple que je devrais expliquer serais plutôt : 2^15 mod 22 , simplifier cela pour trouver facilement la réponse .

Tu peux utiliser la méthode qu'on appelle exponentiation rapide (dite 'square and multiply' en anglais), elle permet de calculer rapidement les résidus de puissances modulo un certain nombre rapidement. Pour cela, on écrit le diviseur en binaire, dans ton exemple 15=1+2+4+8.
On a

• 2^1=2 (mod 22)
• 2^2=4 (mod 22)
• 2^4=16 (mod 22)
• 2^8=14 (mod 22)

Pour finir tu as juste à multiplier ces résultats et établir un nouveau reste, celà donne 2¹⁵=2*4*16*14=1792=10 (mod 22)

En fait ton exemple se prête assez mal à cette méthode, d'autant plus que tout le monde sait que 2^15 vaut 32768 dont le reste par 22 vaut 10.

Un exemple plus probant serait de calculer le reste modulo 31 de 3²⁵⁷. Là ton ordinateur n'aura pas assez de chiffres significatifs pour effectuer le calcul directement. On a 257=1+256.

• 3^1=3 (mod 31)
• 3^2=9 (mod 31)
• 3^4=20 (mod 31)
• 3^8 = 28 (mod 31)
• 3^16=9 (mod 31)
• 3^32=20 (mod 31)
• 3^64=28 (mod 31)
• 3^128=9 (mod 31)
• 3^256=20 (mod 31)

Et finalement 3²⁵⁷=3¹*3²⁵⁶=3*20=29 (mod 31)

[invite1237a629]

C'est trop compliqué ~

Surtout ça :

d'autant plus que tout le monde sait que 2^15 vaut 32768 dont le reste par 22 vaut 10.

Soit x la congruence de 2^15 modulo 22
2^15 = x + 22k
Hop ! On est dans un cas particulier puisque 2 divise 22 (autrement, on cherche l'inverse)

2^14 = x/2 + 11k

Now on cherche la congruence de 2^14 modulo 11
: fonction indicatrice d'Euler.
Le théorème d'Euler dit en fait que si a et b sont premiers entre eux,

Formule générale :




Donc on sait que



Donc x = 10.

C'est peut-être plus long en taille mais c'est beaucoup moins fastidieux que de faire des calculs.

[invite1237a629]

Un exemple plus probant serait de calculer le reste modulo 31 de 3²⁵⁷. Là ton ordinateur n'aura pas assez de chiffres significatifs pour effectuer le calcul directement. On a 257=1+256.

• 3^1=3 (mod 31)
• 3^2=9 (mod 31)
• 3^4=20 (mod 31)
• 3^8 = 28 (mod 31)
• 3^16=9 (mod 31)
• 3^32=20 (mod 31)
• 3^64=28 (mod 31)
• 3^128=9 (mod 31)
• 3^256=20 (mod 31)

Et finalement 3²⁵⁷=3¹*3²⁵⁶=3*20=29 (mod 31)

Trop compliqué aussi !
On regarde
Donc

Division euclidienne de 257 par 30 : reste 17



Et après on fait ta méthode pour 3^17.

[invite88636644]

Bonjour, 81 mod 31=19 et pas 20....c'est pourquoi le calcul de 3^257 mod 31 était faux...
Amicalement,