Primality Testing and Jacobi Sums (Q3699757)

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 3924864
Language Label Description Also known as
default for all languages
No label defined
    English
    Primality Testing and Jacobi Sums
    scientific article; zbMATH DE number 3924864

      Statements

      0 references
      0 references
      1984
      0 references
      primality testing
      0 references
      Jacobi sums
      0 references
      computational number theory
      0 references
      version of Adleman-Pomerance-Rumely algorithm
      0 references
      efficiency
      0 references
      Primality Testing and Jacobi Sums (English)
      0 references
      This paper describes a version of the Adleman, Pomerance, and Rumely (APR) primality algorithm. [\textit{L. M. Adleman}, \textit{C. Pomerance} and \textit{R. S. Rumely}, Ann. Math. (2)117, 173--206 (1983; Zbl 0526.10004)]. The new algorithm is both theoretically and computationally simpler than the APR technique. The development of this idea requires a number of results not usually associated with the problem of primality testing. For example, techniques from the theory of cyclotomic fields are used to reformulate the APR test in terms of Jacobi sums. This reformulation results in congruences, involving these sums, which are much easier to test than those needed by the APR algorithm. The exposition of these developments is pretty-well self-contained and the algorithm is discussed in considerable detail. The resulting primality test is very efficient in practice. To give some indication of just how powerful this test is, a PASCAL program implementing the test on CDC Cyber 170-750 computer can routinely handle 100 digit numbers within 45 seconds. Also, a FORTRAN version of this test, implemented on the same machine, can dispose of numbers of up to 200 digits in about 10 minutes or less. These remarkable speeds are much greater than those of any previously developed primality test.
      0 references

      Identifiers

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