Überlauf

Computer: Software & Programmierung C/C++
#1

Hallo!
Ich möchte ein kleines Verschlüsselungsprogramm nach RSA schreiben. Große Primzahlen kombiniert mit der Modulorechnung ergeben einen schwerknackbaren coktail. Es soll mit C++ 6 folgendes berechnet werden:
c=65^228901 mod (509329*11197); //fmod oder % ist im Grunde egal

Warum tut das nicht? Es kommt ständig Überlauf. Ich speichere die Werte niergend zwischen, sondern es kommt alles in eine Zeile als ein Ausdruck. Auch am Datentyp zu basteln bringt nicht (float, long double, usw.).
Wenn ich die Gleichung in Maple 8 eingebe, kmmt nach ein paar Milisekunden das Ergebnis raus, in diesem Fall c = 246714407.
Außerdem für kleinere Werte (> = 11) rechnet C ++ was anderes aus als das CAS-System Ti92+, wem kann ich dann trauen?
Was mache ich falsch? Wie schaffen es die von Waterloo oder PGP? Hat mir jemanden einen funktionierenden Rat? Aber bitte keine RSA-Header oder dll aus dem Netz, weil ich es selbst verstehen will.
Vielen Dank im Voraus!

Gruß Christian

#2

schön, du hast den RSA-algo gelesen und verstanden. bei der umsetzung braucht es aber noch ein paar tricks.

Warum tut das nicht? Es kommt ständig Überlauf.

65^228901 ist eine zahl, die kein system des universeums ausschreiben kann.

Auch am Datentyp zu basteln bringt nicht (float, long
double, usw.)

float wäre nicht gut, das sind kommazahlen mit begrenzter genauigkeit.

Wenn ich die Gleichung in Maple 8 eingebe, kmmt nach ein paar
Milisekunden das Ergebnis raus, in diesem Fall c = 246714407.

maple ist bei solcher mathematik wesentlich mächtiger als C ohne extras.
Es benutzt lange integers (länger als ein prozessorregister) und ebenfalls einige tricks.

wie genau das geht kann ich auch nicht sagen, nur, dass du das problem etwas unterschätzt hast :smile:

wer weiss mehr?

gruss, matze

#3

X-Posting => Programmierung allg. (owT)
(owT)

#4

Wie man das jetzt ausrechnet, kann ich dir auch nicht sagen. Aber daß es wohl nicht so einfach ist, zeigt folgendes kleines Rechenbeispiel:

Nehmen wir mal 64 statt 65 (ist ja ungefähr gleich). Dann haben wir

64^228901 = (2^6)^228901 = 2^1373406

Das heißt, du bräuchtest alleine für die Darstellung dieser einen Zahl im Rechner 170MB Speicher. Wie der arme Prozessor dann auf so eine Zahl Modulo rechnen soll weiß ich auch nicht… :smile:
Aber so ist der halt mit der Mathematik: Sehr elegant aber im Endeffekt irgendwie im wahrsten Sinne des Wortes un-praktisch! :wink:

Viele Grüße,

Hendrik.

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#5

Eigentlich sollte es möglich sein diese Zahl zu berechnen, wenn du eine Klasse mit einige algebraische Funktionen für CStrings schreibst. Der Nachteil dieser Lösung ist, dass diese Klasse wahrscheinlich sehr langsam sein wird.

class CBig
{
private:
CString string;

public:
multipliziern(int x);
modulo(int x);
}

Du solltest beim Schreiben der Methoden wie in der Grundschule vorgehen.

MULTIPLIZIERN:

CString string=123;
int x=4;

123*4

2 // 3*4 = 12 -> 2 & 1 merken
9 // 2*4 = 8 + 1 (gemerkt von 3*4)
4 // 1*4 = 4

492

MODULO:

CString string=123;
int x=4;

123:4

0 // 1:4=0 -> 1 merken
3 // 12*4=3
0 // 3:4=0 -> Rest (also modulo) = 3

30 REST 3