My first post

Hi all,
I've made this blog on purpose of Google Summer of Code 2013 initiative.
I am enthusiast of Number Theory so the project I've chose is to develop the FLINT library.

The first test task for me is to write a simple C program which enables user to find a primitive root $\pmod{n}$, where $n$ is any ulong.

A primitive root $\pmod{n}$ is the element in $Z_n$ which has a multiplicative order equals to Euler's totient of $n$ ( $\varphi(n)$ ) - so the maximal case, which is sometimes not possible case. A primitive root $\pmod{n}$ may exist or not depending on $n$. It exists iff $n$ is a prime, or 2*prime or any power of an odd prime or 2*(any power of an odd prime). If primitive roots exist, there are $\varphi(\varphi(n))$ primitive roots modulo $n$. If you found one of them, say $g$, you can generate others by proper exponentiation of $g \pmod{n}$. In order to obtain remain primitive roots, you should use powers which are not divisible by any divisor of $\varphi(n)$.

There is no general strategy on finding primitive root $\pmod{n}$.
A simple case are Fermat Primes, i.e. prime numbers of the form $F_k=2^{2^k} + 1$ for any integer $k$.
In the case, the set of primitive roots is identical to the set of quadratic non-residues $\pmod{n}$ (elements $x$ of $Z_{F_k}$ which have Jacobi symbol $(\frac{x}{F_k})$ equal to $-1$).

In general, $g$ is a primitive root $\pmod{n}$ iff two following sentences are true:
1. $n$ is of the form: $p$ or $2p$ or any power of an odd prime or 2*(any power of an odd prime).
2. $g^{\frac{\varphi(n)}{d_i}}$ is not equal to $1\pmod{n}$ for all $i$ where $d_i$ is a $i$-th divisor of $\varphi(n)$.

There are two approaches on finding any primitive root modulo $n$:
1. Find the smallest primitive root modulo $n$: Iterate $g$ from $2$ to $n-2$ and check if $g$ is a primitive root modulo $n$. Not every value can be a primitive root. One can omit values which are perfect squares. In order to find the smallest primitive root we can omit each values which are divisible by any squares, i.e. $4,9,25$, etc...
2. Find a random primitive root modulo $n$: get a random $g$ from $2$ to $n-2$ and check if $g$ is a primitive root modulo $n$. Again, one can omit values which are perfect squares.

Let's code!