In number theory, a Frobenius pseudoprime is a pseudoprime, whose definition was inspired by the quadratic Frobenius test described by Jon Grantham in a 1998 preprint and published in 2000. Frobenius pseudoprimes can be defined with respect to polynomials of degree at least 2, but they have been most extensively studied in the case of quadratic polynomials. Frobenius pseudoprimes w.r.t. quadratic polynomials Definition of Frobenius pseudoprimes with respect to a monic quadratic polynomial , where the discriminant is not a square, can be expressed in terms of Lucas sequences and as follows. A composite number n is a Frobenius pseudoprime if and only if and where is the Jacobi symbol. When condition (2) is satisfied, condition (3) becomes equivalent to Therefore, Frobenius pseudoprime can be equivalently defined by conditions (1-2) and (3), or by conditions (1-2) and (3′). Since conditions (2) and (3) hold for all primes which satisfy the simple condition (1), they can be used as a probable prime test. (If condition (1) fails, either the greatest common divisor is less than , in which case it is a non-trivial factor and is composite, or the GCD equals , in which case you should try different parameters and which are not multiples of .) Relations to other pseudoprimes Every Frobenius pseudoprime is also a Lucas pseudoprime with parameters , since it is defined by conditions (1) and (2); a Dickson pseudoprime with parameters , since it is defined by conditions (1) and (3'); a Fermat pseudoprime base when . Converse of none of these statements is true, making the Frobenius pseudoprimes a proper subset of each of the sets of Lucas pseudoprimes and Dickson pseudoprimes with parameters , and Fermat pseudoprimes base when . Furthermore, it follows that for the same parameters , a composite number is a Frobenius pseudoprime if and only if it is both Lucas and Dickson pseudoprime. In other words, for every fixed pair of parameters , the set of Frobenius pseudoprimes equals the intersection of the sets of Lucas and Dickson pseudoprimes. While each Frobenius pseudoprime is a Lucas pseudoprime, it is not necessarily a strong Lucas pseudoprime. For example, 6721 is the first Frobenius pseudoprime for , which is not a strong Lucas pseudoprime. Every Frobenius pseudoprime to is also a restricted Perrin pseudoprime. Analogous statements hold for other cubic polynomials of the form . Examples Frobenius pseudoprimes with respect to the