# 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 $(u_{n})$ via de recursieve relatie:
    $u_{n}=u_{n-1}^{e}{\pmod {m}}$;
Daarin zijn $u_{0}$ (de startwaarde), $m$ en $e$ gehele getallen zodanig dat ggd$(u_{0},m)=1$.
Voor de gegenereerde getallen geldt: $0\leq u_{n}\leq m-1$.
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 $m$ een priemgetal en periode $T$ kan de lineaire complexititeit L afgeschat worden door:
    $L\geq {\frac {T^{2}}{m-1}}$.

## RSA-generator

Een bijzonder geval van een machtsgenerator is de RSA-generator. Als $d$ zodanig gekozen wordt dat $\operatorname {ggd} (e,\varphi (m))=1$, met $\varphi (m)$ de Eulerfunctie, wordt de generator RSA-generator genoemd. Het is aangetoond dat als de periode $T$ van de rij $(u_{n})$ voldoet aan de ongelijkheid $T\leq m^{3/4+\varepsilon }$ voor een gegeven $e>0$, dan zijn de fracties $(u_{n}/m)_{n=1}^{T}$ uniform verdeeld op het interval [0,1].

## Blum-Blum-Shub generator

Een ander speciall geval is de Blum-Blum-Shub-generator, Als $e=2$, 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 $u_{n}\equiv u_{n-1}^{2}\!\!\!{\pmod {m}}$, met $m=pq$ het product van twee grote priemgetallen $p$ en $q$. Bij elke stap van het algoritme wordt een uitkomst verkregen uit het berekende getal $u_{n}$. Die uitkomst is meestal de pariteitsbit van $u_{n}$ of een of meer van de minst significante bits van $u_{n}$.
De beginwaarde $u_{0}$ moet een geheel getal zijn ongelijk aan 1 en $\operatorname {ggd} (u_{0},m)=1$. De priemgetallen $p$ en $q$ moeten beide modulo 4 congruent zijn met 3 (dit garandeert dat elk kwadratisch residu een wortel heeft die ook een kwadratisch residu is) en $\operatorname {ggd} (\varphi (p-1),\varphi (q-1))$ moet klein zijn (dit maakt de cycluslengte groot).
Een interessant kenmerk van de Blum-Blum-Shub-generator is de mogelijkheid om elke $u_{i}$ 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 $m$ 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 $(u_{n})$ periodiek is met periode $T$. Dan geldt voor de lineaire complexiteit $L$ van de Blum-Blum-Shub-generator de afschatting:
    $L\geq T\varphi (m)^{-1/2}$.
Met behulp van van de Chinese reststelling kan men zien dat de lineaire complexiteit modulo een samengesteld getal $m$ gelijk is aan de grootste lineaire complexiteit modulo alle priem machtsdelers van $m$. Dit geldt inderdaad als $m=m_{1}m_{2}$, met $m_{1},m_{2}\geq 2$ relatief priem en als een zekere oneindige rij $(s_{n})$ voor $n=1,2,\ldots$ voldoet aan de congruenties:
    $S_{n+L_{1}}\equiv a_{L_{1}-1}s_{n+L_{1}-1}+\ldots +a_{0}S_{n}{\pmod {m_{1}}}$
en
    $S_{n+L_{2}}\equiv b_{L_{2}-1}s_{n+L_{2}-1}+...+b_{0}S_{n}{\pmod {m}}_{2}$
We zetten $b_{k}=a_{k}=0$ voor $k<0$ en definiëren vervolgens integers
    $0\leq c_{0},\ldots ,c_{L-1}\leq m-1,$ met $L={\rm {max}}\{L_{1},L_{2}\}$
vanuit de congruenties:
    $c_{L-j}\equiv a_{L1-j}{\pmod {m_{1}}}$ en $c_{L-j}\equiv b_{L2-j}{\pmod {m_{2}}}$.
Dan geldt dat $S_{n+L}\equiv c_{L-1}s_{n+L-1}+\ldots +c_{0}S_{n}{\pmod {m}},n=1,2,\ldots$
Daarom geldt dat voor een Blum-integer $m=pq$ met $p\equiv q\equiv m^{1/2}$ dat de lineaire complexiteit $L$ de volgende formule niet overschrijdt:
    $L={\rm {max}}\{L_{p},L_{q}\}\leq {\rm {max}}\{T_{p},T_{q}\}\leq {\rm {max}}\{p,q\}=(1+o(1))m^{1/2},$
met $L_{p}$ en $T_{p}$ de lineaire complexiteit en de periode modulo $p$ en $L_{q}$ en $T_{q}$ de lineaire complexiteit en de periode modulo $q$.
In het meest interessante geval voor toepassing, namelijk als de periode $T$ van orde $m$ is, geven bovenstaande formules dat $L$ van grootst mogelijke orde ${\sqrt {m}}$ is.