Primality Test in Finite Fields

175 Views Asked by At

Is there a name for the following primality test? Was it ever discussed in literature?

We want to test if some $x \in \mathbb{N}$ is a prime number.

Let $p = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot \ldots \cdot p_k +1$ some primorial prime such that $p_k < x < p_{k+1}^2$. And let $g$ be some generator of the finite field $\mathbb{F}_p$. We can test if $x \in \mathbb{N}$ is prime:

\begin{equation} \prod_{i=1}^k (g^{\frac{p-1}{p_i} \cdot x} - 1)^{p-1} \bmod p = \begin{cases} 1 & \text{if}\ x \text{ is prime} \\ 0 & \text{otherwise} \end{cases} \end{equation}

This product implements the trial devision algorithm in $\mathbb{F}_p$.


Furthermore, is there a name for the resulting prime counting function? For all integers $n$ such that $p_k < n < p_{k+1}^2$ the number of primes up to $n$ is: \begin{equation} \pi(n) = k + \sum_{x=1}^n \prod_{i=1}^k (g^{\frac{p-1}{p_i} \cdot x} - 1)^{p-1} \bmod p \end{equation}


Generalization 1: $p$ does not have to be a primorial prime. A prime of the form $p = m \cdot 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot \ldots \cdot p_k +1$ with some $m \in \mathbb{N}$ is sufficient.


Generalization 2: $p$ can even be a composite. It's sufficient if $\varphi(p)$ is divisible by $2,3,5,7,11,\ldots,p_k$.

2

There are 2 best solutions below

1
On

In general there is no finite field $\Bbb{F}_p$ because $p$ need not be prime. Already for $k=6$ you have $$p=2\cdot3\cdot5\cdot7\cdot11\cdot13+1=59\times509.$$

6
On

So for a given $x$ you choose $p_k$ such that $p_k < x < p_{k+1}^2$ and construct $p = 2\cdot 3 \cdots \cdot p_{k}+1$. But $p$ may not be prime, so you need to test if $p$ is prime. So your algorithm for primality test include testing if a (much bigger) number is prime?