### Finding primitive roots

First off, it has to be noted that the constraint that the modulo value is a prime number is just for simplicity (hint: all values from 1 to**p-1**are coprime to

**p**for a prime number

**p**).

Now, what EVEN is a primitive root modulo p you may ask. This is just a number

**g**which generates all numbers from

**1**to

**p-1**with \(g^{t} \: mod \: p\). That is, for every positive integer

**x < p**there exists a

**t**, so that \(g^{t} \equiv x \pmod{p}\).

Properties of primitive roots:

- for a given p there are phi (phi(p))=phi(p-1) primitive roots
- g is a primitive root \( \Leftrightarrow\) for every divisor d of \((p-1)=phi(p)\), \(g^{d} \not\equiv 1\pmod{p}\) holds \( \Leftrightarrow\) for every prime \(x\) from the prime factorization of \(p-1\), \(g^{(p-1)/x} \not\equiv 1\pmod{p}\) holds.

*(comment: this is essentially there to check for repeating sequences in \(g^{t}\) for \(t \in {1,..,p-1} \pmod{p}\).*

- the lower bound for the number of primitive roots is \(0.15 \cdot p\). Therefore, 15% of the numbers smaller than \(p\) are primitive roots for a given p (
**in worst case!**). By selecting a random positive integer**< p**we have a 15% chance of selecting a primitive root! - given a random p, the chance of hitting a primitive root on random is even ~40%.

Therefore, in order to find a primitive root, we may simply pick up random numbers and check the above property which has to hold for primitive roots. Code which does that: link.

### Now to the discrete logarithm (the index):

for a given**x**, how to find a \(y=ind_{g}(x)\) with \(g^{y} \equiv x \pmod{p}\). The answer is: you can't. Many encryption algorithms are based on this fact. Though, they have some nice properties as normal logarithms:

- \(ind_{g}(ab) \equiv ind_{g}(a) + ind_{g}(b)\pmod{p-1} \)
- \(ind_{g}(a^{k}) \equiv k \cdot ind_{g}(a)\pmod{p-1} \)

Useful links:

- Wiki - Wiki(discrete logratihm) - Finding primitive roots - Index properties

## No comments:

## Post a Comment