GSoC week 2 and Gauss sums

As described earlier, we need to implement the operation in $\mathbb{Z}[\zeta_p, \zeta_q]$. We can represent $x$ from $\mathbb{Z}[\zeta_p, \zeta_q]$ as vector of size $p$ of $\mathbb{Z}[\zeta_q] = \mathbb{Z}[X]/(X^q-1)$. 

The addition of $x, y \in \mathbb{Z}[\zeta_p, \zeta_q]$ is just elementwise addition of polys $x[i] + y[i]$ for $i \in [0, p-1]$.
For multiplication $z = x * y$ from $\mathbb{Z}[\zeta_p, \zeta_q]$ we set
$$z[i +j\pmod{p}] \mathrel{+}= x[i]*y[j]\pmod{X^q-1} \text{ for } i,j<p$$

It will also be useful to have some memory management, comparison, powering and multiplication on $\zeta_p^k$ functions.

Now when we have structure to work with the elements of the $\mathbb{Z}[\zeta_p,\zeta_q]$ we can compute Gauss sum $\tau(\chi)$ for Dirichlet character $\chi_{p, q}$. $$\tau(\chi)=\sum\limits_{x \in (\mathbb{Z}/q\mathbb{Z})^*}{\chi(x)\zeta_q^x}=\sum\limits_{j=1}^{q-1}{\zeta_p^j\zeta_q^{g^j}}$$, there $g$ is the primitive root modulo $q$.

So, we now can compute Gauss sums. For test $n$ for primality we must check two conditions of the theorem 4.2 from "Four primality testing algorithms" for all $q$ and prime powers $r|q-1$:

• for every prime $t$ dividing $n$ there exists $t\lambda_t$ in the ring $\mathbb{Z}_l$ of $l$-adic integers such that: $$t^{l-1}=n^{(l-1)\lambda_t} \in \mathbb{Z}_l^*$$
• $\tau^{\sigma_n-n}(\chi)  \in \langle\zeta_p\rangle$ in the ring $\mathbb{Z}[\zeta_p, \zeta_q]/(n)$

$\tau^{\sigma_n}(\chi)=\tau(\chi^n)$, so the second condition can be checked as:
$$\tau(\chi^n)=\zeta_p^i*\tau^n(\chi) \text{ for some }i$$
The example how this works can be found in the unit-test for Gauss sum and in the Gauss sum primality test. 

The first condition  can be checked using Proposition 4.3 and Claim 2.

When I finally implement first condition the Gauss sum test will be finished and we can continue to implement APR-CL. In the beginning I need to rewrite operations in $\mathbb{Z}[\zeta_p]$ more carefully.