n_is_prime_pocklington

Most of the time goes into factoring $n - 1$ with n_factor_partial (trial division, then Hart's one-line algorithm [Har2012] or SQUFOF), which stops once the factored part $F$ of $n - 1$ is at least $(n - 1)^{1/3}$. If $F \le \sqrt n$, the cube root criterion of Brillhart, Lehmer and Selfridge is applied in addition. Then, for each prime $q$ dividing $F$, n_is_prime_pocklington tries the bases $a = 2, 3, \ldots, \mathit{iterations} - 1$ until $a^{(n-1)/q} \ne 1$, returning 0 if some $a^{n-1} \not\equiv 1 \pmod n$ and $-1$ if no base works. Finally it checks that $n$ is coprime to the product of the values $a^{(n-1)/q} - 1$. In most cases a larger number of iterations hardly affects the running time.