Powmod( ) problème

[dheroux]

Bonjour,

Powmod(3,346 111 643,346 111 643) donne pour résultat 3

Or une procédure que j'ai écrit en VB Net 2010 me donne comme résultat 150 180 452 et non 3. Cette procédure est en parfait accord avec Powmod SAUF pour ce cas particulier.
J'ai écrit également cette procédure sous Excel 2013, qui me donne encore 150 180 452.


Voir mon document récapitulatif:
http://www.dheroux.net/Modulo.txt

Merci.

[Cheval]

Bonjour,
juste pour info, Maxima avec la fonction équivalente power_mod donne le même résultat que Xcas, à savoir 3
et Xcas, avec la commande
irem(3^346111643,346111643)
répond :
"Exponent overflow Erreur: Valeur Argument Incorrecte"
Mais je suppose que powmod a un algo optimisé par rapport à cette dernière commande…

[parisse]

Et la réponse de Xcas et Maxima est juste puisque p=346111643 est premier donc a^p=a mod p.
L'algorithme en VB n'est pas très simple, difficile de savoir où est l'erreur, peut-etre un overflow sur les entiers?
Une remarque on n'a pas besoin de calculer à l'avance la décomposition en base 2 de l'exposant, on peut le faire en même temps par division euclidienne de l'exposant par 2.

Code : Tout sélectionner

f(a,n,p):={
  local a2p,res;
  res:=1;
  a2p:=a;
  tantque n!=0 faire
    si irem(n,2) alors res:=irem(res*a2p,p); fsi;
    a2p:=irem(a2p*a2p,p);
    n:=iquo(n,2);
  ftantque;
  retourne res;
}:;