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
MultiQuote
| 