Primality Testing For Huge Integers July 23, 2015

Primality – Fermat and Miller-Rabin

HUGE Prime Numbers, and how to find them, provides the very foundation for what we do on the internet. Whenever we enter a password, or buy something from Amazon, or check our bank balances we are, behind the scenes, using security software that performs encryption on the data that travels back and forth on the internet. And that software relies on the ability to QUICKLY find Prime numbers that are hundreds of digits long. That said…and as usual…

Lock The Gates!!!

Anywho, I started reading up on cryptography which, of course, led to that topic of prime numbers and in particular, very large prime numbers and how to find them. Again, we’re talking about huge numbers with hundreds of digits! There are lots of very good books and web sites that deal with cryptography and necessarily with large primes and how to generate them. At the end of this post there is a list of links with associated comments to help you (and to serve as a reminder to myself in the future?).

Luckily the cryptography and “primality” reading led to yet another hobby program in C-Sharp (C#). Of course, there are sufficient examples of similar code to be found on the internet but I think you’ll find the code detailed here is significantly more instructive due to its clarity (variable and procedure names) and the comments included.

If you are interested, the entire Visual Studio C# WinForms project

is provided here as a ZIP file. To download it just click HERE

“PrimeTest” is the name of project and resulting exe file. It was created with Visual Studio 2013 Community Edition. The C# code you’ll want to examine is the file Form1.cs

Of course, as with many (most?) C# Winforms projects, you’ll want the latest version of .Net installed.

There is just 1 screen (a sample screen-print is below).

PrimeTest example screen

On the screen you provide a starting number along with a count of how many numbers to test beginning with the Start Number. For example, if you specify a Start Number of 100 and you specify 100 for how many numbers to test then the program will do Primality testing for 100 thru 199.

There is a processing option for showing only the final statistics (un-check this option to see individual testing details).

There is a processing option for showing only information for Primes detected. Details about composite odd numbers encountered will not be logged unless you un-check the option ShowPrimeResultsOnly). Even numbers are never tested for primality (obviously?).

The program will test numbers for Primality using either the Fermat Little Theorem technique or the Miller-Rabin technique (or both). Each of these techniques uses a “confidence” (iteration) number that you can specify (you’ll read about this parameter on various web sites if you haven’t already… no need to explain it here).

Then just click the GO button.

I suggest that you start playing with the program by using a Start Number of 1 and a “How many numbers to test” value of 100 to see what happens.

When you run the program, especially with smaller numbers and/or very small values for “Confidence Iterations” you will often see differences between the results for the Fermat technique and the Miller-Rabin technique (as you should!). This is especially true for the “Carmichael Numbers.” To see this, try using a Start Number of 1, How Many Numbers to Test of 1,000, and a Confidence/Iterations value of 2, 3, or 4.

I guess it’s obvious but using the BigInteger class is the main thing that makes this simple test program possible. This is the second program for this blog that uses BigInteger.

Note that the program has only been tested for integers up to 300 digits.

Now for my conspiracy theory…

If I were the NSA, I would have the compiler place back-doors in the resulting code whenever the BigInteger class is used and certainly whenever the BigInteger.ModPow() method is used. I mean, after all… who else but someone interested in encryption would use that stuff (especially ModPow() !!!! ). But I am thinking that has already been done.

The following links will get you started. Enjoy.

Khan Academy – Take the entire Cryptography course. Highly recommended!!!

https://www.khanacademy.org/computing/computer-science/cryptography

Listed on the main page and of particular interest are the sections on: