Modulo d'un grand nombre

**fred44220** · 04/05/2007, 10h34

Bonjour,

Je suis très ennuyée avec un calcul de modulo 24 sur un grand chiffre, en espérant que quelqu'un aura la solution...
Voici mon pb :
je dois donc calculer le modulo 24 d'un nombre grand nombre (la qté de chiffres de ce nombre varie entre 13 et 26) (obtenu par programmation)
Malheureusement, l'outil de programmation que j'utilise n'est pas capable de traiter de si grands nombres (il ne traite que des integer et donc pas les virgules non plus ). Je dois donc trouver le moyen de décomposer ce sacré nombre de manière à trouver le même modulo.
Voici un exemple :
101230122127274567 modulo24 = 23 => comment trouver ce même résultat en ne travaillant que par groupe de 8 chiffres maxi... ça me paraît impossible mais je me trompe peux t-être.
Merci pour votre aide.

Fred

**méphistopheles** · 07/05/2007, 09h26

Bonjour

Au contraire, c'est tout à fait possible (8 chiffres seulement ?

quel langage limite à ça ? même VB c'est 24).

il te suffit de considérer le premier groupe de chiffres (dans ton exemple 10).

tu calcul 10 modulo 24= 10 puis tu multiplie par 10^4 (tu ajoute quatre zéros) et tu prend les quatre premiers chiffres du second octet (1230 de 12301221 dans ton exemple *) et tu les ajoute (tu obtient 101230) là tu calcule ton modulo (22) et tu recommence avec le deuxième morceau du second octet (1221 ) au quel tu ajoute le résultat précédemment obtenu *10^4 (soit comme résultat 221221) et tu recommence : 221221 modulo 24= 13
puis: 132727 modulo 24=7
puis: 74567 modulo 24=23

le résultat est donc 23 et tu à une méthode générale pour tout modulo qui ne dépasse pas 9999 (au delà, il faut prendre un décalage plus petit).

bonne chance

*Pour calculer le morceau d'un octet, il te suffit de prendre la partie entière de ce nombre divisé par 10^(numéro de la dernière décimale) (dans l'exemple: partie_entière(10^12)).

**Nemerle** · 09/05/2007, 15h00

Ce que dit Mephistopheles, c'est que

a*b [mod 24] = (a [mod 24]) * (b [mod 24]),
a+b [mod 24] = (a [mod 24]) + (b [mod 24]).

Dans le début de son exemple,

1012301221
= (101230*10^4)+1221
= ((10*10^4)+1230)+1221

et tu prends chacun des termes en [mod 24].

Autre façon, plus simple:

100 [mod 24]=4, et 10^n [mod 24] =16 pour tout n>2.
Donc, par exemple,

1012301221 [mod 24] = (1+0+1+2+3+0+1)*16+2*4+2*10+1 [mod 24]

!!!!

**pseudocode** · 09/05/2007, 20h16

Envoyé par Nemerle

100 [mod 24]=4, et 10^n [mod 24] =16 pour tout n>2.
Donc, par exemple,

1012301221 [mod 24] = (1+0+1+2+3+0+1)*16+2*4+2*10+1 [mod 24]

+1

C'est comme ca qu'on fabrique les fameux criteres de divisibilité (les regles du genre 'N est divisible par 3 si la somme de ses chiffres est divisible par 3").

**Nemerle** · 11/05/2007, 01h19

pseudocode:

**méphistopheles** · 11/05/2007, 19h27

Bravo nemerle, je connaissait pas cette methode (note ça dans un coin de classe)

**Nemerle** · 13/05/2007, 00h57

Envoyé par méphistopheles

(note ça dans un coin de classe)

gééé??

**méphistopheles** · 14/05/2007, 18h17

heu dans un coin de class*

**Nadd** · 23/08/2008, 17h02

Bonjour

Ne désirant pas créer un nouveau topic pour un sujet ayant déjà été traité, j'ai décidé de sortir ce topic vieux de plus d'un an pour vous demander quelques explications au sujet du calcul de modulo.

En fait, je me penche actuellement sur le cryptage RSA. J'ai ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Je dois calculer le reste de la division de 76^59 par 91, ce qui se note, je pense, comme ceci :

(76)^59 = x mod 91

La réponse attentue est 6 (donnée au cours et également par Maple). Toutefois, je ne parviens pas à tomber sur la méthode utilisée pour parvenir au reste : 6.

Je m'en remets donc à vous.

En vous remerciant d'avance,

Nicolas.

**oiffrig** · 23/08/2008, 18h36

Tu cherches n tel que 76^n soit congru à 1 ou -1 modulo 91, tu effectues la division euclidienne de 59 par n et tu décomposes :
59 = nq + r -> 76^59 = (76^r) * (76^n)^q

**rrk275** · 28/08/2008, 19h28

En math a la main tu chercherais effectivement un +1 ou un -1 mais en algo ce probleme ( qui se nomme exponentiation modulaire peut se resoudre en log2(puissance) operations ( si toutes les valeurs tiennent sur des variables de bases bien sur ;... )

Pour le resoudre on part des principes suivants

a^n = (a^(n/2))² en n'utilisant que des entiers c'est donc
Si n pair
-> a^n = a^(n/2)
sinon
-> a^n = a * a^[n/2]

comme le modulo conserve la multiplication on a donc par exemple :
76^59 modulo 91 = (((76^29) modulo 91)²*76) modulo 76 ( j'ai mis expres le modulo 2 fois pour montrer qu'on peut appliquer le principe recursivement )

cf google pour plus de precisions ... (http://fr.wikipedia.org/wiki/Exponentiation_modulaire)

Louis