In de cryptografie wordt vaak gebruikgemaakt van zogenaamde generatoren. Dat is bijvoorbeeld het geval voor het Diffie-Hellman-sleuteluitwisselingsprotocol¹. We zeggen dat een getal $$g \in \mathbb{N}_0$$ een generator is van het priemgetal $$p \in \mathbb{N}_0$$ (met $$g < p$$) als het kleinste getal $$n \in \mathbb{N}$$ (met $$n > 1$$) waarvoor $$g^n\ \text{mod}\ p \equiv g$$ gelijk is aan $$p$$. Hierbij staat de operator $$\text{mod}$$ voor de rest na (gehele) deling.

Stel dat $$g = 5$$ en $$p = 7$$. Dan berekenen we de opeenvolgende machten van $$g = 5$$, te beginnen bij de tweede macht, en bepalen telkens de rest na deling door het priemgetal $$p = 7$$. \[ \begin{array}{rcl} 5^2 \mod 7 &=& 4 \\ 5^3 \mod 7 &=& 6 \\ 5^4 \mod 7 &=& 2 \\ 5^5 \mod 7 &=& 3 \\ 5^6 \mod 7 &=& 1 \\ 5^7 \mod 7 &=& 5 \end{array} \] Uiteindelijk zal dit proces altijd terug het getal $$g = 5$$ opleveren en dat gebeurt hier voor het eerst bij de zevende macht. Omdat 7 ook de waarde is van het priemgetal $$p$$, zeggen we in dit geval dat $$g = 5$$ een generator is van $$p = 7$$.

Stel dat $$g = 4$$ en $$p = 7$$. We bepalen opnieuw de opeenvolgende machten van $$g = 4$$ te beginnen bij de tweede macht, totdat dit het getal $$g = 4$$ oplevert. \[ \begin{array}{rcl} 4^2 \mod 7 &=& 2 \\ 4^3 \mod 7 &=& 1 \\ 4^4 \mod 7 &=& 4 \end{array} \] Omdat dit voor het eerst gebeurt bij de vierde macht en 4 niet gelijk is aan het priemgetal $$p$$, zeggen we in dit geval dat $$g = 4$$ geen generator is van $$p = 7$$.

Invoer

Twee getallen $$g, p \in \mathbb{N}_0$$ die elk op een afzonderlijke regel staan. Hierbij geldt dat $$p$$ een priemgetal is waarvoor geldt dat $$g < p$$.

Uitvoer

Bepaal of het getal $$g$$ een generator is van het priemgetal $$p$$. Hiervoor bereken je de opeenvolgende machten van $$g$$, te beginnen vanaf de tweede macht, waarvan je telkens de rest na deling door $$p$$ bepaalt. Dit doe je totdat je voor het eerst terug het getal $$g$$ bekomt (omdat $$p$$ een priemgetal is, is dat altijd het geval). Voor elke macht die hierbij berekend wordt, moet een regel uitgeschreven worden waarvan het formaat en de inhoud kan afgeleid worden uit onderstaande voorbeelden (we stellen hierbij $$m^n$$ voor als m^n).

Nadat je alle machten hebt berekend en daarbij telkens een bijhorende regel hebt uitgeschreven, moet er nog een laatste regel uitgeschreven worden die aangeeft of $$g$$ een generator is van $$p$$. Het formaat van deze regel kan je opnieuw afleiden uit onderstaande voorbeelden.

Voorbeeld

Invoer:

5
7

Uitvoer:

(5^2) mod 7 = 4
(5^3) mod 7 = 6
(5^4) mod 7 = 2
(5^5) mod 7 = 3
(5^6) mod 7 = 1
(5^7) mod 7 = 5
5 is een generator van 7

Voorbeeld

Invoer:

4
7

Uitvoer:

(4^2) mod 7 = 2
(4^3) mod 7 = 1
(4^4) mod 7 = 4
4 is geen generator van 7