Machtsgenerator
Een machtsgenerator is een pseudotoevalsgenerator, een algoritme dat pseudotoevalsgetallen produceert. Dat zijn getallen die deterministisch worden voortgebracht en dus niet echt willekeurig zijn, maar veel eigenschappen van toevalsgetallen hebben.

Definitie
Een machtsgenerator is een algoritme voor het berekenen van de rij  via de recursieve relatie:

;

Daarin zijn  (de startwaarde),  en  gehele getallen zodanig dat ggd.

Voor de gegenereerde getallen geldt: .

De machtsgenerator heeft veel toepassingen op het gebied van cryptografie. Daarnaast zijn pseudotoevalsgetallen ook van belang voor numerieke simulaties van Monte Carlo-methoden, numerieke analyse, het testen van computerchips voor gebreken en de programmering van speelautomaten. Verschillende toepassingen vereisen verschillende eigenschappen van de getallen.

Complexiteit
Voor een machtsgenerator met  een priemgetal en periode  kan de lineaire complexititeit L afgeschat worden door:
.

RSA-generator
Een bijzonder geval van een machtsgenerator is de RSA-generator.
Als  zodanig gekozen wordt dat , met  de Eulerfunctie, wordt de generator RSA-generator genoemd. Het is aangetoond dat als de periode  van de rij  voldoet aan de ongelijkheid  voor een gegeven , dan zijn de fracties  uniform verdeeld op het interval [0,1].

Blum-Blum-Shub generator
Een ander speciall geval is de Blum-Blum-Shub-generator,
Als , wordt de generator Blum-Blum-Shub-generator genoemd, bedacht  door Lenore Blum, Manuel Blum and Michael Shub in 1986.
Deze generator is van de vorm , met  het product van twee grote priemgetallen  en . Bij elke stap van het algoritme wordt een uitkomst verkregen uit het berekende getal . Die uitkomst is meestal de pariteitsbit van  of een of meer van de minst significante bits van .

De beginwaarde  moet een geheel getal zijn ongelijk aan 1 en . De priemgetallen  en  moeten beide modulo 4 congruent zijn met 3 (dit garandeert dat elk kwadratisch residu een wortel heeft die ook een kwadratisch residu is) en  moet klein zijn (dit maakt de cycluslengte groot).

Een interessant kenmerk van de Blum-Blum-Shub-generator is de mogelijkheid om elke  rechtstreeks te berekenen (via de stelling van Euler).

Beveiliging
De Blum-Blum-Shub-generator is niet geschikt voor gebruik in simulaties, alleen voor cryptografie, omdat het algoritme erg traag is. Het heeft wel een ongewoon sterke beveiliging; de kwaliteit van de generator hangt af van de rekentechnische moeilijkheid van het ontbinden in priemfactoren.

Als factorisatie in priemfactoren moeilijk is (zoals wordt vermoed), zou de Blum-Blum-Shub-generator met grote  een output moeten hebben vrij van niet-willekeurige patronen die kunnen worden ontdekt met niet te veel berekeningen. Zo lijkt het net zo veilig als andere encryptietechnologieën gebonden aan de factorisatieprobleem, zoals RSA-encryptie.

Lineaire complexiteit
Neem aan dat de rij  periodiek is met periode . Dan geldt voor de lineiare complexiteit  van de Blum-Blum-Shub-generator de afschatting:
.

Met behulp van van de Chinese reststelling kan men zien dat de lineaire complexiteit modulo een samengesteld getal  gelijk is aan de grootste lineaire complexiteit modulo alle priem machtsdelers van . Dit geldt inderdaad als , met  relatief priem en als een zekere oneindige rij  voor  voldoet aan de congruenties:

en

We zetten  voor  en definiëren vervolgens integers
 met 
vanuit de congruenties:
 en .

Dan geldt dat 

Daarom geldt dat voor een Blum-integer  met  dat de lineaire complexiteit  de volgende formule niet overschrijdt:

met  en  de lineaire complexiteit en de periode modulo  en  en  de lineaire complexiteit en de periode modulo .

In het meest interessante geval voor toepassing, namelijk als de periode  van orde  is, geven bovenstaande formules dat  van grootst mogelijke orde  is.

Referenties
Cusick, T.W., C. Ding, and A. Renvall, Stream ciphers and number theory, Elsevier (2004)

Shparlinski, I., On the linear complexity of the power generator, School of MPCE (2001)

Algoritme
Informatietheorie