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.