Žodis angliškai
Linear Congruential Generator
Santrumpa
LCG
Žodis Lietuviškai
Tiesinis kongruentinis generatorius
Apibrėžimas
Pseudoatsitiktinių skaičių generavimo metodas.
Paaiškinimai
Algoritmas parametrizuojamas keturiais skaičiais:
m – modulis, m>0
a – daugiklis, 0<a<m
c – prieaugis, 0≤c<m
X0 – pradinė vertė, seed, 0 ≤X0<m
Atsitinių skaičių seka {Xn} yra gaunama pakartojant sprendimą lygties:
X(n+1)=(aXn+c) mod m
Jeigu m,a,c ir X0 yra sveikieji skaičiai, tai šitas algoritmas generuos sveikųjų skaičių seką ruože 0 ≤Xn<m.
Verčių a,c ir m parinkimas yra kritinis norint sukurti gerą atsitiktinių skaičių generatorių. Pavyzdžiui, a=c=1. Gauta seka yra aiškiai netinkama. Tarkim parenkame vertes a=7,c=0,m=32 ir X0=1. Generuojama seka {7,17,23,1,7 ir t.t.}. Iš galimų 32 verčių tik keturios yra naudojamos. Taigi sakoma, kad seka turi periodą 4.
Norint gauti ilgas sekas atsitiktinių skaičių reikia parinkti m. Dažnas kriterijus yra, kad m būtų lygus didžiausiam teigiamam skaičiui išsaugomam kompiuteryje. Taigi dažnai parenkama vertė yra šalia ar lygi 231.
Siūlome testai atsitiktinių skaičių generatoriui įvertiniti:
T1 – funkcija turi būti visą periodą generuojanti funkcija. Taigi visi skaičiai turi būti sugeneruoti nuo 0 iki m prieš pradedant kartotis.
T2- generuojama seka turi atrodyti atsitiktinė.
T3 – funkcija turi būti lengvai įgyvendinama naudojant 32 bitų aritmetiką.
Esant tinkamoms a, c ir m reikšmėms šie testai gali būti išlaikyti. Dėl T1 testo, galima įrodyti, kad jeigu m yra pirminis skaičius ir c=0, tada tam tikroms vertėms a, generuojamos funkcijos periodas m-1, vienintelė nepanaudota reikšmė yra 0.
32 bitų aritmetikoje patogi m reikšmė yra pirminis skaičius 231-1. Taigi generuojančioji funkcija tampa:
X(n+1)=(aXn)mod(231-1)
Iš dviejų milijardų galimų a reikšmių, tik keletas tenkina visus tris testus. Viena tokių reikšmių a=75=16807. Šio linijinio kongruentinio algoritmo stiprioji pusė yra tai, kad jei parinkus daugiklį ir modulį, gauta seka statistiškai neatskiriama nuo sekos gautos iš aibės 1, 2, ... , m-1. Tačiau nėra nieko atsitiktinio apie šį algoritmą, išskyrus X0 parinkimą. Kai vertė parinkta, visi sekantys skaičiai seka deterministiškai.
Jeigu oponentas sužino, kad naudojamas linijinis kongruentinis algoritmas, tai žinodamas mažą sekos dalį (X0,X1,X2,X3) gali nustatyti a,c ir m vertes, bei visą seką. Jam tereikia išspręsti trijų lygčių sistemą:
X1=(aX0+c)mod m
X2=(aX1+c)mod m
X3=(aX2+c)mod m
Dažnai reikia, kad PRNG generuotų nenuspėjamą seką, kad dalies jos žinojimas neleistų nuspėti oponentui tolesnių reikšmių. Tai galima pasiekti keliais būdais. Pavzydžiui, galima naudoti vidinį sistemos laikrodį atsitiktinės skaičių sekos modifikavimui. Panaudojama laikrodžio momentinė vertė. Ji pridedama prie kiekvieno sekos numerio ir atlikti papildomai mod m veiksmą
Naudota literatūra
William Stallings. Cryptography and Network Security. Principles and Practice. New York, 2011.