TOPICS
Search

Witness


A witness is a number which, as a result of its number theoretic properties, guarantees either the compositeness or primality of a number n. 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

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Witness." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Witness.html

Subject classifications