Sieve algorithms for perfect power testing (Q2366224): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 17:56, 2 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sieve algorithms for perfect power testing |
scientific article |
Statements
Sieve algorithms for perfect power testing (English)
0 references
29 June 1993
0 references
Many tests for primality of \(n\) first require the elimination of the case where \(n\) is a perfect \(k\)-th power. This is negligible compared with the main primality routines, so it is usually ignored. There is a rich variety of methods including Newton's root extraction with starting value found by counting digits, modular tests for \(k\) power and search for small prime divisors (for elimination). On a more sophisticated level there is the (logarithmic number of) parallel processors, and the ERH to bound the trial moduli for power tests. (This requires a small table for efficiency.) The worst case is \(O(\log^ 3 n)\), the average is \(O(\log^ 2 n)\), and \(O(\log n)\) is the median.
0 references
Newton's method
0 references
sieve algorithm
0 references
parallel algorithms
0 references
average-case analysis
0 references