Frobenius Pseudoprimes Let f(x) ∈ Z[x] be a monic polynomial of degree d with

discriminant Δ. An odd integer n > 1 is said to pass the Frobenius probable prime test with respect to f(x) if we have gcd(n, f(0)Δ) = 1, and n is declared to be a probable prime by the following algorithm. (Such an integer will be called a Frobenius probable prime with respect to f(x).) All computations are done in (Z/nZ)[x].

Factorization Step Let f_{0}(x) = f(x) mod n. For 1 ≤ i ≤ d, let F_{i}(x) = gcd(x^{n^{i}} − x, f_{i−1}(x)), and let f_{i}(x) = f_{i−1}(x)/F_{i}(x). If any of the gcds fail to exist, declare n to be composite and stop. If f_{d}(x) ≠ 1, declare n to be composite and stop.

Frobenius Step For 2 ≤ i ≤ d, compute F_{i}(x^{n}) mod F_{i}(x). If it is nonzero for some i, declare n to be composite and stop.

Jacobi Step Let S = ∑_{2|i} deg(F_{i}(x))/i.

If (−1)^{S} ≠ (\frac{Δ}{n}), declare n to be composite and stop.

A Theorem in Analytic Number Theory

Let f(t) ∈ Z[t] be a monic polynomial with splitting field K, [K : Q] = n. Then we have real numbers x_{1/3}, η_{1/3} > 0 and an integer q_{1/3}(x) > log x, depending on K, such that the following statement holds. If q ≤ x^{η_{1/3}}, gcd(a, q) = 1, q_{1/3}(x) |̸q, x ≥ x_{1/3} and x^{1/2} < y < x, then the number of primes p < y that are a mod q and such that f(t) splits into linear factors mod p (equivalently, p splits completely in K) is at least \frac{1}{2ϕ(q)nπ(x)}.