Algorithme

[mehdi-128]

Bonjour,

Il existe un plus petit entier naturel non nul tel que et que cet entier est inférieur ou égal à . Cet entier s'appelle l'ordre de et on le note

Je dois écrire un algorithme permettant de calculer l'ordre d'un nombre entier premier avec .

Je dirais il faut taper x et initialiser l'ordre à 1 , puis faire la division euclidienne de x par 29 et prendre le reste et vérifier s'il est égal à 1. Sinon on fait et on divise par 29 et on regarde le reste. Tant que le reste ne vaut pas 1 on incrémente l'ordre.

Je tente de faire l'algo mais j'ai un souci il est incomplet je n'arrive pas à intégrer le reste dans la boucle tant que pour vérifier qu'il es différent de 1.


Taper


Tant que


Fin tant que

Rendre

[aviateur]

bjr
Tu calcules le reste s'il est égal à 1, tu arrêtes la boucle et tu sors le résultat.

[mehdi-128]

Je vois mais une chose me chagrine. On choisit la valeur de

Au début je calcule le premier reste : (je calcule le reste de la division euclidienne de par )

Je rentre dans la boucle si le reste est différent de 1, je calcule

Mais quelle est la relation entre et ?

Parce que mon reste est initialisé à et j'aimerais passer à en utilisant comment faire ?

[FLBP]

Pour les n premiers tu peux t'aider du petit théorème de fermat

[mehdi-128]

Pour tout entier relatif premier avec on a :

Mais quel est le rapport avec l'algorithme permettant de calculer l'ordre de ? Je vois pas

Je dois calculer tel que
Puis tel que

[aviateur]

Donc 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.

[mehdi-128]

Donc 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.

Merci j'ai compris