Modulo

[batch]

bonjours a tous, je suis lycéen mais je n'ai pas encore vu ce qu'était le "modulo"
et j'en ai besoin aujourd'hui pour un truc tout bête ( je créé une clef de chiffrement asymétrique )
j'aurais besoins de connaitre la méthode pour :

yx mod z =1
car pour l'instant je ne dois trouver que x pour :
3x mod 4 =1
ce qui ne nécessite pas beaucoup de maîtrise mais je devrais le faire avec des nombres du type 56198413216...
(un peu plus galère)
merci de votre aide !

[Ben314]

Salut,
La question telle qu'elle est posée à pas franchement de sens : une phrase qui commence par "...la méthode pour" ben forcément vaudrait quand même mieux qu'il y ait un verbe derrière pour qu'on comprenne le sens, non ?

Vu l'exemple donné ensuite, j'ai l'impression que la question est :
Pour et entiers fixés, quelle est la méthode pour trouver un entier tel que ?

Si c'est bien ça, la méthode classique utilisé que ce soit à la main ou en informatique, c'est l'algorithme d'Euclide étendu qui donne la réponse en O(ln(N)) itérations.

[batch]

merci de cette réponse mais ce serait plutot :
Pour a et N entiers fixés, quelle est la méthode pour trouver un entier x tel que : a*x mod N = 1 ?

[pascal16]

je pense que Ben a raison, sinon, y a plus simple : avec un tableur (attention à la limite des nombres entier) ou un programme informatique (et la classe décimal de Python ou Small basic si tu es trop limité)

l'équation n'a pas forcément de solution
avec a=2 et N paire, ça marche pas

[Ben314]

Sinon, ça :

et ça :

a*x mod N = 1 ?

C'est exactement la même chose.
La première notation (i.e. celle que j'utilise) est celle des matheux, avec un "égal à 3 barres" qui se prononce "congru" et un "modulo N" à la fin pour préciser le type de congruence (qu'on écrit aussi fréquemment sous la forme [N] avec des crochets)
C'est celle utilisé par tout les matheux et qui est on nepeut plus pratique vu les propriété de "stabilité" de la notion de congruence (et, plus ou moins vers le L2, on apprend comment faire pour que le "congru" devienne une vrai égalité via un passage au quotient).

L'autre notation (i.e. celle que tu emploie) est plus celle dédiée à l'informatique où l'opérateur en question peut être noté de différentes façon en fonction du langage :
- Soit mod pour certain d'entre eux (mais c'est assez crétin vu qu'étymologiquement parlant, si tu cherche dans un dico., le mot "modulo", ça a rien à voir avec un opérateur, ni en Français, ni en Anglais),
- Soit % pour d'autre,
- Ou encore rem comme "Reminder"="Reste" (ce qui semble bien plus logique vu que le résultat de l'opération, c'est effectivement le reste de la division Euclidienne)

P.S. : Faire attention aussi au fait que, comme il n'y a pas d'opérateur "reste de la division" en mathématique, je ne sais pas si tout les langages de programmations placent cet opérateur au même niveau de priorité (la plupart des langages le placent au même niveau que la multiplication et la division, mais je ne sais pas si c'est le cas de tous)

[batch]

merci beaucoup , meme si avec mon niveau actuel ça reste tres vague !

[Ben314]

Code: Tout sélectionner

fonction InverseModulaire(entier a ; entier N)
| entier q, U, Ud, V, Vd, temp
| U:=N; Ud:=a; V:=0; Vd:=1;
| tant que Ud>0 faire
| | q:=U div Ud; { div = quotient de la division Euclidienne }
| | temp:=Ud; Ud:=U-q*Ud; U:=temp
| | temp:=Vd; Vd:=V-q*Vd; V:=temp
| si non(U==1) alors retour -1
| tant que V<0 faire V:=V+N
| retour V


Invariant de boucle :
Sortie : une solution de s'il en existe et -1 s'il n'y a pas de solutions.