Cyclotomic primality testing algorithm

Our final goal is to implement the APR-CL algorithm, but let's start with something simple. The Cyclotomic primality testing algorithm discribed in Four primality testing algorithms well suited for this goal. This algorithm is based on the theorem, described in a previous post.


Let the $n$ be a number for primality testing. The algorithm can be divided into three stages: 

1. Preparation. We need to select integer numbers $R$ and $s$ such that $s=\prod\limits_{\substack{q-1|R \\ q \text{ prime}}}q$, $\sqrt{s} > n$ and $R$ is as small as possible.
2. Gauss sum tests. For all primes $q$ dividing $s$ and for each prime power $r$ that divides $q - 1$ we make sure that $gcd(n, qr) = 1$ and then check conditions for Gauss sum for character $\chi:(\mathbb{Z}/q\mathbb{Z})^*\to\mu_r$.
3. Search divider. For each integer $k < R$ check that $(n^k \bmod s) | n$. If that never happens, then $n$ is prime.

The Gaussian sum $\tau(\chi) = - \sum\limits_{q \in (\mathbb{Z}/q\mathbb{Z})*} {\zeta_p^x\chi(x)}$ . The character $\chi(x)$ can be constructed by the following formula: $\chi(g^m)=\zeta_q^m$ for each integer $m$, there $g$ is the primitive root modulo $q$. 

So, the Gauss sum $\tau(\chi) \in \mathbb{Z}[\zeta_q, \zeta_p]$. This structure can be represented as a matrix or as a vector of polynomials (vector of $\mathbb{Z}[\zeta]$ elements, implemented here). That's what I'm going to do in the next days.

We now have implementation of function $f(m)$ such that $\chi(m)=\zeta_q^{f(m)}$. We also have implementation of first step of algorithm.

When I implement operations in $\mathbb{Z}[\zeta_q,\zeta_p]$ we will be able to check the two conditions of Theorem 4.2 from the "Four primality testing algorithms" paper.