Prime Numbers And Primality Testing
Written by Mike James   
Thursday, 27 June 2019
Article Index
Prime Numbers And Primality Testing
Primes & Primality Testing
Almost Sure Its Prime

Pick a prime, any prime…

To return to primality testing.

You might think that the simplest way to create a randomized test that n is prime is to simply pick random values between 2 and n and see if they divide n.

The more you pick and fail to find a divisor the more certain you are that n is prime. While this is a randomized primality test it isn’t a particularly good one and there are much, much better ones, both in terms of the amount of work they require you to do and the level of certainty they provide.

Any number which passes a randomized test with a high probability is referred to as a “pseudo-prime”.

Currently one of the best known and most used test is Rabin’s Strong Pseudoprimality test and it’s interesting enough to explain in more detail.

If the number we want to test is n, assumed odd, first we have to find d and s such that

 n-1=2sd  

where d is also odd (this is easy to do, try it).

Next we pick an x smaller than n and form the sequence:

xd, x2d, x4d, x8d, … xn-1  (mod n)

all calculated modulo n.

Calculating modulo n simply means use “clock arithmetic” with the clock wrapping round to zero at n-1. For example, counting mod 6 goes 0,1,2,3,4,5,0,1,2,3,4,5,0 and so on as the clock wraps round at 5 back to 0 again.

Once you have the sequence of values –  called a “Miller-Rabin sequence” – you can be sure that if n is a prime the sequence ends in a 1.

How does this help with a randomized primality test?

Simple, just pick a value of x less than n and compute the Miller-Rabin sequence. If it doesn’t end in a 1, then the number is composite and not a prime. Notice that if it does end in a 1 then this doesn’t prove it is a prime because some composite numbers produce Miller-Rabin sequences that end in a 1.

The reason why this is such a good test is that if n isn’t a prime just less than three-quarters of all the x values you could pick at random produce Miller-Rabin sequences that don’t end in a 1.

So if you pick one value at random and it gives a sequence that ends in a 1 the probability is one in four that it is really a composite non-prime.

Pick 2 and the probability goes down to one sixteenth. If you continue picking M numbers that give a sequence that ends in 1, this means that the probability that you have a non-prime is ¼M.

For example, if you get sequences that end in 1 with 100 random values then the probability that you have a non-prime number is ¼10 which is roughly 1/1061 which is exceeding unlikely and so you are safe in concluding that the number is indeed prime.

Such is the strange reasoning behind randomized testing for primes, and many other randomized algorithms. They never produce certainty but what is the practical difference between a probability of 1/1061 and certain proof?

There is more chance of a machine malfunction giving you the wrong answer computing a certain proof of primality than the Strong Pseudoprimality test failing!

Certainty restored?

So if knowing that a number is probably a prime is almost as good as knowing that it certainly is what’s the fuss about?

There is still the philosophical point that a mathematical proof reveals a deeper truth than some random chance that something is true.

What is more surprising is that the proof is so very simple and that it has remained undiscovered for so long.

The problem also seems, on the face of it, to be an NP problem. That is the brute force way of testing a prime takes exponential time but if you give me a factor I can check that the number isn't prime with a single division. All NP problems are difficult to compute but easy to check.

Also notice that proving a number to be a prime or not a prime doesn't actually help with the factoring problem. If you know a number is prime then it doesn't have factors but if you prove the number to be non-prime you still don't know what its factors are.

Now consider what this means for the rest of the foundation of our cryptographic security. It is not that we can test primes fast that is important for the cryptography in general. It is more that something that we thought was difficult turns out to be easy.

We assume that because something is difficult and because mathematicians have been working on the problem for years, centuries even, that the problem must really be difficult, intrinsically difficult. This is the assumption behind the factoring problem that many code systems rely on.

Suppose now that the next problem Agrawal, Kayal, and Saxena, or some similar group, turn their attention to is factoring. Perhaps what was always assumed to be difficult will turn out not be if a sufficiently fresh approach is taken to the problem.

Perhaps this has already happened.

Answer to the factor problem:
2760727302559 and 2760727302517. 

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

theorycover

Contents

  1. What Is Computable?
  2. Finite State Machines
  3. What is a Turing Machine? 
  4. Computational Complexity
  5. Non-computable numbers
  6. The Transfinite
  7. Axiom Of Choice
  8. Lambda Calculus
  9. Grammar and Torture
  10. Reverse Polish Notation - RPN
  11. Introduction to Boolean Logic
  12. Confronting The Unprovable - Gödel And All That
  13. The Programmer's Guide to Fractals
  14. The Programmer's Guide to Chaos*
  15. Prime Numbers And Primality Testing
  16. Cellular Automata - The How and Why
  17. Information Theory
  18. Coding Theory
  19. Kolmogorov Complexity

*To be revised

Related Articles

The Mod function       

Public Key Encryption  

Public Key Cryptography Set To Fail In Five Years       

Solve The Riemann Hypothesis With A Quantum Computer       

48th Mersenne Prime Computed       

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook or Linkedin.

 

square

 



 

Comments




or email your comment to: comments@i-programmer.info

 

<ASIN:3540403442>

<ASIN:0387252827>

<ASIN:0471462349>

<ASIN:0387970401>

<ASIN:0385495323>

<ASIN:3540430725>

<ASIN:0387772677>

 



Last Updated ( Thursday, 27 June 2019 )