Generátory pseudonáhodných čísiel

Úvod

Generovanie náhodných čísiel je dôležité v lotériách, hrách a bezpečnosti. Náhodnosť je kľúčová v kryptografii, pretože odstraňuje predvídateľnosť. Útočníci sa obvykle pokúšajú získať čo najviac informácií o systéme (a o tom ako funguje). Keď je však informácia generovaná náhodne, útočník stráca záchytné body a tým sa významne obmedzujú možnosti útokov na systém.

Rozdiel medzi skutočnou náhodnosťou a pseudonáhodnosťou

Pseudonáhodnosť

Väčšina knižníc na generovanie náhodných čísel produkuje takzvane pseudonáhodné čísla. Tieto čísla vyhovujú aspoň jednému z testov náhodnosti, ale sú generované deterministickým kauzálnym procesom. (Determinizmus znamená, že určitý systém alebo algoritmus produkuje rovnaké výstupy pri rovnakých vstupoch. Tým je predvídateľný. Kauzálnosť je príčinnosť, čiže taký vzťah, pri ktorom je jasná súvislosť medzi príčinou a dôsledkom. Čím sa opäť potvrdzuje predvídateľnosť alebo predurčiteľnosť správania sa systému.) To v konečnom dôsledku znamená, že nejde o skutočné náhodné čísla, pretože pri tých istých počiatočných podmienkach sa vždy vygeneruje rovnaká sekvencia „náhodných“ čísel. To môže byť užitočné pri rôznych výpočtových modeloch, ale spôsobuje zraniteľnosť kryptografických systémov vnášaním elementu predvídateľnosti. Stačí, keď útoční zistí, aký algoritmus generovania pseudonáhodných čísel bol použitý pri kryptovaní, aké boli počiatočné hodnoty zadané do tohto algoritmu a môže systém napadnúť.

Skutočná náhodnosť v prírode

V prírode môžeme pozorovať skutočne náhodné javy. Tie sa môžu stať zdrojom generovania skutočne náhodných čísel. Pri výpočtoch sa často na vnesenie náhodnosti používa meranie tepelného šumu polovodičových rezistorov. Operačné systémy Linux udržujú generovanie náhodných čísel a) meraním rýchlosti stláčania klávesov (používateľom) počas písania b) paralelne s čítaním najnižšej platnej bitovej číslice z merania voltáže určitého komponentu c) súčasne s ďalšími nedeterministickými a merateľnými procesmi.

Problémom pri používaní tohto štýlu generovania náhodných čísel pri šifrovaní je zabezpečenie toho, aby útočník nemohol merať tie isté hodnoty, aby vďaka nim nemohol generovať rovnaké náhodné čísla. To vyžaduje zladenie fyzickej aj matematickej bezpečnosti, čo nie je celkom vyhovujúce. Preto sa namiesto toho používajú kryptograficky bezpečné funkcie generovania pseudonáhodných čísel. Nimi sa podrobnejšie nebudeme zaoberať.

Semienko

Pretože generátory pseudonáhodných čísel sú deterministické (t. j. sú predvídateľné), musia prijať určitý vstup, ktorý bude pre nich štartovacím bodom. Podľa tohto vstupu budú generovaná sekvencia čísel a tento vstup sa nazýva semienkom (angl. seed). Semienka môžu byť volené napríklad tak, aby optimalizovali výkon alebo aby zachovali konzistenciu jednotlivých vlákien simulácie. Rovnaké semienko zadané do generátora v rôznych časoch spôsobí vygenerovanie rovnakej sekvencie pseudonáhodných čísel, preto je napríklad v kryptografii veľmi dôležité často meniť semienka, aby sa zabránilo generovaniu opakovaných predvídateľných sekvencií zdanlivo náhodných čísiel.

(Davies, Dhandhania, 2018)

LCG – linear congruential generator, lineárny kongruenčný generátor je taký generátor pseudonáhodných čísel, ktorý používa kongruenciu.

Kongruencia je pojem z teórie čísiel a doslovne znamená: „A relation between two numbers indicating they give the same remainder when divided by some given number.“ – „Vzťah medzi dvomi číslami, ktorý vyjadruje, že (čísla) majú po vydelení konkrétnym číslom rovnaký zvyšok.“

Kongruencia vo všeobecnosti značí „zhodu s niečím,“ „vhodnosť.“ Termín sa v súvislosti s modulom používa na vyjadrenie akejsi „príbuznosti“ skupiny zvyškov po delení k nejakému základu. V kontexte generovania pseudonáhodných čísiel sa kongruenciou myslí využívanie zvyšku po delení, ktorý vzniká pri operácii modulo.

Modulus doslovne znamená: „The base with respect to which a congruence is computed.“ – „Základ, vzhľadom ku ktorému je počítaná kongruencia.“

Čiže vidíme, že termíny kongruencia a modulus, tak ako sa používajú v tomto kontexte, obojstranne súvisia.

