Four primality testing algorithms

Details Four primality testing algorithms Four primality testing algorithms

2008-01-24

arxiv.org/abs/0801.3840v1

Mathematics

Number Theory

21 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Four primality testing algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Four primality testing algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Four primality testing algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-412015