Four primality testing algorithms

Publication date 24 March 2009

Full work available at URL https://arxiv.org/abs/0801.3840

AKS algorithm cyclotomic primality test elliptic curve primality test Miller-Rabin test primality tests

Abstract: In this expository paper we describe four primality tests. The first test is very efficient, but is only capable of proving that a given number is either composite or 'very probably' prime. The second test is a deterministic polynomial time algorithm to prove that a given numer is either prime or composite. The third and fourth primality tests are at present most widely used in practice. Both tests are capable of proving that a given number is prime or composite, but neither algorithm is deterministic. The third algorithm exploits the arithmetic of cyclotomic fields. Its running time is almost, but not quite polynomial time. The fourth algorithm exploits elliptic curves. Its running time is difficult to estimate, but it behaves well in practice.

Recommendations

Cited in

(22)

This page was built for publication: Four primality testing algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3615921)