From Hurwitz's theorem about irreducible factor $F_{n-1}(x)$ of degree $\varphi(n-1)$ of $x^{n-1}-1$ we can deduce the following criterion for the primality of $N=2^m \cdot p_1^{n_1} \cdot p_2^{n_2} \cdot \ldots \cdot p_k^{n_k} +1$ :
Let $N=2^m \cdot p_1^{n_1} \cdot p_2^{n_2} \cdot \ldots \cdot p_k^{n_k} +1$ , $m>0 , n_1>0 ,n_2>0, \ldots ,n_k>0$ with $k$ fixed odd primes $\{p_1,p_2, \ldots ,p_k \}$ , $p_i<p_j$ for $i<j$. Let $q$ be a product of $p_1,p_2, \ldots ,p_k $ and let $\Phi_n(x)$ be the nth cyclotomic polynomial . If there exists an integer $a$ such that $$\Phi_q\left(-a^{(N-1)/2q}\right)\equiv 0 \pmod{N}$$ then $N$ is a prime.
You can run this test here.
My question is: What is the most efficient algorithm for calculating $\Phi_q(b) \operatorname{mod} N$ , where $b$ is an integer?
I know that $\Phi_q(b)$ can be calculated by using repeated polynomial division (see Algorithm 1 in this paper). I also know that there is an algorithm (see Algorithm 2 in the paper mentioned above) for calculating $\Phi_{mp}(x) \operatorname{mod} M$ , where $m$ is an odd squarefree integer , $p$ is a prime not dividing $m$ and $M$ is a prime , but I am not sure if these two algorithms can be used for efficiently calculation of $\Phi_q(b) \operatorname{mod} N$ .