Čo si pod tým máme predstaviť? Keď sa podrobnejšie pozrieme na to, ako funguje zvyšok po delení, zistíme, že tam platí jasný vzor, že čísla delené rovnakým deliteľom produkujú opakujúce sa rady zvyškov po delení a tým sa samé zaraďujú do akýchsi „rodín“ (tvoria „príbuzenstvo“ – v nasledujúcej tabuľke sme sa ich snažili odlíšiť v jednotlivých riadkoch striedavo farebne):

`mod`	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
2	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
3	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0
4	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3	0	1
5	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1
6	1	2	3	4	5	0	1	2	3	4	5	0	1	2	3	4	5	0	1	2	3
7	1	2	3	4	5	6	0	1	2	3	4	5	6	0	1	2	3	4	5	6	0
…

Matematický vzťah na vyjadrenie spôsobu generovania pseudonáhodných čísiel LCG generátorom je nižšie. X_n označuje naposledy vygenerovaný člen postupnosti (pričom X₀ je semienko) a X_n + 1 označuje nový/nasledujúci člen postupnosti, čiže každý nasledujúci člen postupnosti je určený svojím predchodcom. mod je operátor zvyšku po delení – modulus.

X_n + 1 = (a X_n + c) `mod` m
	m,	0 < m	—	deliteľ na výpočet zvyšku po delení (modula)
	a,	0 < a < m	—	násobok
	c,	0 ≤ c < m	—	prírastok
	X₀,	0 ≤ X₀ < m	—	semienko alebo počiatočná hodnota

Nižšie je zverejnený kód miniaplikácie slúžiacej na preskúmanie rôznych vlastností vyššie uvedeného vzťahu vďaka tomu, že ho implementuje tak, aby bol konfigurovateľný. Konfigurácia parametrov generátora sa otvára kliknutím ľavého tlačidla myši a konfigurácia zobrazeného grafu (histogramu zo zvoleného počtu generovaných hodnôt) sa otvára kliknutím pravého tlačidla myši na plochu.

import knižnica.*;

/**
 * LCG – Linear Congruential Generator, lineárny kongruenčný generátor –
 * taký, ktorý používa kongruenciu, čím sa v tomto kontexte myslí využívanie
 * zvyšku po delení, ktorý vzniká pri operácii modulo.
 *
 * (Poznámky: Kongruencia vo všeobecnosti značí „zhodu s niečím“, „vhodnosť“.
 * Termín sa používa v súvislosti s modulom na vyjadrenie akejsi „príbuznosti“
 * skupiny zvyškov po delení k nejakému základu.
 *
 * Doslova modulus je: „The base with respect to which a congruence is
 * computed.“ — „Základ, vzhľadom ku ktorému je počítaná kongruencia.“
 *
 * A v teórii čísiel kongruencia je: „A relation between two numbers
 * indicating they give the same remainder when divided by some given
 * number.“ — „Vzťah medzi dvomi číslami, ktorý vyjadruje, že (čísla) majú
 * po vydelení konkrétnym číslom rovnaký zvyšok.“)
 */
public class Generátor_LCG extends GRobot
{
	private int m  = 50;
	private int a  = 31;
	private int c  = 19;
	private int x0 = 13;
	private boolean hp = false; // Hyperbolický prepočet
	private int n  = 1000;      // Počet generovaných hodnôt

	private int x = x0;
	private int[] histogram = new int[50];
	private int hodnôtMimo = 0;

	private int generuj()
	{
		return x = (a * x + c) % m;
	}

	private boolean zmenaKonfigurácie = false;

	private double šírkaStĺpcovGrafu      = 19;
	private double medzeraStĺpcovGrafu    = 2;
	private double posunutieGrafuZľava    = 30;
	private double posunutieGrafuZdola    = 60;
	private double polohaIndexovPodGrafom = 15;
	private double polohaHodnôtPodGrafom  = 30;
	private double polohaPravdepodobnostíPodGrafom = 45;
	private double mierkaVýškyGrafu       = 2.5;


