Fehler in Berechnung

jo Gast #2259487
Lesenswert?
• ▲
▼ 
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
1
erge :=1;

2
  modulus := 4937;

3
  number:='10011';

4
  i:=length(number);

5
  while i>=1 do begin

6
  erge := erge *erge mod modulus;

7


8
  if number[i] ='1' then begin

9


10
    erge := erge *base  mod modulus;

11


12
  end;

13
   

14
  i:=i-1;

15


16
  end;

17
  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
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Yalu X. Moderator #2259715
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
jo Gast #2259777
Lesenswert?
• ▲
▼ 
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!
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren