On distinguishing prime numbers from composite numbers (Q594912)
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:
scientific article; zbMATH DE number 3834048
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On distinguishing prime numbers from composite numbers |
scientific article; zbMATH DE number 3834048 |
Statements
On distinguishing prime numbers from composite numbers (English)
0 references
1983
0 references
nearly polynomial time
0 references
probabilistic algorithm
0 references
deterministic algorithm
0 references
primality testing
0 references
Jacobi sum
0 references
pseudoprimality tests
0 references
p-th power residue symbols in cyclotomic fields
0 references
This is an important paper which presents an algorithm that decides whether a given number \( {n} \) is prime or composite within \( (\log n)^{c \log \log \log n} \) steps, where \( c \) is an effectively computable positive constant. For practical purposes, the complexity of this algorithm may be considered as polynomial in the length, \( \log n \), of the input \( n \). The basic idea behind the algorithm is the use of a set of pseudo-primality tests which involve \(p\)-th power residue symbols in the cyclotomic fields \( Q\left(\mathrm{e}^{2 \pi \mathrm{i} / \mathrm{p}}\right) \), for a special finite set of primes \( \mathrm{p} \) which depends on the input \( n \). Information from these tests is combined in such a way that the conclusion can be drawn whether or not \( n \) is prime. The paper relies heavily on concepts from algebraic number theory.
0 references