Discussion:Exponentiation modulaire
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Logiciel
modifierEst-ce que quelqun pourrait proposer un logiciel d'exponentiation modulaire ? ( pour les nombre trop important qui nécessite d'effectuer en même temps l'exposant et le modulo)
mise en réserve
modifierne s'agit-il pas plutôt de la surcharge (overloading) permettant à des opérateurs distincts de partager le même symbole, dès lors qu'ils diffèrent par leurs profils d'appel (type opérande gauche, type opérande droit) ?? 90.48.132.8 (d) 27 septembre 2010 à 15:25 (CEST)
Petite erreur ?
modifierIl est écrit dans l'article (en ligne 6) :
"Si b, e, et m sont positifs et b < m, alors l'unique solution c existe et possède la propriété ."
or il me semble que c vérifie et non car on a trivialement : . Mais comme je n'ai aucune envie de faire d'erreur je tiens à avoir une confirmation.
Limitation de l'algorithme
modifierSi l'un des produits base*base ou result*base dépasse le plus grand Bignum le résultat de l'algorithme est incorrect. --86.69.15.13 (d) 24 décembre 2011 à 11:18 (CET)
==J'ai fait une implémentation en c++ de l'algorithme dit "Méthode la plus efficace". pour le type bignum, j'ai pris le type "unsigned long" (entier non signe sur 32bits), j'observe que si le produit p*q > 65535 (16 bits) alors l'algorithme ne fonctionne plus.
Petites remarques
modifier1) La première phrase après l'équation dans la première partie ne veut pas dire grand-chose : vous pouvez faire n'importe quelle opération sur des entiers modulo m, vous aurez toujours une solution unique comprise entre 0 et m - 1.
2) Le problème du logarithme discret consiste à trouver e à partir de c, b et m, et non b à partir de c, e et m comme il est écrit. C'est l'exposant l'inconnue.
- Bonjour, j'ai l'impression que peu de gens suivent cet article, je vous encourage à modifier vous même
.--Roll-Morton (discuter) 5 avril 2016 à 09:03 (CEST) PS : N'oubliez pas de signer vos messages en cliquant sur l'icône
au-dessus de votre fenêtre d'édition, ce qui ajoutera les quatre tildes --~~~~ et vos messages seront signés lorsque vous éditerez une page de discussion.
- A propos de la 1ère remarque "vous aurez toujours une solution unique comprise entre 0 et m - 1". Il s'agit seulement de préciser que c'est ce nombre entier c (et non pas c + m, ou c + 2.m) que l'on veut calculer. La précision est nécessaire dans la mesure où on a utilisé le signe congruent à pour définir l'exponentiation modulaire. Dans le texte anglais, c'est différent et il n'y a pas besoin de cette précision, puisque le modulo m est présenté comme le reste de la division par m, et que par suite le signe égal (égalité entre nombres entiers) est utilisé au lieu du signe congruent à (égalité entre classes d'équivalence). Le texte anglais est donc plus simple et plus efficace : il formule directement la valeur entière c que l'on veut calculer (et non pas une classe d'équivalence, dont ensuite on chercherait un représentant entre 0 et m). Une orientation "calculatoire" ou "informatique" adoptée dès le départ est plus simple que si l'on commence avec un orientation "congruence" ou "classe d'équivalence modulo m". Rester rigoureux rend alors le texte très "lourd" car il faut expliquer à la volée que l'on souhaite passer de la classe d'équivalence à son unique représentant entre 0 (inclus) et m (exclus).
- A noter que, sauf dans le cas inintéressant b = 0, si m est premier alors on aura toujours c > 0. Les applications en cryptographie se positionnent dans ce cas (et encore d'autres restrictions s'appliquent). Il n'y aura que m - 1 valeurs possibles pour c, non pas m valeurs possibles. On se trouve alors dans un groupe multiplicatif modulo m, non pas dans le groupe additif modulo m, et le nombre d'éléments de ces groupes n'est pas le même, parce que le groupe multiplicatif ne contient pas 0. Voir l'article Anneau ℤ/nℤ. JPB (discuter) 29 novembre 2021 à 22:57 (CET)
c ou e ?
modifierJe cite :
<<
Méthode utilisant moins de mémoire[modifier | modifier le code]
modifier[...]
L'algorithme suivant :
- Fixer c = 1, e' = 0.
- Augmenter e' de 1.
- Calculer .
- Si e' < e, aller à l'étape 2. Sinon, c contient la solution correcte de .
>>
Au 3. c'est pas c' ?
Au 4, c'est pas c'<c plutôt que e'<e
Désolé, j'ai pas passé trop de temps à lire, donc j'en sais rien. 90.32.241.160 (discuter) 30 novembre 2022 à 20:57 (CET)
c ou e ? suite
modifierpuisqu'on cherche e (et qu'on connaît b, c et m). 90.32.241.160 (discuter) 30 novembre 2022 à 21:02 (CET)