On the running time of the Adleman-Pomerance-Rumely primality test (Q2714158)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the running time of the Adleman-Pomerance-Rumely primality test |
scientific article; zbMATH DE number 1603946
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the running time of the Adleman-Pomerance-Rumely primality test |
scientific article; zbMATH DE number 1603946 |
Statements
12 June 2001
0 references
primality tests
0 references
pseudoprimes
0 references
Carmichael's \(\lambda\)-function
0 references
On the running time of the Adleman-Pomerance-Rumely primality test (English)
0 references
Let \(f(n)\) denote the least positive square free integer such that the product of the primes \(q\) with \(q-1\mid f(n)\) exceeds \(\sqrt n\). The function \(f\) plays an important role in the running time analysis of the Adleman-Pomerance-Rumely primality test [\textit{L. M. Adleman, C. Pomerance} and \textit{R. S. Rumely}, Ann. Math. (2) 117, 173-206 (1983; Zbl 0526.10004)]. The authors prove the inequality NEWLINE\[NEWLINE f(n)<(\log n)^{(c_0+c)\log_3 n} \quad (n\geq n_0(\varepsilon)) NEWLINE\]NEWLINE with an explicitly given \(c_0\). In the proof they use theorems on the distribution of primes in residue classes.
0 references
