Den MOD per Hand berechnen! -> falsches Ergebnis!!!!

[Kamikaze87]

Hi Leute


ich sehe mich wieder mal vor ein problem gestellt wo ich den fehler nicht finde!!!!

also ich habe drei zahlen die nach rsa entschlüsselt werden soll

299 soll mit 173 und 481 entschlüsslt werden!!!

Also 299^173 MOD 481 = entschlüsselt .

es gibt aber folgendes problem und zwar das 299^173 eine für longint zu hohe zahlen rauskommen deshalb habe ich den extended benutzt weil ich nur mit delphi3 programmiere und int64 da noch nicht vorhanden sind...


also lasse ich den mod per hand berchnen da er sonst nur für integer konzipiert ist:
achso und 299^173 ist schon mit einer weiteren prozedur berechnet und heisst bei mir 'k1'.
b:=481;

Delphi-Quellcode:

  a:=k1/b;
          a:=fract(a);
          a:=a*b;
          a:=round(a);

und für genau die zahlen wie oben schon angegeben kommt bei mir für a=0 raus was nicht stimmt es müsste nämlich 65 rauskommen......das funktioniert sogar wenn ich das mit dem windows taschenrechner berechne!!!!
könnt ihr mir helfen??????


ich hoffe die infos reichen
wenn nicht meldet euch!!!

DAnke schon mal im voraus für eure Hilfe!!!!

MFG
Kamikaze

[shmia]

Zitat von Kamikaze87:

es gibt aber folgendes problem und zwar das 299^173 eine für longint zu hohe zahlen rauskommen deshalb habe ich den extended benutzt

Fliesskommazahlen (double, Extended) kann du bei dieser Aufgabe grundsätzlich vergessen.
Du musst bei Integerarithmetik bleiben!
299^173 ist 299*299*299*...299 (173 Faktoren)
Das ist eine riesige Zahl!!
Es gibt nun sicherlich mathmatische Möglichkeiten a^b mod c auszurechnen ohne dass man
die Zahl a^b wirklich berechnet.
Tipp: die einzelnen Multiplikationen und Modulooperationen lassen sicher verschachteln. Dabei wird der Integerbereich nie verlassen.

[3_of_8]

Das hatten wir vor kurzem schon mal. Such einfach nach "Diskrete Exponentialfunktion". Da ist ein schöner, langer Beitrag von mir mit einem Beispiel.

EDIT: Ich hab heute gute Laune und geb dir deshalb gleich den Link: http://www.delphipraxis.net/internal...=675294#675294

[alcaeus]

Moin,

kurz gesagt: du brauchst keinen Extended oder aehnliches. Im Gegenteil: du musst nur die Integer-Zahlen abspeichern koennen, mit denen du arbeitest, und sonst nichts. Schliesslich ist

Code:

a^b % c

auch zu umschreiben als

Code:

((a^(b-1) % c) * (a % c)) % c

Wir haben also eine rekursive Gleichung, die du mit einigen Optimierungen auf die Variante aus Wikipedia zurueckfuehren kannst. Wenn du das also bis ans Ende fortfuehrst, wirst du kein einzges Mal eine Potenz berechnen muessen.

Greetz
alcaeus

[JasonDX]

Zitat von 3_of_8:

Das hatten wir vor kurzem schon mal. Such einfach nach "Diskrete Exponentialfunktion". Da ist ein schöner, langer Beitrag von mir mit einem Beispiel.

EDIT: Ich hab heute gute Laune und geb dir deshalb gleich den Link: http://www.delphipraxis.net/internal...=675294#675294

Zitat von 3_of_8:

Code:

function discreteExponent(b, x, m: Integer): Integer;  
begin  
  result:=1;  
  while x>0 do  
  begin  
    if x and 1=1 then Result:=Result*b mod m;  
    b:=[b](b*B)[/b] mod m;  
    X:=x div 2;  
  end;
end;

Bei 299^173 MOD 481 geht das noch gut, wenn man allerdings (wie bei RSA so ueblich ist) mit grossen Zahlen rechnet, duerfteste mit der Funktion ziemlich dumm aussehn.
In einer sache hast du aber recht: sowas hatten wir letztlich schon: *klick*
D.h. eigentlich wie alci schon geschrieben hat:

Code:

(a ^ b) % c = ((a^(b-1) % c) * (a % c)) % c

vllt. stell ich heut noch ne nicht-rekursive Gleichung dafuer auf.

greetz
Mike

[XooL]

hi,
ich hab das ganz ähnliche Problem...
ich habs auch mal mit der Gleichung ausprobiert allerdings: wie soll dazu der rekursive Rahmen aussehen ?

mfg

[Corpsman]

Ich habs nu nicht ganz Geblickt,

aber ich Poste euch mal wie ich das mache.

Delphi-Quellcode:

Function XHochYModZ(x, y, z: integer): Integer;
Var
  i, e: INteger;
Begin
  e := 1;
  For i := 1 To y Do
    e := (e * x) Mod z;
  result := e;
End;

Ich hoffe das hilft.

[XooL]

vielen Dank... manchmal hat man einfach n Brett vorm Kopf...

[Jerk]

Evtl liegt es an dem Div 2 weil das doch noch mit graden zahlen funktioniert. Teste mal it x*0.5.

Edit hat sich ja schon gelöst...

[negaH]

Delphi-Quellcode:

Function XHochYModZ(x, y, z: integer): Integer;
Var
  i, e: INteger;
Begin
  e := 1;
  For i := 1 To y Do
    e := (e * x) Mod z;
  result := e;
End;

Das ist defakto inpraktikabel und ineffizient. Wir führen damit Y mal eine modulare Multiplikation aus. Und stelle dir vor Y wäre wie bei RSA üblich circa 2^1024 groß.

Der Vorschlag von 3_of_8 ist da schon weitaus besser. Dieser führt im Durchschnitt Ln2(Y) mal eine modulare Multiplikation und Ln(Y)/2 eine Quadrierung durch wenn man nicht wie sein Vorschlag die Rechts nach Links Methode sondern die Links nach Rechts Methode anwendet. Ich kenne das aber und einen anderen Namen -> "Left to Right/Right to left binary Exponentation" also einfach gesagt eine binäre Exponentation.

Ich hatte hier vor langer Zeit schonmal einen Source für Int64 reingestellt, http://www.delphipraxis.net/internal...+exponentation

Gruß Hagen