Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

Algorithme : Calcul rapide des puissances modulo n

Posté par
kadile
24-11-16 à 19:45

Bonjour
Voici un algorithme qui est censé calculer a^m modulo n, même pour les grandes puissances que la calculette affiche "infini"
Algorithme trouvé sur internet.

Fonction puissance(a,m,n) // entier, exposant, module
R ← 1 ;
Tant que (m > 0) faire
Si (m est impair) Alors
R ← (R × a)mod n ;
Fin Si
a ← (a × a)mod n ;
m ← m/2 ; // la division par 2 est un d´ecalage binaire (shift)
Fait
Retouner R;

Je l'ai transcrit en basic sur ma Ti-spire cas mais ça boucle à l'infini.
C'est normal car la condition m>0 est toujours valide pour l'instruction while

Merci pour vos commentaires

Posté par
cocolaricotte
re : Algorithme : Calcul rapide des puissances modulo n 24-11-16 à 19:49

Bonjour,

Une machine ne sait pas tester si m est impair  ou pas

Il faut l'aider un peu.

Posté par
cocolaricotte
re : Algorithme : Calcul rapide des puissances modulo n 24-11-16 à 19:50

De plus le nombre a n'étant pas initialisé, il peut valoir n'importe quelle valeur ou 0 selon la machine et le langage utilisé.

Posté par
cocolaricotte
re : Algorithme : Calcul rapide des puissances modulo n 24-11-16 à 19:54

si m > 0 alors m/2 sera aussi > 0

Cet algorithme a donc toutes les chances de ne pas donner ce qui est attendu !

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 24-11-16 à 19:56

Bonjour,

la division de 1 par 2 devrait donner 0 si on la faisait en nombres entiers (et reste 1)
garantissant que l'algorithme se termine (sur m = 0)

le calcul de m/2 par contre calcule en nombres "réels" et donne 0.5 et ce sans fin avec des m tendant vers 0 sans jamais l'atteindre

si m est impair il faut calculer (m-1)/2
et si m pair m/2

de toute façon il est nécessaire que m se représente par un nombre entier en machine et donc "pas trop grand"
(sinon ça fait absolument n'importe quoi, un algorithme sur des nombres entiers calculés en virgule flottante)

Posté par
cocolaricotte
re : Algorithme : Calcul rapide des puissances modulo n 24-11-16 à 20:03

Mea culpa sur le "a" c'est un paramètre passé à cette fonction donc connu.

Mes autres remarques rejoignent celles de mathafou que je salue.

Posté par
kadile
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 11:18

Bonjour

Voici ma fonction
frest(a,m,n)
local r
r:=1
:While m>0
:If mod(n,2)≠0 Then
: r:=mod(r*a,n)
:EndIf
:a:=mod(a*a,n)
:m:=m/2
:EndWhile
return r

Posté par
cocolaricotte
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 11:41

Revoir nos remarques sur la division de m par 2 cela ne donnera jamais 0.

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 11:59

toujours la même erreur sur le calcul de m/2 qui si m est impair ne donne pas un nombre entier ce qui ruine complètement le fonctionnement de l'algorithme. (boucle sans fin et résultats imprévisibles vu que l'algorithme est conçu avec que des nombre entiers à tout instant)

(déja signalée)

soit on fait un calcul différent selon que m est pair ou impair comme déja dit
soit on calcule la partie entière de m/2

m:=int(m/2) ou du même genre selon la façon dont on écrit "partie entière de" sur la calculette en question.

de plus c'est pas n mod 2 qu'il faut tester
mais m
(si m est impair dans l'énoncé d'origine)

le but principal de la boucle est d'obtenir en binaire les chiffres de m en commençant par les poids faibles

tant que m > 0 (différent de 0)
si m est impair le bit vaut 1, remplacer m par (m-1)/2
sinon le bit vaut 0, remplacer m par m/2

algorithme général de décomposition d'un nombre en base quelconque (ici 2)
tant que m > 0 (différent de 0)
le chiffre vaut r = m%b, remplacer m par (m-r)/b (m%b est le reste de la division de m par b)

on utilise alors cette décomposition en binaire "latente" (non explicitement produite) de m pour décomposer le calcul de la puissance en élévations au carré (passage au bit suivant) et en multiplications par a (si le bit vaut 1)