	private Generátor_LCG()
	{
		super(1000, 600, "LCG generátor (" + versionString + ")");

		new ObsluhaUdalostí()
		{
			// Overenie toho, či sa konfigurácia zmenila.
			@Override public boolean konfiguráciaZmenená()
			{ return zmenaKonfigurácie; }

			@Override public void zapíšKonfiguráciu(Súbor súbor)
				throws java.io.IOException
			{
				// Zápis hodnôt vlastností:
				súbor.zapíšVlastnosť("m", m);
				súbor.zapíšVlastnosť("a", a);
				súbor.zapíšVlastnosť("c", c);
				súbor.zapíšVlastnosť("x0", x0);
				súbor.zapíšVlastnosť("hp", hp);
				súbor.zapíšVlastnosť("n", n);

				súbor.zapíšVlastnosť("šírkaStĺpcovGrafu",
					šírkaStĺpcovGrafu);
				súbor.zapíšVlastnosť("medzeraStĺpcovGrafu",
					medzeraStĺpcovGrafu);
				súbor.zapíšVlastnosť("posunutieGrafuZľava",
					posunutieGrafuZľava);
				súbor.zapíšVlastnosť("posunutieGrafuZdola",
					posunutieGrafuZdola);
				súbor.zapíšVlastnosť("polohaIndexovPodGrafom",
					polohaIndexovPodGrafom);
				súbor.zapíšVlastnosť("polohaHodnôtPodGrafom",
					polohaHodnôtPodGrafom);
				súbor.zapíšVlastnosť("polohaPravdepodobnostíPodGrafom",
					polohaPravdepodobnostíPodGrafom);
				súbor.zapíšVlastnosť("mierkaVýškyGrafu",
					mierkaVýškyGrafu);
				súbor.zapíšVlastnosť("početHodnôtGrafu",
					histogram.length);
			}

			@Override public void čítajKonfiguráciu(Súbor súbor)
				throws java.io.IOException
			{
				// Čítanie hodnôt vlastností:
				m = súbor.čítajVlastnosť("m", m).intValue();
				a = súbor.čítajVlastnosť("a", a).intValue();
				c = súbor.čítajVlastnosť("c", c).intValue();
				x = x0 = súbor.čítajVlastnosť("x0", x0).intValue();
				hp = súbor.čítajVlastnosť("hp", hp);
				n = súbor.čítajVlastnosť("n", n).intValue();

				šírkaStĺpcovGrafu      = súbor.čítajVlastnosť(
					"šírkaStĺpcovGrafu", šírkaStĺpcovGrafu);
				medzeraStĺpcovGrafu    = súbor.čítajVlastnosť(
					"medzeraStĺpcovGrafu", medzeraStĺpcovGrafu);
				posunutieGrafuZľava    = súbor.čítajVlastnosť(
					"posunutieGrafuZľava", posunutieGrafuZľava);
				posunutieGrafuZdola    = súbor.čítajVlastnosť(
					"posunutieGrafuZdola", posunutieGrafuZdola);
				polohaIndexovPodGrafom = súbor.čítajVlastnosť(
					"polohaIndexovPodGrafom", polohaIndexovPodGrafom);
				polohaHodnôtPodGrafom  = súbor.čítajVlastnosť(
					"polohaHodnôtPodGrafom", polohaHodnôtPodGrafom);
				polohaPravdepodobnostíPodGrafom  = súbor.čítajVlastnosť(
					"polohaPravdepodobnostíPodGrafom",
					polohaPravdepodobnostíPodGrafom);
				mierkaVýškyGrafu       = súbor.čítajVlastnosť(
					"mierkaVýškyGrafu", mierkaVýškyGrafu);
				int početHodnôtGrafu   = súbor.čítajVlastnosť(
					"početHodnôtGrafu", histogram.length).intValue();
				if (histogram.length != početHodnôtGrafu)
					histogram = new int[početHodnôtGrafu];
			}
		};

		Svet.zbaľ();
		farba(tmavoatramentová);
		skry();
		strop.písmo("Cambria", 10);
		písmo("Calibri", 10);
		Svet.nekresli();
		pregenerujGraf();
		prekresliGraf();
		Svet.kresli();
		Svet.pridajPoložkuPonuky("Vymaž texty", Kláves.VK_V).
			klávesováSkratka(Kláves.VK_DELETE, 0);
	}


	@Override public void voľbaPoložkyPonuky()
	{
		Svet.vymažTexty();
	}


	private void prekresliGraf()
	{
		hrúbkaČiary(šírkaStĺpcovGrafu - medzeraStĺpcovGrafu);

		for (int i = 0; i < histogram.length; ++i)
		{
			skočNa(
				Svet.najmenšieX() + posunutieGrafuZľava +
					i * šírkaStĺpcovGrafu,
				Svet.najmenšieY() + posunutieGrafuZdola);

			odskoč(polohaIndexovPodGrafom);
			text("" + i);
			skoč(polohaIndexovPodGrafom);

			odskoč(polohaHodnôtPodGrafom);
			text("" + histogram[i]);
			skoč(polohaHodnôtPodGrafom);

			odskoč(polohaPravdepodobnostíPodGrafom);
			text((histogram[i] * 100 / n) + " %");
			skoč(polohaPravdepodobnostíPodGrafom);

			vpred(histogram[i] * mierkaVýškyGrafu);
		}

		if (0 != hodnôtMimo)
		{
			skočNa(
				Svet.najmenšieX() + posunutieGrafuZľava +
					histogram.length * šírkaStĺpcovGrafu,
				Svet.najmenšieY() + posunutieGrafuZdola);
			Farba f = farba();
			farba(červená);

			odskoč(polohaHodnôtPodGrafom);
			text("" + hodnôtMimo);
			skoč(polohaHodnôtPodGrafom);

			odskoč(polohaPravdepodobnostíPodGrafom);
			text((hodnôtMimo * 100 / n) + " %");
			skoč(polohaPravdepodobnostíPodGrafom);

			vpred(hodnôtMimo * mierkaVýškyGrafu);
			farba(f);
		}
	}


