## Thursday, February 27, 2014

### 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}$$.
Some research: I've ran this code to look at the distribution of the primitive roots for primes between 100 and 1,000,000,000. By running the code we see this from the output:
• 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}$$
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}