Discussion :

[Gotman-B]

Bonjour à tous, je vous expose mon problème :
je souhaite effectuer le calcul suivant : (nbcode^E mod(N)) et le pb est que lorsque les valeurs de a ou b (integer) sont trop élevé Delphi sature.
J'essaye donc de me servir des calculs de simplification des modulo
Voila ce que j'ai programmé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
   While E<>1 do
     begin
      If not Odd(E)
      Then
      Begin
       nbcode:=(puissance (Nbcode,2))mod N ;
       E:=E div 2;
      end
      Else
      Begin
       nbcode:=((puissance (Nbcode,2)mod  N)*aux)mod N;
       E:=E div 2;
      End;
 
     end;

Mais malheureusement ça ne marche pas
It doesn't work
Aidez moi SVP
merci d'avance

[didier2020]

si tu veux gagner en puissance, il y l'assembleur !
assembleur

[Gotman-B]

En faite c'est lorsque delphi fait Nbcode^E que ça sature.
C'est pour ça que je me sert des formules du genre :
(a*b)mod n = ((a mod n)*(b mod n)) mod n

[Masterglob]

D'abord méfie toi de ta condition de sortie (while e <>1) car (e=0 par exemple, ou e<0) fera planter ton appli.
Ensuite que vaut Aux? (Valeur initiale de nbcode j'imagine)

Ensuite, si nbcode ou N est supérieur à sqrt(2^32) tu auras toujours un problème de débordement,

Quelle est la valeur de N?

Sinon à quoi ca te sert de faire puissance (..,2)? alors que tu as dit toi eme que tu utilisait un algo de type (x mod n) * (x mod n)

plutot un truc genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
While E<>1 do
begin
  nbCodeMod = nbcode mod N ;
  If not Odd(E)
  Then
  Begin
    nbcode:=(nbCodeMod * nbCodeMod )mod N ;
  end
  Else
  Begin
    nbcode:=(nbCodeMod * nbCodeMod *aux)mod N;
  End;
  E:=E div 2;
end;

PS utilise les balises [ CODE] [ /CODE ]

[Gotman-B]

merci beaucoup de t'être penché sur mon problème.
Je vais maintenant essayer ce que tu me propose

[CapJack]

Pour repousser les limites, pense aussi au type Int64 (entier 64 bits) !

Par ailleurs, si n n'est pas trop grand, il faudrait peut-être se pencher sur la fabrication en amont d'une table de multiplication modulo n... outre que celà repousse aussi la limite, puisqu'une telle table peut facilement se remplir par de simples additions, donc sans vraie limite supérieure, on pourrait avoir un gain de performance non négligeable puisqu'il n'y aurait plus d'appel aux routines de division du processeur !