Posté par
kadile
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 12:35

Merci mathafou pour les explications mais cela me dépasse un peu!

Oui, comme tu dis, il faut tester m si impair et non le modulo n. C'était une erreur de frappe de ma par!

Voici la fonction, elle marche. J'ai mis un compteur pour sortir de la boucle dans le cas ou ça boucle indéfiniment!

r:=1:compteur:=0:While m>0isp m:If mod(m,2)≠0 Then: r:=mod(r*a,n):m:=m-1:EndIf: a:=mod(a*a,n): m:=((m)/(2)): Disp m:: compteur+1→compteur: If compteur>200 Then:    Disp "Exit":          Exit:         EndIf:    EndWhile:Return r

Posté par
cocolaricotte
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 12:50

Illisible !

r:=1
:compteur:=0
:While m>0
????????????isp m
:If mod(m,2)≠0
Then
   : r:=mod(r*a,n)
   :m:=m-1
:EndIf
: a:=mod(a*a,n)
: m:=((m)/(2))
: Disp m
: compteur+1→compteur
: If compteur>200
Then:    Disp "Exit"
    :Exit:        
EndIf
: EndWhile
:Return r

Si tu es obligé(e) d'utiliser un subterfuge (compteur) au cas où ton programme bouclerait, c'est que ton algorithme n'est pas bon !

Avant d'écrire un programme dans un langage, quel qu'il soit, il faut écrire un algorithme qu'on teste à la main sur un exemple dont on connait la réponse.

Posté par
cocolaricotte
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 12:51

On t'a déjà dit que ton algo ne donnait pas la réponse à ton problème. Il faut revoir l'algo.

Posté par
cocolaricotte
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 13:15

Je rajouterai qu'avant de se lancer dans un algorithme, il faut essayer de faire à la main un exemple, pas trop long, pour se donner un aperçu des étapes à réaliser.

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 13:31

Oui avec l'ajout de m:=m-1 dans le cas "si m impair" ça fait ce que j'avais dit : calcul de (m-1)/2 si m impair et de m/2 si m pair.

OK
nota : j'ai eu du mal à lire ce fatras sans retours à la ligne, le m:=m-1 a failli passer inaperçu ...)

note importante :
cet algorithme ne fonctionne que du moment que m est un nombre entier
un nombre "trop grand" ne fonctionnera donc pas car ce n'est pas représenté comme un nombre entier en machine.

par exemple la calcul de 7^(31^47) modulo n ne marche pas car 31^47 n'est pas un nombre entier en machine
c'est représenté comme "à peu près" 1.241651 10^70

les explications concernaient le fonctionnement intime de l'algorithme, ce qu'il fait vraiment et pourquoi.
si on te demandait dans l'énoncé un algorithme et si tu proposes celui là c'est que tu l'as toi même conçu, ou tout au moins que tu en comprends le fonctionnement et pourquoi il fonctionne.
donner un truc extrait de Internet comme réponse ne vaudra donc pas grand chose comme note ...
il en est différemment si on ne te demande pas un tel algorithme mais si tu cherches juste à l'avoir pour l'utiliser.

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 13:33

cocolaricotte : j'ai faille répondre pareil avant de déceler ce petit "m:=m-1" caché dans le magma ...

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 13:33

* failli

Posté par
cocolaricotte
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 13:34

Je dois avouer que je n'ai fait que mettre des retour à la ligne et que je n'ai rien lu !

Posté par
kadile
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 19:16

Bonjour

Citation :
donner un truc extrait de Internet comme réponse ne vaudra donc pas grand chose comme note ...
il en est différemment si on ne te demande pas un tel algorithme mais si tu cherches juste à l'avoir pour l'utiliser.


Ce n'est pas du tout un travail demandé par un prof ou autre, c'est juste pour mon usage personnel!

Citation :
un nombre "trop grand" ne fonctionnera donc pas car ce n'est pas représenté comme un nombre entier en machine.

par exemple la calcul de 7^(31^47) modulo n ne marche pas car 31^47 n'est pas un nombre entier en machine
c'est représenté comme "à peu près" 1.241651 10^70


