Rechnen (mod) mit viel zu großer Zahl, umgehen?

Pepsmax

Hallo, bin neu hier im Forum,vielleicht könntet ihr mir helfen..

Bin leider in Mathe eine ziemliche Niete und hab deswegen eine Frage:
Muss in einem Programm mit einer extrem hohen Zahl rechnen.. : 103 hoch 173 mod 247.
Für 103 hoch 173 reicht natürlich nichtmal eine 64bit Variable, also ist es schwer auf direktem Weg auf 103 hoch 173 ein mod zu berechnen.
Ist es nicht möglich teilweise zu modulen und die kleinen zwischenergebnisse zu addieren oder sowas in der Art?
Brauch das ganze für ein RSA Krypto Beispiel..
Bin für jede Hilfe sehr dankbar.
Ciao, Max

Lord Binary

Klar, es gibt da unzählinge Algorithmen.

Recht einfach aber sehr effektiv: "Fast Exponentation"

Ohne Erklärung warum das funktioniert.
(nur bei Bedarf, ist nicht schwer, aber auch nicht trivial)

Gesucht: ((x^e) % m) =?
(?=output=Y nach der loop)

Code

X=x; E=e; Y=1; 
loop while E<>0
{
  if ((E%2)==1)
 {
	 Y=((X*Y) % m);
	 E--;
  } 
  else
  {
	 X=((X^2) % m);
	 E=E/2;
  }
}

Alles anzeigen

Das Ergebnis von (103^173) % 243 ist übrigens 187.

Mfg, LB

Pepsmax

VIELEN vielen Dank!!

Jetzt ist alles gelöst!
Verstehe zwr nicht wirklich das Mathematische an der Sache, habe aber auch schon einige Bier getrunken.. hab mal den Code eingebunden, läuft super, und es kommt das richtige raus.. werd mir alles nochmal morgen ansehen

Danke nochmal, noch einen schönen Abend,
Max

Rechnen (mod) mit viel zu großer Zahl, umgehen?

Jetzt mitmachen!

Benutzer online in diesem Thema