[Math] Primitive root

In cyclic group, a 'generator' is an entiry that can 'generate' all elements of the group.

Look at this: $g^x \mod{13}$, where x=1..12.

What $g$ can be so that that expression would generate all possible outputs in range of 1..12?

The PrimitiveRootList[] function in Wolfram Mathematica can find these generators:

In[]:= PrimitiveRootList[13]
Out[]= {2,6,7,11}

So $g$ can be either of 2,6,7,11.

Let's check this 'generator':

In[]:= a=Table[Mod[2^x,13],{x,1,100}]
Out[]= {2,4,8,3,6,12,11,9,5,10,7,1,2,4,8,3,6,12,11,9,5,10,7,1,2,4,8,3,6,12,11,9,5,10,7,1,2,4,8,3,6,12,11,9,5,10,7,1,2,4,8,3,6,12,11,9,5,10,7,1,2,4,8,3,6,12,11,9,5,10,7,1,2,4,8,3,6,12,11,9,5,10,7,1,2,4,8,3,6,12,11,9,5,10,7,1,2,4,8,3}

In[]:= FindRepeat[a]
Out[]= {2,4,8,3,6,12,11,9,5,10,7,1}

In[]:= Length@FindRepeat[a]
Out[]= 12

For $x=1..\infty$, this expression generates all possible values in 1..12 range (except zero), then the cycle repeating infinitely. We can say, that this expression 'permutate' the 1..12 range.

You can view this as a permutation of 1..12 range.

Other primitive roots will be OK as well, but order may be different:

In[]:= a=Table[Mod[6^x,13],{x,1,100}]
Out[]= {6,10,8,9,2,12,7,3,5,4,11,1,6,10,8,9,2,12,7,3,5,4,11,1,6,10,8,9,2,12,7,3,5,4,11,1,6,10,8,9,2,12,7,3,5,4,11,1,6,10,8,9,2,12,7,3,5,4,11,1,6,10,8,9,2,12,7,3,5,4,11,1,6,10,8,9,2,12,7,3,5,4,11,1,6,10,8,9,2,12,7,3,5,4,11,1,6,10,8,9}

In[]:= FindRepeat[a]
Out[]= {6,10,8,9,2,12,7,3,5,4,11,1}

In[]:= Length@FindRepeat[a]
Out[]= 12

But other 'generators' wouldn't work. Try g=4:

In[]:= a=Table[Mod[4^x,13],{x,1,100}]
Out[]= {4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9,10,1,4,3,12,9}

In[]:= FindRepeat[a]
Out[]= {4,3,12,9,10,1}

In[]:= Length@FindRepeat[a]
Out[]= 6

g=4 as 'generator' makes shorter cycle. It doesn't enumerate all numbers in 1..12 range.

Modulo may not be a prime number, by the way. Composite numbers are OK.

Primitive roots is used in Diffie–Hellman key exchange. Stay tuned to my blog -- I'll explain soon how it works.

List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.