Page 1 of 1

Secret Code VII - Prime numbers Why are Prime numbers so important in encryption Rate Topic: -----

#1 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Posted 28 September 2010 - 09:19 PM

In the next tutorial we will start to use Prime numbers for encryption.
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


Is This A Good Question/Topic? 2
  • +

Replies To: Secret Code VII - Prime numbers

#2 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3034
  • Posts: 10,597
  • Joined: 08-August 08

Posted 30 September 2010 - 06:39 AM

The number 2 is a prime number.
		// if even or 1 surely not a prime
		if(n < 3 || n % 2 == 0)
			return false;


Your code should return true for it.
Was This Post Helpful? 2
  • +
  • -

#3 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Posted 30 September 2010 - 03:11 PM

View PostCTphpnwb, on 30 September 2010 - 07:39 AM, said:

The number 2 is a prime number.
		// if even or 1 surely not a prime
		if(n < 3 || n % 2 == 0)
			return false;


Your code should return true for it.

you are right, I was distracted by the fact that this code will be used for large numbers but to be exact:

         // if even or 1 surely not a prime
         if(n == 2)
            return true;
         if(n < 3 || n % 2 == 0)
            return false;


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1