fonction qui calcule le resultat de g^x mod p

Bonsoir je dois réaliser une petite fonction qui calcule le resultat de g^x mod p

x on le transforme de nombre en binaire

le probleme c'est que pour les petits resultats cela fonctionne comme 358^248 mod 13 = 6

mais on nous a demandé de possèder ce resultat pour cet exemple là :
modPow(-2, -12345, 1073741827) == 11418853 et j'obtiens 1

La raison est apparament d'après l'énoncé :

Citation:

---

Si vous n’obtenez pas ce résultat, l’un des problèmes possibles est dû à un dépassement de la précision des long : vous n’avez pas systématiquement réduit modulo p.

---

Mais je vois pas du tout.
Merci de votre aide

Bonjour,

dans ton code tu dis : tant que x > 0 ....., or dans l'exemple qui ne fonctionne pas x < 0 donc on sort de la boucle et a vaut 1.

A la sortie de la boucle on retourne le reste de 1 divisé par p soit 1.

vérifie que la "Russian Peasant's method" fonctionne avec les nombres négatifs

-2^-12345 = 1 / (-2 ^ 12345), ça dois valoir quelques millionièmes de milliardièmes de je ne sais pas quoi. On est bien loin derrière la virgule, ça ne pourra jamais tenir dans un nombre entier puisque ce résultat n'est pas entier. Tu est sûr que l'énoncé ne met pas plutôt -2 et +12345 ???


De plus, il faut savoir que, en java, le modulo ne tiens pas compte du signe. -1 %3, c'est -1, alors qu'en mathématique, parfois, on considère que -1%3 = 2. A voir ce que ton prof entends par le modulo d'un nombre négatif.

Merci de vos réponse,

Nan le prof ne s'est pas trompé l'énoncé est ici :
http://apollinaire.prism.uvsq.fr/Pas...e%20g%C3%A9ant

Question 3

La question précédente on fait l'inverse , 1/x mod n donc je pense que je vais faire g^-x mod n = 1/(g^x) mod n = (1/g)^x mod n

edit : enfaite je pense avoir trouvé mais je dois comprendre pourquoi j'ai faux sur mon résultat :


pour avoir 1/g^x mod n je dois l'obtenir à partir de l'inverse 1/g mod n *-x (-x car le x de l'exemple est négatif )

car 1/g * 1/g =1 /g^2 etc. j'usqu'a x

Donc j'ai fait :

inverse(g,p)*-x
Mais c'est dans la formule ou j'ai du me tromper et je vois pas ou

edit : je le multiplie pas par lui même ça va pas aider

Merci lucho , les deux méthodes fonctionnes.