Bonjour,
Je ne comprends pas cet algorithme qui calcule l'ordre d'un nombre entier premier avec 29 : pourquoi on multiplie le nombre x par le reste de la division euclidienne de x par 29 ?
Il faudrait faire le reste de la division euclidienne de x par 29. Puis le reste de la division de x^2 par 29. etc ... Jusqu'à obtenir 1. Je comprends rien à cet algo.
Bonjour
C'est simple: tu fais une boucle avec un tant que.
Tu calcules au fur et à mesure le reste modulo 29 de x^k en utilisant le reste précédent (pour éviter de faire exploser la machine)
et tu sors quand ce reste =1.
Salut JB merci pour la réponse !
Je teste sur un exemple pour avoir les idées plus claires.
Je prends :on a :
On a
Puis on entre dans la boucle car
On doit effectuer :
On a bien j'ai vérifié :
Quelle propriété mathématique on utilise ici qui donne :
Tu peux faire ici pour une fois dans ta vie une démonstration par toi même.
Oui vous avez raison j'ai trouvé !
On a le droit de multiplier une congruence par n'importe quel nombre on utilise la propriété :
Donc dans l'exemple :
Donc
Et ainsi de suite...
en toute rigueur, l'algorithme doit tester ses entrées et vérifier que x est premier avec 29.
Sinon N=0, et on voit facilement que le programme boucle sans jamais s'arrêter. Ce qui n'est jamais bienvenu en informatique...
There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.
Ah j'avais pas fait attention à ça bien vuEnvoyé par jacknicklaus
