Modulo et nombre de 66 chiffres
velvetwizard
Messages postés
2
Date d'inscription
dimanche 17 février 2008
Statut
Membre
Dernière intervention
18 février 2008
-
17 févr. 2008 à 16:15
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
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
2 réponses
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
4
18 févr. 2008 à 14:17
18 févr. 2008 à 14:17
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
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
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
18 févr. 2008 à 22:05
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. . .
<?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. . .