Everybody knows (or almost everybody knows) that Prime numbers are very important in crypting/decrypting algorithms. We will see why in the next tutorial when we will talk about transmitting, the secure way, a Key over the net.

Before doing that, we need a way to generate Prime numbers and more precisely to get a prime number > a certain number.

I apologize to DIC who already wrote a tutorial about the subject. Here is my version of it, very efficient. It uses the sieve of Eratosthene algorithm which use a BitField. Calculations of Prime is done on demand an only when required.

It has 2 methods:

- isPrime(n) which returns TRUE is the number passed as parameter is a Prime number

- getPrimeGreaterOrEqual(n) which returns the first prime number >= n

The class does not pre-calculate prime numbers, it just register in a BitSet is a number is a Prime or not (starting with 3) and expands this BitSet on demand if the calls to isPrime() or getPrimeGreatedOrEqual(n) request a bigger number

Here is Prime.java... it will be required by the followin tutorials on Secret Code

import java.util.BitSet; /* * Encryption/Decrytion requires prime numbers * This class facilates the use of them using the sieve of Eratosthene */ public class Prime { // A BitSet to hold the primes usually when a BitSet is used to generate // Prime numbers using the Sieve of Eratosthene // 1) the BitSet is initialize to TRUE (true meaning that the number IS Prime) // 2) then non Prime numbers are set to FALSE // 3) in the BitSet bit 0 says if 0 is prime or not, bit 1 says if 1 is prime or not, // bit 2 says if 2 is prime or not, ...bit N syas if N is prime or not // This way of working have multiple disavantages // 1) when the BitSet is created and later expanded we have to set to TRUE the bits // in the extension as possible Prime. This is a waste of time. // 2) So here we will inversed the standard way of working // bit set to FALSE means that the corresponding number is Prime // bit set to TRUE means that the corresponding number is NOT Prime // so extending the BitSet will autmatically assumed that the numbers in the extension are Prime // 3) no need to waste memory for even number so // bit 0 is for 1 bit 1 for 3 bit 2 for 5 ... bit N/2 for N // make it static all instances of this class will share the same BitSet and max private static BitSet bitSet = new BitSet(1000); // int to a reasonable size // the largest number stored up to which Primes are identified private static int max = 3; /* * return if a number is prime */ public boolean isPrime(int n) { // if even or 1 surely not a prime if(n == 2) return true; if(n < 3 || n % 2 == 0) return false; // if we have already determine up to that prime if(n <= max) return !bitSet.get(n / 2); // ok we have to extend our bitSet up to that Prime for(int i = 3; i <= n; i += 2) { // if the first multiple of that number is > n we are done if(i * 2 > n) break; // if the already stored number is prime we will have to set all its // multiples to non prime if(!bitSet.get(i / 2)) { // found the last multiple set (recorded in our BitSet) for that prime // so we won't reset them twice for nothing int multiple = max / i; multiple *= i; // at the beginning this will be true if(multiple <= i) multiple = i * 2; // so fetch the first multiple of the prime // set as non prime all the multiples of that prime clearMultiple(i, multiple, n); } } // reset new max (the largest number tested) max = n; // ok return if rime or not depending if the bit is set return !bitSet.get(n / 2); } /* * Returns the first prime greater than the number pass as parameter */ int getPrimeGreaterOrEqual(int n) { // make sure we start with an odd number if(n % 2 == 0) ++n; // loop until we found one while(true) { // if the number is registered as prime return it if(isPrime(n)) return n; // else check next one n += 2; } } /* * Method to set a number not prime */ private void setNotPrime(int n) { // ignore the set for even numbers if it was not the case 6 (multiple of 3) // would set bit 6 / 2 = 3 in the BitSet to non prime and 3 is actually the bit for the number 7 if(n % 2 == 0) return; bitSet.set(n / 2, true); } /* * Will set as non prime all the multiple of this prime up to max * we specify as parameter the multiple to start with so when the BitSet is * expanded we are not redoing the job already done */ private void clearMultiple(int prime, int multiple, int max) { // set as non prime all the multiples of the number until we exceed the max while(multiple <= max) { setNotPrime(multiple); multiple += prime; } } /* * to test the class */ public static void main(String[] args) { // build a Prime object Prime prime = new Prime(); // test if the class returns the good first prime numbers from 3 to 101 // in reverse order to avoid multiple BitSet resizing for(int i = 101; i >= 3; i -= 2) { if(prime.isPrime(i)) System.out.println("Is " + i + " is prime: "); } // do some test with larger ones for(int i = 500; i < 2000; i += 50) System.out.println("The first prime number >= " + i + " is " + prime.getPrimeGreaterOrEqual(i)); } }

This code can be showed as example for any thread talking about Prime number

Stay tune the next tutorial about key transmission using Prime numbers is coming

Happy coding

EDITED: use a staic max and BitSet so all instances will share them

This post has been edited by **pbl**: 03 October 2010 - 04:30 PM