Page 1 of 1

## Secret Code VII - Prime numbers Why are Prime numbers so important in encryption Rate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=192554&amp;s=540afc112493db019b0eb6bf4177ba5e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 pbl

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

Reputation: 8378
• Posts: 31,956
• 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) {
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

• D.I.C Lover

Reputation: 3778
• Posts: 13,688
• 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.

### #3 pbl

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

Reputation: 8378
• Posts: 31,956
• Joined: 06-March 08

Posted 30 September 2010 - 03:11 PM

CTphpnwb, 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;