modulo et nombre de 66 chiffres

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 ?

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

Si j'ai bien compris :

 

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 i =0 à 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. . .