Fehler bei function (c=m^e mod N)

[Mb123]

Hallo,
ich habe eine funktion geschrieben die mir folgenden ausdruck ausrechnen soll: c=m^e mod N
so hier erstmal die funktion:

Delphi-Quellcode:

[...]
var
  e,m:integer;
[...]
function verschluesseln(q:integer;s:integer):integer;
begin

result:=m^e; mod q*s;
end;

ich erhalte nun folgenden fehler:
[Error] Programm.pas(87): Pointer type required
[Fatal Error] Project5.dpr(5): Could not compile used unit 'Programm.pas'

kann mir einer sagen was ich da verändern muss ? denn mit der meldung kann ich irgendwie nich besonders viel anfangen.

[leddl]

^ steht für einen Pointer :zwinker:
Versuch dein Glück stattdessen mal mit Power der Unit Math ;)

[Mb123]

danke erstmal :) hab jetzt so gemacht :

Delphi-Quellcode:

function Power(Basis,Exponent:Extended):extended;
begin
result := exp(Exponent*ln(Basis))
end;

function verschluesseln(m:integer):integer;
begin
n:=q*s;
result:=Power(m,e) mod n;
end;

nur das problem ist jetzt das ich mit Power(m,e) ja einen extended Wert habe. ich schätz es wird jetzt schwierig diesen wert in einen integer umzuwandeln, denn bei der rsa verschlüsselung sind werte die bei power(m,e) eingesetzt werden schon mal zahlen wie power(133,151). weiß jemand wie ich das problem lösen kann ?

[Mb123]

kann man nicht vielleicht irgendeine langzahlen bibliothek oder sowas implementieren ?
weil mit zahlen wie 291^151 sollte der computer durch irgendwie eine modulo rechnung durch-
führen können ?? mit meinem TI Voyage 200 geht das sogar :shock:

Zitat:

...mit Microsoft Visual C++ 6.0 zu entwickeln.
Um das Rechnen auch mit großen Zahlen zu gewährleisten, musste eine geeignete
Langzahlen-Bibliothek implementiert werden, die den Ansprüchen der einfachen
Implementierung in die Entwicklungsumgebung genügte. Diese Anforderungen wurden
durch die so genannte NTL-Langzahlen-Bibliothek([6]) erfüllt. Die benötigten Funktionen,
wie z. B. der erweiterte Euklidsche Algorithmus wurden unter Verwendung der in
den Quellen [1], [2], bzw. [8] bereitgestellten Pseudo-Codes in die Sprache C++ umgesetzt.

das habe ich in einer arbeit gelesen, in der das problem auch aufgetreten und gelöst wurde.
könnte man sowas auch in delphi umsetzten ?

[MatWur]

eine gute Bibliothek mit Routinen für grosse Ganzzahlen suche ich auch schon lange, bisher ohne Erfolg :roll: Deswegen versuche ich gerade eine für mich zu programmieren, ich hänge aber bei der Multiplikation fest... naja.
Für die Potenzierung gibt es im binären einen sehr schnellen und nicht allzu schwer zu implementierenden Algorithmus, den kannst du in der Wiki nachlesen: http://de.wikipedia.org/wiki/Schnelles_Potenzieren

mfg

Matthias

[Die Muhkuh]

Zitat:

Zitat von MatWur

eine gute Bibliothek mit Routinen für grosse Ganzzahlen suche ich auch schon lange, bisher ohne Erfolg :roll:

Dann kennst Du Hagens DecMath nicht ;)

DecMath

http://www.michael-puff.de/dirindex....agen_Reddmann/

[MatWur]

hm, Danke Schön.
In der Tat kannte ich diese Bibliothek noch nicht, sie sollte für Mb123 eigentlich sehr gut brauchbar sein. Die sieht sehr schön und übersichtlich aus. Für mein Problem hilft sie mir leider nicht. Ich versuche den Schönhage-Strassen-Algorithmus zur schnellen Multiplikation von Binärzahlen zu realisieren, vom Prinzip her habe ich das auch schon. Meine Implementierungen sind aber nicht praktikabel, weil ich noch viel zu viel Speicherplatz während der Multiplikation brauche und dementsprechend auch langsam bin. In der Library ist der Algorithmus implementiert, aber ich bräuchte den Source-Code um mal zu gucken, wie Hagen das Platzproblem gelöst hat... naja, dafür habe ich meinen eigenen Fred (seltsamerweise in Numerik/Optimierung...wieso ich den gerade da reingestellt habe weiss ich nicht mehr so sicher :lol: ), das gehört hier gar nicht her.
Danke nochmal für den Link!

mfg

Matthias

[hsg]

Hmm, darf ich mal fragen, was du für Zahlen multiplizieren möchtest?

Der Schönhage-Strassen-Algo taugt nur was für wirklich extrem große Zahlen. Bei "normalen" Zahlen braucht er wegen den DFTs sogar länger als der normale Schulalgo.

Zitat:

Zitat von Wikipedia

Selbst bei modernen Computern ist diese Methode der Berechnung erst bei Zahlen mit mehreren tausend Stellen effizienter als der Karatsuba-Algorithmus.

[alcaeus]

Ach Jungs...

Warum wollen so viele einen RSA-Algorithmus implementieren, wenn sie denn absolut keine Ahnung von den mathematischen Grundlagen der modulo-Rechnung haben? Das Thema hatten wir schon ein paar Mal, letztens in http://www.delphipraxis.net/internal...t.php?t=102928. Fakt ist: wer bei (a ^ b) mod c zuerst a ^ b ausrechnet, sollte sich dringendst mit Modulorechnungen auseinandersetzen.

Greetz
alcaeus

[MatWur]

@ hsg: ich möchte Zahlen mit bis zu 2^27 Bit multiplizieren können, wenn man mit Mersennezahlen rumspielt kommen solche Grössenordnungen raus. Selbst Karazuba (oder Karatsuba) ist da viel zu langsam. Im Moment müsste der Wiki-Satz übrigens lauten: 'Gerade bei modernen Computern ...' den von steigender Registergrösse (wie momentan von 32 auf 64 Bit) profitiert die Karazuba-Methode stärker als der SchönStrAlg (der profitiert stärker von einer Takterhöhung als die K_Methode)

mfg

Matthias