Probabilistic Primality Testing (Q7361146)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Probabilistic_Prime_Tests
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Probabilistic Primality Testing |
AFP entry Probabilistic_Prime_Tests |
Statements
11 February 2019
0 references
Daniel Stüwe
0 references
Manuel Eberl
0 references
Probabilistic Primality Testing (English)
0 references
The most efficient known primality tests are probabilistic in the sense that they use randomness and may, with some probability, mistakenly classify a composite number as prime – but never a prime number as composite. Examples of this are the Miller–Rabin test, the Solovay–Strassen test, and (in most cases) Fermat's test. This entry defines these three tests and proves their correctness. It also develops some of the number-theoretic foundations, such as Carmichael numbers and the Jacobi symbol with an efficient executable algorithm to compute it.
0 references
