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
      0 references
      0 references
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references