Blum-Blum-Shubov generator psevdonaključnih števil

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Blum-Blum-Shubov generator psevdonaključnih števil ali krajše BBS-generator je generator psevdonaključnih števil, ki so ga leta 1986 predlagali ameriška matematičarka in računalnikarka Lenore Blum, njen mož, venezuelski računalnikar Manuel Blum in Michael Shub.

BBS ima obliko:

xn+1 = (xn)2 mod M

kjer je M=pq produkt dveh velikih praštevil p in q. V vsakem koraku algoritma, je izhodna vrednost dobljen iz xn. Izhodna vrednost je običajno ali bit sodosti xn ali en ali več od najmanj pomembnih bitov xn.

Praštevili p in q morata biti kongruentni 3 (mod 4) (to zagotavlja, da ima vsak kvadratni ostanek en kvadratni koren, ki je tudi kvadratni ostanek) in D(φ(p-1), φ(q-1)) mora biti majhen, kar poveča dolžino cikla.