Modulo et nombre de 66 chiffres

Messages postés
2
Date d'inscription
dimanche 17 février 2008
Statut
Membre
Dernière intervention
18 février 2008
- - Dernière réponse : velvetwizard
Messages postés
2
Date d'inscription
dimanche 17 février 2008
Statut
Membre
Dernière intervention
18 février 2008
- 18 févr. 2008 à 22:05
J'ai un problème à résoudre en C.


« faire un un pgm C permettant de donner le résultat de A mod X.
A étant un nombre de 66 et X= 1 à 100 »


1/ déjà je suis obligé de stocker ce nombre A dans tableau et de le découper en plusieurs parties car n'existe par de type de donnée pouvant stocker un nombre de 66 chiffres
2/ par contre comment faire le calcul du modulo ?


Je peux utiliser la fonction fmod ?!?
Je ne sais pas comment faire (pour que mon pgm C soit portable). Auriez vous une idée, svp ?
Afficher la suite 

2 réponses

Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2
0
Merci
Alors ca c'est tres simple,
supposons que tu memorises tes 66 chiffres dans un tableau T
(tu es en base 10) qui represente un nombre x dont tu cherches
le reste modulo 97 (prenons 97 pour l'exemple), alors on a les
relations suivantes :
x=somme sur i de 0 a 65 de T[i]*10^i

le truc c'est que ton resultat au final tiendra sur un entier de type int
puisque tu fais le calcul moldulo 100 au pire des cas.

Voici l'algorithme:
tu calcules les 10^i mod 97...
en fait tu calcules successivement ton nombre x, et a chaque etape
tu reduis ton nombre modulo 97, ainsi tous tes calcules intermediaires
seront sur des entiers
il te suffit d'adapter le principe de l'evaluation des polynomes de Horner
en faisant modulo 97 a chaque etape ! (l'evaluation se fait en 10)

donc regarde Horner et tu auras ta reponse !
(je pourrais te donner en fait la solution directement, mais je prefere
etre plus pedagogique qu'autre chose...)

cordialement JCDjcd
Commenter la réponse de cs_JCDjcd
Messages postés
2
Date d'inscription
dimanche 17 février 2008
Statut
Membre
Dernière intervention
18 février 2008
0
Merci
Si j’ai bien compris :



<?xml:namespace prefix o ns "urn:schemas-microsoft-com:office:office" /??>
 




Prenons le nombre 895602.


Ce qui donne dans le tableau T


T(0) = 2, T(1)=0, T(2)=6, T(3)=5, T(4)=9 et T(5)=8.



 




Appliquons la formule magique :



 




X(X + T(i)*10^i) mod 97 avec i0 à 5



 




Mais avec un nombre de 66 chiffres, on va avoir un problème en faisant 10^66.



 




Pour éviter ce problème, tu proposes de faire des étapes intermédiaires en utilisant la méthode de Horner…



 




Là, je sèche. . .
Commenter la réponse de velvetwizard