Fehler in Berechnung

[jo (Gast)]

Hallo,
ich kann mir ein Phänomen nicht erklären.

Ich möchte 6072 hoch 19 mod 4937 berechnen. Der Algorithmus ist
http://books.google.de/books?id=OW7LwewTKVQC&pg=PA202&dq=modular+exponentiation&hl=de&ei=zPYZTr-aNoi28QP96a30Dw&sa=X&oi=book_result&ct=result&resnum=2&ved=0CDwQ6AEwAQ#v=onepage&q=modular%20exponentiation&f=false

Seite 203

Mein Delphi Code

erge :=1;
  modulus := 4937;
  number:='10011';
  i:=length(number);
  while i>=1 do begin
  erge := erge *erge mod modulus;

  if number[i] ='1' then begin

    erge := erge *base  mod modulus;

  end;
   
  i:=i-1;

  end;
  showmessage('result:'+floatToStr(erge ) )  ;

und ein Testdurchlauf kommt einfach zum falschen Ergebnis

6027 hoch 19 mod 4937
(19)DEZ= (10011)BIN
auf papier
1. durchlauf  erg=1135
2. durchlauf erg= 3329
...
letzter: erg=3051

das ist das falsche ergebnis. Sieht jemand einen Fehler in der 
Implementierung von mir, oder kann sich erklären warum das Ergebnis 
falsch ist?

Grüße!
jo

[Rufus Τ. F. (rufus)]

Geschickterweise hast Du die Typdefinitionen der verwendeten Variablen 
nicht angegeben.

[jo (Gast)]

Hallo, danke für deine Antwort.
Alles Integer oder Extended..spielt keine Rolle. Es klappt so oder so 
nicht.

[jo (Gast)]

Den Testdurchlauf habe ich übrigens auf dem Papier durchgeführt. Mit den 
Ergebnissen komme ich zu der Annahme, dass am Algorithmus selbst etwas 
nicht stimmt?

[Yalu X. (yalu) (Moderator)]

Die Schleife geht number von rechts nach links durch. Von links nach
rechts wäre richtig.

[Power (Gast)]

aber warum nicht die vorhandene Bibliothek nutzen: Power()
http://www.epinasoft.com/delphikurs/dkk_reference_libsurvey.html

und wenn nicht effektiv genug:
http://edn.embarcadero.com/article/20026

[Yalu X. (yalu) (Moderator)]

Power schrieb:
> aber warum nicht die vorhandene Bibliothek nutzen: Power()

Weil 6027 hoch 19 =
663624846493501501654159262111497009695440367743133697838534018651800563
zu viele Stellen für die Standarddatentypen von Delphi hat. Bei Integer
ist der Wertebereich zu klein, bei Double oder Extended die Auflösung.

Da aber nur das Ergebnis modulo 19 interessiert, können die Teilmulti-
plikationen ebenfalls modulo 19 gerechnet werden, so dass 32-Bit-
Integer-Arithmetik vollkommen ausreichend ist.

[jo (Gast)]

Hallo, danke für Eure Antworten. Die Schleife ist tatsächlih falsch 
herum durchlaufen ;)
@Power
ich benutze die nicht, weil nach den Erkentnissen der modulu nicht 
beachtet ist

@Yalu,
die Berechnung wird indirekt durchgeführt und nicht 19 Multiplikationen 
von 6027 ...

Danke!

[Yalu X. (yalu) (Moderator)]

jo schrieb:
> die Berechnung wird indirekt durchgeführt und nicht 19 Multiplikationen
> von 6027 ...

Das ist schon klar. Aber habe ich das irgendwo geschrieben?

In meinem letzten Post ist aber trotzdem ein Fehler: Es sollte natürlich
zweimal "modulo 4937" statt "modulo 19" heißen.

[Abdul K. (ehydra)]

Und was macht man dann mit dem Ergebnis? Irgendwas mit Verschlüsselung?

[jo (Gast)]

ja woher weißt du das :D