Schnelles Potenzieren in Verbindung mit Modulo

[derabkoemmling]

So erstmal grüße an alle, bin ja neu hier .

Wie das so ist wenn man sich anmeldet, hat mich dazu zunächst ein Problemchen hier hin geführt .
Ich bin mir zwar nicht sicher ob ich hier mit disem Problem richtig bin aber ich hoffe doch, dass ja :

Also, wir sind dabei ein RSA Verschlüsselungs und Entschlüsselungs Programm (in Visual Basic .NET) zu schreiben, allen die sich da ein bisschen schlau machen wollen kann ich nur
RSA @ mathematik.de
empfehlen.
Dieses Wissen ist allerdings nicht zwingen notwendig, denn ...

mein Problem liegt allein darin, dass die Zahlen bei Ver-/Entschlüsselungen mit notwendigen Rechnungen wie z.B. 50541 ^ 75475 mod 114061 einfach zu groß werden.

Um dieses Problem zu umgehen habe ich dann hier zunächst einen Lösungsweg zur Abhilfe gefunden:
Methode des Fortgesetzten Quadrierens

Jetzt komme ich zwar bis zu einem bestimmten Punkt, an dem dann bei oben genanntem Beispiel "nur" noch 50541 ^ 9939 gerechnet werden muss, die Zahlen sind allerdings immernoch zu groß.

Jetzt hab ich mich bezüglich der Methode des Fortgesetzten Quadrierens noch mal bei Wikipedia informiert. Dort ist es zwar nicht ganz genauso erklärt wie beim anderen Link allerdings das gleich Prinzip und verstanden hab ich es auch .

Was ich allerdings nicht verstanden habe ist der Algorithmusbeispiel bezüglich Modulus auf Wikipedia und ich frage mich ob ich mit diesem Algorithmus weiter kommen würde, da ich ansonsten keine andere Lösung mehr wüsste mit den hohen Zahlen umzugehen.

Also hier eindlich mal eine konkrete Frage :

Versteht jemand diesen Algorithmus und kann er mir sagen ob ich damit weiterkomme?

Ich hätte es ja auch gerne einfach ausprobiert aber selbst dazu bin ich in diesem Fall zu böde .
Wäre also super, wenn mir derjenige das ganze dann auch nochmal an einem vielleicht etwas klareren Beispiel erklären könnte .

Naja, mir fällt gerade auf, dass ich nun schon ziemlich viel geschrieben habe und ich erwarte jetzt auch von keinem, dass er sich das alles einfach so mal aneignet und sich damit beschäftigt, zumal das ja auch ziemlich komplex ist (zumindest meiner Ansicht nach ).

Aber falls sich jemand damit auskennt oder sich einfach mal mit etwas Anspruchsvollem beschäftigen will und zu viel Zeit hat oder so ...

Bin für alle Antworten dankbar.

Mit Freundlichen Grüßen

derabkoemmling

P.S.: Vielleicht hat ja auch jemand einen völlig anderen Lösungsvorschlag, bin für alles offen .

 

[Thomas Darimont]

Hallo,

schau mal hier:
http://www.codeproject.com/csharp/biginteger.asp

Btw:

/**
 * 
 */
package de.tutorials;

import java.math.BigInteger;

/**
 * @author Tom
 * 
 */
public class BigNumberMathExample {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(BigInteger.valueOf(50541L).pow(9939));
	}
}

Gruß Tom

 

[derabkoemmling]

Hi,

Vielen Dank dir erstmal für die Antwort

Bin auf den BigInteger zwar auch schon vorher gestoßen, aber das schien mir zunächst ziemlich schwer umzusetzten da ich mich in der Hinsicht noch kaum mit dem Programmieren auskenne.
Naja, mathematisch hab ichs immerhin verstanden und dass man das ganz einfach in sein Programm implementieren kann hab ich wohl auch übersehen .

Also nochmal vielen Dank, ich werd das jetzt auf jeden Fall mal probieren denn Prinzipiell sollte ich damit ja dann mit den Zahlen umgehen können.

Und das mit dem Algorithmus werd ich mit wohl nie wieder angucken wenns klappt ;-).
Hatte sowieso nicht viel Hoffnung das ich das damit hinbekomme.

Viele Grüße der.abkoemmling