	private final static String[] popisyGenerátora = new String[]
		{"<html>Deliteľ (na zvyšok po delení) <i>m</i>:</html>",
		"<html>Násobok <i>a</i>:</html>",
		"<html>Prírastok <i>c</i>:</html>",
		"<html>Semienko (počiatočná hodnota) <i>x</i><sub>0</sub>:</html>",
		"Hyperbolický prepočet:", "Počet generovaných hodnôt:"};
	private final static String[] oznamyGenerátora = new String[]
		{"deliteľa m", "násobku a", "prírastku c", "semienka",
		"hyperbolického prepočtu", "počtu generovaných hodnôt"};
	private final static Object[] údajeGenerátora =
		{0.0, 0.0, 0.0, 0.0, false, 0.0};


	private final static String[] popisyGrafu = new String[]
		{"Rozsah grafu:", "Šírka stĺpcov grafu:", "Medzera stĺpcov grafu:",
		"Mierka výšky grafu:", "Posunutie grafu:"};
	private final static String[] oznamyGrafu = new String[]
		{"rozsahu grafu", "šírky stĺpcov grafu", "medzery stĺpcov grafu",
		"mierky výšky grafu", "posunutia grafu"};
	private final static Object[] údajeGrafu =
		{0.0, 0.0, 0.0, 0.0, stred};


	private void pregenerujGraf()
	{
		x = x0; hodnôtMimo = 0;
		for (int i = 0; i < histogram.length; ++i) histogram[i] = 0;

		for (int i = 0; i < n; ++i)
		{
			int číslo = generuj();
			if (hp) číslo = (m / (číslo + 1)) - 1;
			if (číslo < 0 || číslo >= histogram.length)
				++hodnôtMimo; else ++histogram[číslo];
			if (n <= 1000 && i == 0)
				Svet.vypíš("Generované hodnoty: ", číslo);
			else if (n - i == 1000)
				Svet.vypíš("Posledných tisíc generovaných hodnôt: ", číslo);
			else if (n - i < 1000)
				Svet.vypíš(", ", číslo);
		}
		Svet.vypíšRiadok(".");
	}

	@Override public void klik()
	{
		Svet.nekresli();

		if (ÚdajeUdalostí.tlačidloMyši(ĽAVÉ))
		{
			údajeGenerátora[0] = new Double(m);
			údajeGenerátora[1] = new Double(a);
			údajeGenerátora[2] = new Double(c);
			údajeGenerátora[3] = new Double(x0);
			údajeGenerátora[4] = hp;
			údajeGenerátora[5] = new Double(n);

			if (Svet.dialóg(popisyGenerátora, údajeGenerátora,
				"Úprava parametrov generátora"))
			{
				Svet.vymaž();

				int i = 0;
				for (Object údaj : údajeGenerátora)
				{
					if (údajeGenerátora[i] instanceof Double &&
						!((Double)údajeGenerátora[i]).isNaN())
					{
						boolean zmena = false;
						int j = ((Double)údajeGenerátora[i]).intValue();
						switch (i)
						{
						case 0: if (m != j)  { m = j;  zmena = true; } break;
						case 1: if (a != j)  { a = j;  zmena = true; } break;
						case 2: if (c != j)  { c = j;  zmena = true; } break;
						case 3: if (x0 != j) { x0 = j; zmena = true; } break;
						case 5: if (n != j)  { n = j;  zmena = true; } break;
						}
						if (zmena)
						{
							Svet.vypíšRiadok("Zmena ",
								oznamyGenerátora[i], ": ", j);
							zmenaKonfigurácie = true;
						}
					}
					else if (údajeGenerátora[i] instanceof Boolean)
					{
						boolean zmena = false;
						boolean j = (Boolean)údajeGenerátora[i];
						switch (i)
						{
						case 4: if (hp != j) { hp = j; zmena = true; } break;
						}
						if (zmena)
						{
							Svet.vypíšRiadok("Zmena ",
								oznamyGenerátora[i], ": ", j);
							zmenaKonfigurácie = true;
						}
					}
					++i;
				}

				pregenerujGraf();
				prekresliGraf();
			}
		}
		else
		{
			údajeGrafu[0] = new Double(histogram.length);
			údajeGrafu[1] = new Double(šírkaStĺpcovGrafu);
			údajeGrafu[2] = new Double(medzeraStĺpcovGrafu);
			údajeGrafu[3] = new Double(mierkaVýškyGrafu);
			údajeGrafu[4] = new Bod(posunutieGrafuZľava,
				posunutieGrafuZdola);

			if (Svet.dialóg(popisyGrafu, údajeGrafu,
				"Úprava parametrov grafu"))
			{
				Svet.vymaž();

				int i = 0;
				for (Object údaj : údajeGrafu)
				{
					if (údajeGrafu[i] instanceof Double &&
						!((Double)údajeGrafu[i]).isNaN())
					{
						if (0 == i)
						{
							int j = ((Double)údajeGrafu[i]).intValue();
							if (histogram.length != j)
							{
								if (j > 1)
								{
									histogram = new int[j];
									Svet.vypíšRiadok("Zmena ",
										oznamyGrafu[i], ": ", j);
									pregenerujGraf();
									zmenaKonfigurácie = true;
								}
								else
									Svet.chyba(
										"Rozsah musí byť väčší ako 1.");
							}
						}
						else
						{
							boolean zmena = false;

							double j = (Double)údajeGrafu[i];
							switch (i)
							{
							case 1: if (šírkaStĺpcovGrafu != j)
								{
									šírkaStĺpcovGrafu = j;
									zmena = true;
								}
								break;

							case 2: if (medzeraStĺpcovGrafu != j)
								{
									medzeraStĺpcovGrafu = j;
									zmena = true;
								}
								break;

							case 3: if (mierkaVýškyGrafu != j)
								{
									mierkaVýškyGrafu = j;
									zmena = true;
								}
								break;
							}

							if (zmena)
							{
								Svet.vypíšRiadok("Zmena ",
									oznamyGrafu[i], ": ", j);
								zmenaKonfigurácie = true;
							}
						}
					}
					else if (údajeGrafu[i] instanceof Bod)
					{
						double x = ((Bod)údajeGrafu[i]).polohaX();
						double y = ((Bod)údajeGrafu[i]).polohaY();

						if (posunutieGrafuZľava != x ||
							posunutieGrafuZdola != y)
						{
							posunutieGrafuZľava = x;
							posunutieGrafuZdola = y;
							Svet.vypíšRiadok("Zmena ",
								oznamyGrafu[i], ": ", x, ", ", y);
							zmenaKonfigurácie = true;
						}
					}
					++i;
				}

				prekresliGraf();
			}
		}

		Svet.kresli();
	}