Voici le résultat:
frest(7,31^47,4)
affichage :r=3

On dirait qu'il calcule 7 modulo 4 et laisse tomber la puissace 31^47

Donc il faut chercher autre chose pour ce cas mais ce n'est pas pour moi!

Merci pour tout.

Posté par
cocolaricotte
re : Algorithme : Calcul rapide des puissances modulo n 25-11-16 à 19:23

Avant de se lancer dans un algorithme, il faut essayer de faire à la main un exemple, pas trop long, pour se donner un aperçu des étapes à réaliser.

Et avant d'écrire un programme dans un langage, quel qu'il soit, il faut écrire un algorithme qu'on teste à la main sur un exemple dont on connait la réponse.

User d'un artifice comme un compteur pour éviter une boucle infinie n'est pas une solution admissible.

Posté par
kadile
re : Algorithme : Calcul rapide des puissances modulo n 26-11-16 à 11:18

Bonjour

Citation :
Et avant d'écrire un programme dans un langage, quel qu'il soit, il faut écrire un algorithme qu'on teste à la main sur un exemple dont on connait la réponse.

D'accord avec toi!

Citation :
User d'un artifice comme un compteur pour éviter une boucle infinie n'est pas une solution admissible.

Le compteur, dans ce cas, me sert pour une mise au point...Je pense que c'est rare les gens qui réussissent un programme du premier coup!
Ce n'est pas ma parole mais c'est celle de certains programmeurs. Bien sûr cela dépend de la difficulté du travail.
Etant amateur, je fais ce que je peux!
Bien entendu, si c'était un travail qui m' a été demandé et à rendre, le compteur ne figurera pas.

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 26-11-16 à 12:46

pour info :

7^(31^47) modulo 4 (comme exemple)

il est d'abord nécessaire de réduire 7 modulo 4, effectivement : 7^n ≡ 3^n [4] quel que soit n

on est donc amené à étudier de plus près les restes de 3^n modulo 4

3^1 ≡3 [4]
3^2 = 9 ≡ 1 [4]
et donc les restes successifs seront éternellement 3, 1, 3, 1 etc (périodiques)

il faut alors trouver le reste de 31^47 modulo 2 (modulo la longueur de la période) pour savoir où se situe dans cette période l'exposant 31^47

il est évident qu'il s'agit d'un nombre impair (sans calcul) et donc 7^(31^47) ≡ 3^1 [4]

le résultat fourni par le programme est donc "miraculeusement juste"

pour un test plus réaliste il faudrait par exemple tester modulo 13 (pourquoi ? parce que 13 est un "nombre premier long" on a donc toutes les chances que la période sur les exposants soit elle aussi longue)

calculons les puissances successives de 7 modulo 13
7^1 ≡ 7 [13]
7^2 = 49 ≡ 10 [13]
7^3 = 7*7^2 ≡ 7*10 = 70 ≡ 5 [13]
7^4 = 7*7^3 ≡ 7*5 = 35 ≡ 9 [13]
7^5 = 7*7^4 ≡ 7*9 = 63 ≡ 11 [13]
7^6 = 7*7^5 ≡ 7*11 = 77 ≡ 12 [13]

on va arrêter là car 12 ≡ -1 [13] et les restes suivants seront les opposées des restes déja calculés
jusqu'à
7^12 = (7^6)^2 ≡ (-1)^2 = +1 [13]

la période des restes de 7^n modulo 13 est donc 12 (comme on pouvait l'espérer d'un nombre premier long)
et il faut étudier le reste de 31^47 modulo 12
ce qui est tout à fait à la portée du programme
ou peut se faire à la main

