Frobenius pseudoprime
Encyclopedia
In number theory
, a Frobenius pseudoprime is a composite number
which passes a three-step probable prime
test set out by Jon Grantham in section 3 of his paper "Frobenius pseudoprimes". Although a single round of Frobenius is slower than a single round of most standard tests, it has the advantage of a much smaller worst-case per-round error bound of 1/7710, which would require 7 rounds to achieve with the Miller–Rabin primality test according to best known bounds.
which obeys an additional restriction beyond that required for a Frobenius pseudoprime.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, a Frobenius pseudoprime is a composite number
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
which passes a three-step probable prime
Probable prime
In number theory, a probable prime is an integer that satisfies a specific condition also satisfied by all prime numbers. Different types of probable primes have different specific conditions...
test set out by Jon Grantham in section 3 of his paper "Frobenius pseudoprimes". Although a single round of Frobenius is slower than a single round of most standard tests, it has the advantage of a much smaller worst-case per-round error bound of 1/7710, which would require 7 rounds to achieve with the Miller–Rabin primality test according to best known bounds.
Strong Frobenius pseudoprimes
A strong Frobenius pseudoprime is a pseudoprimePseudoprime
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.- Definition :...
which obeys an additional restriction beyond that required for a Frobenius pseudoprime.
External links
- Symmetric Pseudoprimes at MathPages