	public static void main(String[] args)
	{
		Svet.použiKonfiguráciu("Generátor_LCG.cfg");
		new Generátor_LCG();
	}
}

Prerekvizity

Na prácu budete potrebovať softvér inštalovaný automatickým aktualizátorom a najnovšiu verziu programovacieho rámca GRobot.

(Mali by ste ich nájsť v sekcii Softvér na prevzatie.)

obrázok
Vzhľad okna miniaplikácie po prvom spustení.

Úloha

V zdroji Random Number Generation na strane 42 je nasledujúci generátor:

x_n = (25 173 ⋅ x_n − 1 + 13 849) mod 2¹⁶

obrázok

Ak k nemu nastavíte nasledujúce parametre grafu, môžete lepšie preskúmať jeho vlastnosti:

obrázok

Empiricky overte (skúsenosťou, zážitkom – experimentovaním; najlepšie experimentom, ktorý potvrdí Váš predchádzajúci teoretický predpoklad, čiže najskôr si skúste vec dobre premyslieť), po koľkých opakovaniach generovania hodnôt sa generátor „pretočí“ (to jest, začne generovať hodnoty od začiatku).

Zdroje

Pseudo Random Number Generator (PRNG). In GeeksforGeeks : A computer science portal for geeks. ⟨https://www.geeksforgeeks.org/pseudo‑random‑number‑generator‑prng/ ⟩. Last accessed: 2019‑10‑19.

Jain, Raj: Random Number Generation. St. Louis, MO : Washington University in St. Louis, 2010. 438,03 kB (427,76 KiB), 19. 10. 2019

Wikipedia contributors: Linear congruential generator. In Wikipedia, The Free Encyclopedia. ⟨https://en.wikipedia.org/w/index.php?title=Linear_congruential_generator&oldid=920136390 ⟩. Last accessed: 2019‑10‑19.
Davies, Ian – Dhandhania, Keshav: How Random Number Generation works, with Algorithms and Examples. In CommonLounge. 2018. ⟨https://www.commonlounge.com/discussion/481152258acb4003a5903d2fc1bc425f ⟩. Last accessed: 2019‑11‑02.

x_n + 1 = x_n² `mod` M
	M = p q	—	deliteľ na výpočet zvyšku po delení (modula)
	p, q	—	dve veľké prvočísla (podrobnosti v programe nižšie)
	s, \|s\| > 1	—	semienko alebo počiatočná hodnota (x₋₁); malo by byť také, aby jeho najväčšie spoločné delitele s p a q boli rovné 1

(Príklady vhodných p a q: 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179, 191, 199, 211, 223, 227, 239, 251, 263, 271…)

