|
|
|
A witness is a number which, as a result of its number theoretic properties, guarantees either the compositeness or
primality of a number 
. Witnesses are most commonly used in connection with Fermat's Little Theorem Converse.
A Pratt Certificate uses witnesses to prove primality, and Miller's Primality Test uses witnesses to prove
compositeness.
See also Adleman-Pomerance-Rumely Primality Test, Fermat's Little Theorem Converse, Miller's Primality Test, Pratt Certificate, Primality Certificate