Jo, intesessant ist es allemal. Ausserdem ist man damit ganz dich bei Kryptographie, da wird so was auch gerne verwendet. Also Obacht, wenn du in Frankreich arbeitest. Da werden krypotgraphische Algorithmen genauso behandelt wie Waffenbesitz.

Die Multiplikation ist super simpel und funktioniert nach dam selben Prinzip, wie Grundschüler lernen 2 ganze Zahlen mit Papier und Bleistift zu multiplizieren.

Zum Ergebnis addiert man immer die Zahl a um m Stellen nach links geschoben und mit b_m multipliziert, wenn b_m die m-te Stelle von b ist.

Beide Zahlen hat man binär vorliegen, kennt also ihre Bits. Jedes Mal, wenn Bit m von b gesetzt ist, addiert man zum Ergebnis a * 2^m hinzu. That's it!

Oben in pprod() wird b mit >>=1 immer um 1 nach rechts geschoben. Daher hat man im k. Schritt an Bit 0 das (k-1)-te Bit von b. Alternativ könnte man eine Maske nach links shiften. a wird immer nach links geschoben, was einer Multiplikation mit der formalen Variablen x entspricht. Die Addition zweier Werte ist in unserem Falle aber nicht +, sondern exklusiv-oder (^ in C-Notation). Wenn man statt dem xor ein + nimmt, hat man die Multiplikation ganzer Zahlen! Bis auf einen Unterschied: in unserem Fall wird a noch mod p reduziert. Dadurch bleibt immer grad(a) < grad(p). Erst durch diese Reduktion mod p kommt es zu dem durcheinanderwürfeln der Werte. Zugleich hat man algebraisch voll den Überblick, was abgeht.

Ähnlich gute Zufallszahlen erhält man, wenn man über Z mod p*Z arbeitet. Dabei meint Z die ganzen Zahlen und p eine Primzahl (prim entspricht der Eigenschaft irreduzibel von oben).

Hast du eine ganze Zufallszahl r und ein a, dann berechnest du die nächste Zufallszahl einfach durch
r := r*a mod p
Dabei ist a eine feste Zahl, die man so wählt, daß ggT(a,p) = 1 ist und
a^((p-1)/q) ungleich 1 modulo p für alle Primteiler q von p-1.
Modulo ist der Rest, der bei Divison bleibt, zB
103 mod 10 = 3
100 mod 4 = 0
n mod (n-1) = 1
n mod (n+1) = n = -1
(n*m) mod n = 0 = (n*m) mod m