import knižnica.*;

/**
 * B. B. S. – Blumov Blumov Shubov algoritmus,
 * ⟨https://link.springer.com/chapter/10.1007/978-1-4757-0602-4_6⟩.
 *
 * Úryvok z teórie: p a q musia byť prvočísla, ktorých zvyšok po delení
 * štyrmi je rovný trom. Z nich je potom vypočítaný koeficient m = p × q.
 *
 * Hodnoty x sú potom rátané takto: xₙ = (xₙ₋₁)² mod m, pričom výsledok
 * generujúcej funkcie nie je x, ale jeden bit (v našom programe aj skupina
 * bitov), ktorý je určený buď na základe parity (ak je početBitov v našom
 * programe záporná hodnota), alebo ide o najmenej signifikantný bit aktuálnej
 * hodnoty x (bit „najviac vpravo“, to jest bit na úrovni nultého rádu).
 */
public class Generátor_BBS extends GRobot
{
	private int p = 67; // Iné príklady: 11, 7…
	private int q = 79; // Iné príklady: 19, 31…
	private int m = p * q;
	private int s = 127; // Iné príklady: 3, 100…
	private int početBitov = -8;
		// 0 – generuje hodnoty bitov priamo, nie zoskupené do n-tíc. Ak je
		// počet bitov rovný 1, tak je výsledok rovnaký ako pri hodnote 0,
		// len so zopár výpočtami navyše. Čiže rozdiel sa v kladnom smere
		// začne prejavovať od hodnoty 2 a vyššie. Záporné hodnoty (−1
		// a nižšie) zmenia režim vracania bitov z „najmenej signifikantného“
		// na „paritu.“

	private int početGenerovanýchHodnôt = 1000;

	private int x = s;
	private int[] histogram = new int[255];
	private int hodnôtMimo = 0;

	private int generuj()
	{
		if (0 == početBitov)
		{
			x = (x * x) % m;
			return x & 1;
		}
		else if (početBitov > 0)
		{
			int číslo = 0;

			for (int i = 0; i < početBitov; ++i)
			{
				x = (x * x) % m;
				číslo <<= 1;
				číslo |= x & 1;
			}

			return číslo;
		}

		int číslo = 0;

		for (int i = 0; i > početBitov; --i)
		{
			x = (x * x) % m;

			int xx = x;
			int parita = 0;
			while (0 != xx)
			{
				parita += xx & 1;
				xx >>= 1;
			}

			číslo <<= 1;
			číslo |= parita & 1;
		}

		return číslo;
	}


	private double šírkaStĺpcovGrafu = 2.9;
	private double medzeraStĺpcovGrafu = 1.9;
	private double posunutieGrafuZľava = 30;
	private double posunutieGrafuZdola = 30;
	private double mierkaVýškyGrafu = 2.5;

	private Generátor_BBS()
	{
		super(800, 600, "B. B. S. generátor (" + versionString + ")");
		Svet.zbaľ();
		farba(tmavoatramentová);
		skry();
		strop.písmo("Cambria", 10);
		Svet.nekresli();
		pregenerujGraf();
		prekresliGraf();
		Svet.kresli();
		Svet.pridajPoložkuPonuky("Vymaž texty", Kláves.VK_V).
			klávesováSkratka(Kláves.VK_DELETE, 0);
	}


	@Override public void voľbaPoložkyPonuky()
	{
		Svet.vymažTexty();
	}


	private void prekresliGraf()
	{
		hrúbkaČiary(šírkaStĺpcovGrafu - medzeraStĺpcovGrafu);

		for (int i = 0; i < histogram.length; ++i)
		{
			skočNa(
				Svet.najmenšieX() + posunutieGrafuZľava +
					i * šírkaStĺpcovGrafu,
				Svet.najmenšieY() + posunutieGrafuZdola);
			vpred(histogram[i] * mierkaVýškyGrafu);
		}

		if (0 != hodnôtMimo)
		{
			skočNa(
				Svet.najmenšieX() + posunutieGrafuZľava +
					histogram.length * šírkaStĺpcovGrafu,
				Svet.najmenšieY() + posunutieGrafuZdola);
			Farba f = farba();
			farba(červená);
			vpred(hodnôtMimo * mierkaVýškyGrafu);
			farba(f);
		}
	}


	private final static String[] popisyGenerátora = new String[]
		{"<html>Prvočíslo <i>p</i>:</html>",
		"<html>Prvočíslo <i>q</i>:</html>",
		"<html>Semienko <i>s</i>:</html>",
		"Počet generovaných bitov (0 – generuj hodnoty priamo):",
		"Počet generovaných hodnôt (grafu):"};
	private final static String[] oznamyGenerátora = new String[]
		{"prvočísla p", "prvočísla q", "semienka", "počtu generovaných bitov",
		"počtu generovaných hodnôt"};
	private final static Object[] údajeGenerátora = {0.0, 0.0, 0.0, 0.0, 0.0};