plutot que de le calculer effectivement, je vais ici le déduire par une méthode semblable à la précédente :
31 ≡ 7 [12]
7^1 ≡ 7 [12]
7^2 ≡ 1 [12] (c'est ici très rapide)
la période est donc 2 et il suffit de calculer le reste de 47 modulo 2, qui est "visiblement" 1
donc
31^47 ≡ 7^47 ≡ 7^1 [12]

on peut donc affirmer en revenant au problème initial que

7^(31^47) ≡ 7^7 [13] en "réduisant" l'exposant 31^47 modulo la période 12
on a déja la liste de ces valeurs dans le tableau fait au début

7^6 ≡ 12 ≡ -1 [13]
7^7 = 7*7^6 ≡ 7*(-1) = -7 ≡ 6 [13]

et donc la conclusion de ce calcul fait entièrement à la main est que

7^(31^47) ≡ 6 [13]

(fait entièrement à la main = sauf erreur de calcul)

Posté par
kadile
re : Algorithme : Calcul rapide des puissances modulo n 26-11-16 à 17:42

Ce que tu as fait est très intéressant car je n'ai jamais eu affaire à ce genre de congruence, mais je vais le reprendre à la main pour m'entrainer.

Ton calcul est confirmé par le programme:
frest(7,31^47 ,13)
r=6

Par contre, directement à la calculette:
mod( 7^(31^47) ,13)
affichage: (infini,13)

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 26-11-16 à 18:36

le programme affiche en vrai n'importe quoi :

trace des opérations (fait avec Algobox)

***Algorithme lancé***
Entrer a : 7
Entrer m : pow(31,47)
Entrer n : 13
m=1.2416511931816992e+70, a=10, m/2=6.208255965908496e+69
m=6.208255965908496e+69, a=9, m/2=3.104127982954248e+69
m=3.104127982954248e+69, a=3, m/2=1.552063991477124e+69
...
etc des paquets de valeurs fantaisistes car approchées et pas exactes de m
...
m=2.1239305544831444e+21, a=3, m/2=1.0619652772415722e+21
m=1.0619652772415722e+21, a=9, m/2=530982638620786100000
m=530982638620786100000, a=3, m/2=265491319310393050000
m=265491319310393050000, a=9, m/2=132745659655196520000
m=132745659655196520000, a=3, m/2=66372829827598260000

calcul visiblement faux puisque ça devrait donner
m=132745659655196525000

m=66372829827598260000, a=9, m/2=33186414913799130000
m=33186414913799130000, a=3, m/2=16593207456899566000
m=16593207456899566000, a=9, m/2=8296603728449783000
...
m=129634433257027860, a=3, m/2=64817216628513930
m=64817216628513930, a=9, m/2=32408608314256964

les valeurs de m ne sont des valeurs entières que à partir d'ici
les calculs suivants sont donc justes, mais à partir de valeurs fausses

m=32408608314256964, a=3, m/2=16204304157128482
m=16204304157128482, a=9, m/2=8102152078564241
m=8102152078564241,impair, r=9, m-1=8102152078564240, a=3, m/2=4051076039282120
m=4051076039282120, a=9, m/2=2025538019641060
m=2025538019641060, a=3, m/2=1012769009820530
m=1012769009820530, a=9, m/2=506384504910265
m=506384504910265,impair, r=3, m-1=506384504910264, a=3, m/2=253192252455132
m=253192252455132, a=9, m/2=126596126227566
m=126596126227566, a=3, m/2=63298063113783
m=63298063113783,impair, r=9, m-1=63298063113782, a=9, m/2=31649031556891
m=31649031556891,impair, r=3, m-1=31649031556890, a=3, m/2=15824515778445

etc (je coupe)

m=115,impair, r=3, m-1=114, a=3, m/2=57
m=57,impair, r=9, m-1=56, a=9, m/2=28
m=28, a=3, m/2=14
m=14, a=9, m/2=7
m=7,impair, r=3, m-1=6, a=3, m/2=3
m=3,impair, r=9, m-1=2, a=9, m/2=1
m=1,impair, r=3, m-1=0, a=3, m/2=0
3
***Algorithme terminé***

tous les calculs effectués du début sont totalement fantaisistes vu que les nombres traités ne sont pas des nombres entiers mais des valeurs approchées

il ne calcule en fait sincèrement que à partir du moment où ce n'est plus des valeurs approchées (en e+ quelque chose) mais des valeurs exactes (fausses vu qu'elles dérivent des valeurs approchées précédentes)

il calcule donc en fait 7^32408608314256964 seulement et encore vu que la valeur de a et de r n'est pas franchement la bonne à ce moment

de toute façon, au premier passage 31^47 étant visiblement un nombre impair on devrait passer dans le "si "
or on n'y passe pas !!

