Testing for primality

How to test a huge number for primality? Provides an implementation of the famous Miller-Rabin algorithm using the widely available ‘bc’ (basic calculator) tool. Suitable both for Linux and Windows.

Testing if a number is prime is an interesting problem. Prime numbers have uses in many fields especially Cryptography. Here we show a technique through which we can verify if a number is prime or composite (not with 100% guarantee though). The algorithm we use is called Miller-Rabin.

I have, in another blogpost, talked about a tool available on Unix called bc which stands for basic calculator. In truth, its not ‘basic’ by any stretch of imagination. For my Windows brethren, a version is part of UnxUtils. This tool allows you to do large number, arbitrary precision calculations. It also allows you to write scripts. The script to implement this test is called pcheck.bc.

On Unix, it can be run using ./pcheck.bc while on windows it needs to be run like this:

bc pcheck.bc -ql.

The '-l' option is for bc to load math. library, and the '-q' option is to stop bc from boasting when it runs.

First, it will ask you for an option. The algorithm runs in iterations, each iteration requiring the given number (called p) to be tested against another number from a set (called s). If p is composite against s, then p is composite else p is probably prime. In order to increase this probability, this implementation tests against 30 given numbers. If option is entered as ‘0’, the program will read the numbers in set from the input and you can enter the numbers suitably. If its entered as ‘1’, the program will automatically select the set. If you are able to enter random numbers then select option ‘0’ else select ‘1’. I may talk about generating arbitrary long random numbers in a future blogpost.

Second, it will ask you for the number to test. Enter any large odd number (even numbers are composite). Sample:

900900900900990990990991 (prime)
900900900900990990990993 (composite)
359334085968622831041960188598043661065388726959079839 (prime)

Third, if you selected option ‘0’, it will prompt you for the 30 random numbers.

Read the code to understand further – its not very difficult to understand. Have questions, post comments.

This can be further extended to search for primes: start at any big odd number, test it – it its prime report and stop, if not add 2 to the number and test again. I used this code to search for very large primes. In fact, I used it to prove 2^600-95 is a 181 digit prime.

Share

Licensing and information about the blog available here.