	private final static String[] popisyGrafu = new String[]
		{"Rozsah grafu:", "Šírka stĺpcov grafu:", "Medzera stĺpcov grafu:",
		"Mierka výšky grafu:", "Posunutie grafu:"};
	private final static String[] oznamyGrafu = new String[]
		{"rozsahu grafu", "šírky stĺpcov grafu", "medzery stĺpcov grafu",
		"mierky výšky grafu", "posunutia grafu"};
	private final static Object[] údajeGrafu = {0.0, 0.0, 0.0, 0.0, stred};


	private void pregenerujGraf()
	{
		x = s; m = p * q; hodnôtMimo = 0;
		for (int i = 0; i < histogram.length; ++i) histogram[i] = 0;

		for (int i = 0; i < početGenerovanýchHodnôt; ++i)
		{
			int číslo = generuj();

			if (číslo < 0 || číslo >= histogram.length)
				++hodnôtMimo; else ++histogram[číslo];

			if (početGenerovanýchHodnôt <= 1000 && i == 0)
				Svet.vypíš("Generované hodnoty: ", číslo);
			else if (početGenerovanýchHodnôt - i == 1000)
				Svet.vypíš("Posledných tisíc generovaných hodnôt: ", číslo);
			else if (početGenerovanýchHodnôt - i < 1000)
				Svet.vypíš(", ", číslo);
			Svet.vypíš(" (x = ", x, ")");
		}
	}

	// Rýchla kontrola (nebola by efektívna na hľadanie nových prvočísiel).
	private boolean jePrvočíslo(int n)
	{
		if (n < 2) return false;
		if (0 == n % 2) return false;
		for (int i = 3; i * i <= n; i += 2)
			if (0 == n % i) return false;
		return true;
	}

	@Override public void klik()
	{
		Svet.nekresli();

		if (ÚdajeUdalostí.tlačidloMyši(ĽAVÉ))
		{
			údajeGenerátora[0] = new Double(p);
			údajeGenerátora[1] = new Double(q);
			údajeGenerátora[2] = new Double(s);
			údajeGenerátora[3] = new Double(početBitov);
			údajeGenerátora[4] = new Double(početGenerovanýchHodnôt);

			if (Svet.dialóg(popisyGenerátora,
				údajeGenerátora, "Úprava parametrov"))
			{
				Svet.vymaž();

				int i = 0;
				for (Object údaj : údajeGenerátora)
				{
					if (údajeGenerátora[i] instanceof Double &&
						!((Double)údajeGenerátora[i]).isNaN())
					{
						boolean zmena = false;
						int j = ((Double)údajeGenerátora[i]).intValue();
						switch (i)
						{
						case 0:
							if (p != j)
							{
								if (jePrvočíslo(j))
								{
									if (3 == j % 4) { p = j; zmena = true; }
									else Svet.chyba("Prvočíslo p musí mať " +
										"zvyšok po delení rovný štyrom.");
								}
								else Svet.chyba("Číslo p musí byť prvočíslo.");
							}
							break;

						case 1:
							if (q != j)
							{
								if (jePrvočíslo(j))
								{
									if (3 == j % 4) { q = j; zmena = true; }
									else Svet.chyba("Prvočíslo q musí mať " +
										"zvyšok po delení rovný štyrom.");
								}
								else Svet.chyba("Číslo q musí byť prvočíslo.");
							}
							break;

						case 2: if (s != j) if (Math.abs(j) > 1)
							{ s = j; zmena = true; } else Svet.chyba(
								"Semienko musí byť mimo intervalu ⟨−1; 1⟩");
							break;

						case 3: if (početBitov != j)
							{ početBitov = j; zmena = true; }
							break;

						case 4: if (početGenerovanýchHodnôt != j)
							{ početGenerovanýchHodnôt = j; zmena = true; }
							break;
						}

						if (zmena) Svet.vypíšRiadok("Zmena ",
							oznamyGenerátora[i], ": ", j);
					}
					++i;
				}

				pregenerujGraf();
				prekresliGraf();
			}
		}
		else
		{
			údajeGrafu[0] = new Double(histogram.length);
			údajeGrafu[1] = new Double(šírkaStĺpcovGrafu);
			údajeGrafu[2] = new Double(medzeraStĺpcovGrafu);
			údajeGrafu[3] = new Double(mierkaVýškyGrafu);
			údajeGrafu[4] = new Bod(posunutieGrafuZľava,
				posunutieGrafuZdola);

			if (Svet.dialóg(popisyGrafu, údajeGrafu,
				"Úprava parametrov grafu"))
			{
				Svet.vymaž();

				int i = 0;
				for (Object údaj : údajeGrafu)
				{
					if (údajeGrafu[i] instanceof Double &&
						!((Double)údajeGrafu[i]).isNaN())
					{
						if (0 == i)
						{
							int j = ((Double)údajeGrafu[i]).intValue();
							if (histogram.length != j)
							{
								if (j > 1)
								{
									histogram = new int[j];
									Svet.vypíšRiadok("Zmena ",
										oznamyGrafu[i], ": ", j);
									pregenerujGraf();
								}
								else
									Svet.chyba(
										"Rozsah musí byť väčší ako 1.");
							}
						}
						else
						{
							boolean zmena = false;

							double j = (Double)údajeGrafu[i];
							switch (i)
							{
							case 1: if (šírkaStĺpcovGrafu != j)
								{
									šírkaStĺpcovGrafu = j;
									zmena = true;
								}
								break;

							case 2: if (medzeraStĺpcovGrafu != j)
								{
									medzeraStĺpcovGrafu = j;
									zmena = true;
								}
								break;

							case 3: if (mierkaVýškyGrafu != j)
								{
									mierkaVýškyGrafu = j;
									zmena = true;
								}
								break;
							}

							if (zmena) Svet.vypíšRiadok("Zmena ",
								oznamyGrafu[i], ": ", j);
						}
					}
					else if (údajeGrafu[i] instanceof Bod)
					{
						double x = ((Bod)údajeGrafu[i]).polohaX();
						double y = ((Bod)údajeGrafu[i]).polohaY();

						if (posunutieGrafuZľava != x ||
							posunutieGrafuZdola != y)
						{
							posunutieGrafuZľava = x;
							posunutieGrafuZdola = y;
							Svet.vypíšRiadok("Zmena ",
								oznamyGrafu[i], ": ", x, ", ", y);
						}
					}
					++i;
				}

				prekresliGraf();
			}
		}

		Svet.kresli();
	}