il suffit de demander 7^(31^47+1) pour voir que c'est aberrant puisque ça devrait donner 7*3 = 21 ≡ 8 [13]
alors que ça donne toujours 3 !!

si tu programmes cet algorithme avec un logiciel qui calcule avec une précision "infinie" (avec des nombres aussi grands qu'on veut = tant qu'il y a de la place sur le disque dur, en tera-octets de nos jours)
par exemple avec XCas il en serait différemment
il faut faire tous les calculs avec au moins 72 chiffres significatifs exacts pour m vu qu'il en faut 71 pour écrire la valeur exacte de 31^47, un de plus pour avoir une petite marge.
donc demander cette précision à Xcas

il fera environ 200 boucles vu que 31^47 s'écrit avec environ 200 chiffres binaires

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 26-11-16 à 18:47

à corriger avec les valeurs réellement obtenues (j'ai pris un "3" sans relire les messages précédents)

7^(31^47) ≡ 6 [13] (calcul théorique exact) c'est Algobox ( = JavaScript) qui prétendait que c'est 3

7^(31^47 +1) devrait donner 42 ≡ 3 [13]

la vérification du fonctionnement correct avec ces grands nombres du programme nécessite donc de lui demander aussi 7^(31^47 +1)
pour vérifier que pour lui 31^47 +1 et 31^47 sont bien des nombres différents (qu'il fait ses calculs avec suffisamment de précision pour en connaitre et utiliser la valeur exacte)

ou de vérifier dans la doc du logiciel que c'est vrai (= la précision avec laquelle il fait les calculs)

Posté par
kadile
re : Algorithme : Calcul rapide des puissances modulo n 26-11-16 à 19:29

mon programme confirme que:
7^(31^47 +1)  ≡ 3 [13]

Ma calculette affiche tous les chiffres de  31^47

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 26-11-16 à 19:45

tu as une calculette qui affiche 70 chiffres exacts ??? c'est quelle marque ? une fabrication spéciale ?

31^47 = 12416511931816993664430704668956488110455919221367335034994587979129311

Citation :
Par contre, directement à la calculette:
mod( 7^(31^47) ,13)
affichage: (infini,13)
est en contradiction totale avec
Citation :
Ma calculette affiche tous les chiffres de 31^47
c'est à dire les 70 chiffres au dessus ?

si c'était le cas, elle calculerait correctement mod( 7^(31^47) ,13)


ton programme il est en quoi (quel logiciel) ?

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 26-11-16 à 19:49

pardon je n'ai rien dit
mod( 7^(31^47) ,13) lui ferait calculer 7^(31^47) qui a bien plus de 70 chiffres !

il n'empêche que une calculette qui affiche 70 chiffres, je ne connais pas.

Posté par
kadile
re : Algorithme : Calcul rapide des puissances modulo n 27-11-16 à 18:08

J'ai une TI-nspire Xcas et le logiciel Xcas student software fourni avec la calculette.

Ton résultat:
31^47 = 12416511931816993664430704668956488110455919221367335034994587979129311

Le résultat de mon logiciel Xcas student software :
31^47=
12416511931816993664430704668956488110455919221367335034994587979129311

La calculette donne le même affichage.

Bien sûr  pour mod(7^(31^47),13 elle affiche (infini,13)

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 27-11-16 à 18:13

oui, avec le logiciel Xcas OK.

Posté par
kadile
re : Algorithme : Calcul rapide des puissances modulo n 27-11-16 à 18:54

Citation :
oui, avec le logiciel Xcas OK.


Et aussi la calculette donne:
31^47 = 12416511931816993664430704668956488110455919221367335034994587979129311

je l'ai déjà précisé! A moins que je n'ai pas compris ta réponse.

Posté par
kadile
re : Algorithme : Calcul rapide des puissances modulo n 27-11-16 à 18:56

Je rectifie:
Et aussi la calculette donne, en mode calcul (sans le programme) :
31^47 = 12416511931816993664430704668956488110455919221367335034994587979129311

Posté par
mathafou Moderateur
re : Algorithme : Calcul rapide des puissances modulo n 27-11-16 à 19:15

oui, oui...
on n'arrête pas le progrès avec ces calculettes de plus en plus puissantes



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !