Blum-Blum-Shup Generator wo ist mein Denkfehler?

chrisi01

Romy lieb haben
ID: 101113
L
26 November 2008
2.854
238
hi

versuche eben einen kleinen BlumBlumShup Generator in PHP zu basteln.

PHP:
<?
//Initialisierung
$n = 192285535-549;
$s0 = 64;
$i = 0; //Schleifenzähler
//Schleife
while ($i < 100)
{
$s0 = ($s0*$s0) % $n;
echo $s0;
echo "--";
$s0 = (string)$s0;
$leng = strlen($s0);
$s0 = $s0[$leng-1];
echo $s0;
echo "<br>";
$i++; //Schleifenzähler erhöhen
}
//denkt euch im $n bitte das Minus weg musste das hinmachen damit der Thread mit der Zahl nicht per google gefunden wird damit andere nicht über das Forum auf das Rätsel kommen
?>
$n und $s0 ist vorgegeben mit dem Werten. Aber irgendwie lande ich da im nirgendwo da 64² % $n einfach nur 64² ist was ja irgendwie auch logisch ist (4096 geteilt durch eine sehr große Zahl ist eben 0 und rest 4096). Dann kommt 36 raus und da 36² % $n eben irgendwo wieder 36 ist komme ich da nicht weiter.

Hoffe mir kann wer helfen bei meinen Problem weil ich durch stundenlangen googlen eigentlich der Meihnung bin der Code ist richtig kann aber doch eigentlich nicht funktionieren wenn $n sehr groß ist (was es ja aufgrund der Sicherheit sein muss)

mfg

Chris
 
Zuletzt bearbeitet:
Dein $n wird implizit durch PHP zu einem float oder double gecastet, führt dies ggf. zu Problemen in der Arithmetik des Algorithmus?
Ich könnte mir vorstellen, dass beim Modulo es dann schief geht, da dann daraus der Rest von 2 Fließkommazahlen und nicht Ganzzahlen berechnet werden würde.
Probier es doch mal mit GMP oder BC Math aus.

Solche Algorithmen lassen sich meist nicht 1:1 umsetzen, in PHP auf Grund des impliziten Castings sowieso nicht (5 / 2 = 2.5 und nicht wie von Algorithmen 2 angedacht)
 
hi

danke genau das war das Problem float und modulo funktioniert nicht. Rechne das ganze jetzt gerade in Phyton damit geht es :)

mfg

Chris