nicht angemeldet
Rechenfehler
Hallo!
Ich beabsichtige folgende Rechnung mit JS ausführen zu lassen:
j = a^((p-1)/2) modulo p;
Ergibt:
j = Math.pow(a, (p-1)/2)%p;
Allerdings, und das ist mein Problem, ergibt sich bei a=75 und p=167
für j = 104 - wobei das richtige Ergebnis 1 ist.
Was ist falsch - kann JS vielleicht nicht mit der großen Zahl umgehen?
Besten Dank im Voraus!
-
Hallo,
Ich beabsichtige folgende Rechnung mit JS ausführen zu lassen:
j = a^((p-1)/2) modulo p;
Ergibt:
j = Math.pow(a, (p-1)/2)%p;Allerdings, und das ist mein Problem, ergibt sich bei a=75 und p=167
für j = 104 - wobei das richtige Ergebnis 1 ist.
Was ist falsch - kann JS vielleicht nicht mit der großen Zahl umgehen?Das Problem liegt nicht an den großen Zahlen, JS kann bis ~10^308 rechnen. Die Modulo-Division ermittelt den Rest einer ganzzahligen Division.
Fuer Dein Beispiel waere BCD-Arithmetik geeignet (Binary Coded Decimals). Mit den bc-Funktionen von PHP ist das so loesbar:
<?php
$a=75;
$p=167;
$j=bcmod(bcpow(strval($a),strval(($p-1)/2)),strval($p));
print $j; // 1?>
MfG, Thomas
-
Danke für diese Lösung; dennoch würde mich eine Realisierung in JavaScript interessieren, da ich nämlich eine Möglichkeit suche, für die man keinen Server braucht - also auch offline verfügbar ist!
-
Hallo ihr zwei,
Das Problem liegt nicht an den großen Zahlen, JS kann bis ~10^308 rechnen. Die Modulo-Division ermittelt den Rest einer ganzzahligen Division.
IMHO liegt es sehr wohl an den großen Zahlen. 75^167 ist ganz grob 10^300, in dem Bereich kann JavaScript zwar noch rechnen, aber nicht mit Genauigkeit 1. Vielmehr wird es ungefähr die ersten 30 (wenn überhaupt) Stellen der Zahl speichern und den Rest als 10er-Potenz, genau wie bei floats. Die Modulo-Operation muß also scheitern, weil die entscheidenden letzten 270 Stellen der Zahl (*g*) gar nicht bekannt sind.
Als Lösung fällt mir nur ein, den Ausdruck mathematisch aufzubrechen.z.B. 30^100 mod 999 == ((30x30x30)^33 x 30) mod 999; 30x30x30 == 27000; 27000 mod 999 == 27;
=> ((30x30x30)^33 x 30) mod 999 == (27^33 x 30) mod 999 usw.Das ist ein bißchen Kopfarbeit, aber machbar ;)
Simon
-
Hallo,
IMHO liegt es sehr wohl an den großen Zahlen. 75^167 ist ganz grob 10^300, in dem Bereich kann JavaScript zwar noch rechnen, aber nicht mit Genauigkeit 1.
Schon klar, meine Formulierung war etwas knapp.
Die gesuchte Potenz 75[1] hat den Wert 426662880946597168673103361184847187694364444231874421312649781313170875961362337108573588085969272335079811059202307965687595014969701878726482391357421875 und JavaScript kann diesen Wert eben nur als 4.2666288094659717e+155 darstellen. Mit diesem Wert kann man nicht mehr ganzzahlig operieren (mod 167) und deshalb wies ich ja auf BCD-Arithmetik hin.
Der OP kann ja BCD-Code nach JS portieren oder geeignete Routinen suchen.
MfG, Thomas
(167-1)/2 ↩︎
-
-