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