	public static void main(String[] args)
	{
		Svet.použiKonfiguráciu("Generátor_BBS.cfg");
		new Generátor_BBS();
	}
}

obrázok
Aplikácia po prvom spustení.


Konfiguračné dialógy (otvoriteľné kliknutím ľavého a pravého tlačidla myši na plochu).

Zdroje

Chaum, David – Rivest, Ronald L. – Sherman, Alan T.: Comparison of Two Pseudo‑Random Number Generators. In Advances in Cryptology. Boston, MA : Springer, 1983. Print ISBN 978‑1‑4757‑0604‑8. Online ISBN 978‑1‑4757‑0602‑4. Pp 61 – 78. ⟨https://doi.org/10.1007/978‑1‑4757‑0602‑4 ⟩. Last accessed: 2019‑10‑19.

Geisler, Martin – Krøigård, Mikkel – Danielsen, Andreas: About Random Bits. 2004, pp. 9–14. 155,99 kB (152,34 KiB), 19. 10. 2019

Wikipedia contributors: Blum Blum Shub. In Wikipedia, The Free Encyclopedia. ⟨https://en.wikipedia.org/w/index.php?title=Blum_Blum_Shub&oldid=918901372 ⟩. Last accessed: 2019‑10‑19.
Davies, Ian – Dhandhania, Keshav: How Random Number Generation works, with Algorithms and Examples. In CommonLounge. 2018. ⟨https://www.commonlounge.com/discussion/481152258acb4003a5903d2fc1bc425f ⟩. Last accessed: 2019‑11‑02.
Junod, Pascal: Cryptographic Secure Pseudo‑Random Bits Generation : The Blum‑Blum‑Shub Generator. 1999. ⟨http://www.cs.miami.edu/home/burt/learning/Csc609.062/docs/bbs.pdf 357,00 B (357,00 B), 19. 2. 2006⟩. Last accessed: 2019‑11‑02.
Kun, Jeremy: The Blum‑Blum‑Shub Pseudorandom Generator. In Math ∩ Programming. 2016. ⟨https://jeremykun.com/2016/07/11/the‑blum‑blum‑shub‑pseudorandom‑generator/ ⟩. Last accessed: 2019‑11‑02.

Prosím, vyberte kartu s algoritmom.

`mod`	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
2	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
3	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0
4	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3	0	1
5	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1
6	1	2	3	4	5	0	1	2	3	4	5	0	1	2	3	4	5	0	1	2	3
7	1	2	3	4	5	6	0	1	2	3	4	5	6	0	1	2	3	4	5	6	0
…

`mod`	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
2	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
3	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0
4	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3	0	1
5	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1
6	1	2	3	4	5	0	1	2	3	4	5	0	1	2	3	4	5	0	1	2	3
7	1	2	3	4	5	6	0	1	2	3	4	5	6	0	1	2	3	4	5	6	0
…

`mod`	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
2	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
3	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0
4	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3	0	1
5	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1
6	1	2	3	4	5	0	1	2	3	4	5	0	1	2	3	4	5	0	1	2	3
7	1	2	3	4	5	6	0	1	2	3	4	5	6	0	1	2	3	4	5	6	0
…