Diskussion:Blum-Blum-Shub-Generator

Größe der Menge Q, Anzahl der Wurzeln

hier hat sich ein Fehler eingeschlichen: für n=21 gibt es drei verschiedene Quadrate von zu 21 teilerfremden Zahlen, nämlich 4, 5 und 16. Dabei hat 5 nur eine Wurzel, nämlich die 10, die nicht in Q liegt und 16 hat nur drei Wurzeln, nämlich 17, 11 und 4.

s != 1, oder?

Ich glaube, es fehlt noch eine Bedingung, nämlich $s\neq 1$. Ansonsten sind alle $s_{i}=1$, und wir können nicht wirklich (auch nur pseudo-)zufällige Bits daraus erhalten. -- Paul E. 20:59, 5. Jul. 2011 (CEST)

s wird ziemlich sicher zufaellig gewaehlt, und dann ist die w'keit, dass s=1 vernachlaessigbar. --Mario d 22:22, 5. Jul. 2011 (CEST)

Im Artikel steht nichts von einer zufälligen Wahl von s - und auch dann stellt sich die Wahl, woher man die entsprechenden Zufallsbits bekommt. (Wir wollen ja gerade einen Zufallszahlengenerator bauen.) Ich denke, $s^{2}>m$ ist schon ein guter Ansatz, kann das aber nicht wirklich begründen. -- Paul E. 15:47, 6. Jul. 2011 (CEST)

nein, wir wollen einen pseudozufallszahlengenerator bauen. als deterministischer algorithmus braucht er unbedingt eine zufaellige "seed" (s), aus der dann viel mehr pseudozufallsbits gewonnen werden. wo man die seed herbekommt ist eine andere frage. das sollte im artikel aber sicherlich noch besser erlaeutert werden. --Mario d 17:38, 6. Jul. 2011 (CEST)

Dringend Überarbeiten !

Hier stimmt EINIGES nicht! Z.b. ist nicht erwähnt, woher die Zahlenreihe Z (1,2,3 ,....)kommt. Ferner ist nicht erklärt, was die Startzahl sein soll.

Nehme ich z.B. die 1, dann kommt mit (1*1, MOD 21) immer die !.

Nehme ich z.B. die 4 damm kommt bei n=3x7 die Reihe : 16,4,16,4 ,,, was soll denn das bitte für eine Zufallszahl sein?? (nicht signierter Beitrag von 80.138.174.207 (Diskussion) 16:56, 4. Mai 2021 (CEST))

Z ist die Menge der zu n teilerfremden Zahlen, steht doch dort. Und n = 21 ist natürlich ein "Sandkastenbeispiel" mit dem kleinstmöglichen n, da sehen die Zahlen nicht besonders zufällig aus, einfach weil es zu wenige sind für eine vernünftige Periodenlänge.
s = 1 ist formal zwar ein zulässiger Startwert, aber den sollte man natürlich vermeiden, ebenso wie s = n-1. Normal wählt man n sehr groß (mehrere 100 oder gar 1000 Bit) und s zufällig, dann ist die W'keit so gut wie 0, dass sich einer dieser Werte (oder ein anderer mit sehr kurzer Periode) ergibt.--Megatherium (Diskussion) 17:03, 8. Mai 2021 (CEST)

Programmierung

Mit GCC geht folgendes:

#include <stdint.h>

inline unsigned blumBlumShub(uint64_t &s, uint64_t n)
{
    s = s * __uint128_t(s) % n; // Iterationsschritt
    return s & 1;
}

inline unsigned blumBlumShubMB(uint64_t &s, uint64_t n, uint64_t z)
{
    s = s * __uint128_t(s) % n; // Iterationsschritt
    uint64_t h = s & z; // extrahiere durch z bezeichnete Bits
    h = __builtin_popcountl(h); // bestimme Zahl der Bits mit Wert 1
    return h & 1;
}

--Megatherium (Diskussion) 20:41, 17. Nov. 2023 (CET)