As usual there is a console application ExchangeKey.java that shows how it works. The main() method provides a unit test an prompts the user to enter it's data.
There is also a GUI application ExhangeKeyGui.java which permit to see dynamicaly how changing values updates the calculations.
The Prime.java class first introduced in Secret Code VII is used to validate/generate random numbers.
ExchangeKey.java
import java.math.BigInteger;
import java.util.*;
/*
* Ok if you have followed the Tutorial: Secret Code VIII = TowXor
* you will know that the biggest problem is to exchange keys (an encrypted way) between two
* persons that might be thousands of miles/kilometers away in the world.
*
* Thanks to two folks:
* - Whitfield Diffie, who works most of his life as a free lance specialist in encodeinf/decoding
* but was also during years engineer at Sun
* - Martin Hellman teacher at Stanford University in Callifornia
*
* These 2 guys are the father of cryptology as we know it today and they are both younger then me so I
* guess I missed my turn :-(
*
* They mostly worked on non-reversible functions that are required for encoding.
* Non-reversible function ????
* Most mathematic functions are reversible. Not good for encoding, we do not want the same receipe
* to be reversed to come back to the original message.
*
* Lets take a standard mathematic funtion f(x) = 3^x so
* x = 1 2 3 4 5 6
* f(x) = 3^1 3^2 3^3 3^4 3^5 3^6
* == 3 9 27 81 243 729
*
* This type of function can be easily reversed from 243 is is easy to find out that is coming from 3^5
* Most mathematic functions of that type just produce a result number that grows and grows
* 3 9 81 243 729...
*
* from each produced value we can go back and figure out its origin... if we encode we can decode
* Now, with the modulo operator we can change the growing behaviour of the function
* Let us apply a % 7 to the function
*
* x = 1 2 3 4 5 6
* f(x)= 3^1 3^2 3^3 3^4 3^5 3^6
* == 3 9 27 81 243 729
* f(x) % 7 = 3 2 6 4 5 1
*
* So now we have a function that you can't reverse. OK you can argue that cou can make a table of the %
* value and reverse it back according to that value. This is true for this example where you would store
* in the table 3, 2, 6, 4, 5 and 1 but what happen if I use a 200 digits
* long value for the % operator ? Your table will have 1,000,000,000,... 2 hundred times entries
* Not really easy to manage :-)
* That is why cryptologist uses the largest prime number they can find (we will see why prime later)
* and everytime a new largest prime number is found, the cryptology world makes a step ahead.
*
* Now back to our original problem where Alice and Bernard want to echange a key and they are
* in two opposite locations in the world, so they have to use the internet to exchange their keys.
*
* I won't good in details on how Diffie found that one (you can always Google Diffie for more details)
* but here is how it works.
*
* For the ones who didn't look at the previous tutorials: Alice, Bernard and Eve were introduced
* in Code Secret VIII - Quadruple XOR. Look at it to be formely introduced.
*
* OK, has I said the the whole principle is based on the modulo operator which generates
* irreversible functions and the use of prime number
* The magic formula is: Y**x mod(P) (** being exposant)
* where P is a prime number
* where Y < P
*
* The numbers P and Y are not secret at all. Assume we select Y as 7 and P as 11 which is a prime.
* Alice and Bernard can communicate together on a non secured line and agree on this values 7 and 11.
* We do not care if Eve traps this message.
*
* So let assume Alice (personal preference) selected 3 as her secret number
* Bernard selects 6 as his secret number
*
* OK here how it goes:
* ALICE BERNARD
* ----- -------
* applies 3 to the function and obtains applies 6 to the function and obtains
* 7 ** 3 = 343 7 ** 6 = 117649
* 343 % 11 = 2 117649 % 11 = 4
*
* Now this where the magic occurs... Alice and Bernard can now exchange these numbers
* They are not a key, they are not part of the key, Eve can still watch the wire and grab
* these numbers she cannot do anything with it
*
* So Alice receives 4 from Bernard and Bernard receives 2 from Alice
* Now they apply these numbers to their own formula and secret number
* using the number received from the other one, raising to the exponent their own number
* and applying the modulo P to it
* ALICE BERNARD
* ----- -------
* 4 ** 3 == 64 2 ** 6 = 64
* 64 % 11 = 9 64 % 11 = 9
*
* Hey !!! 9 == 9 !!!
* Now Alice and Bernard has a common key 9 that can be applied using whatever formula
* 9 may means use "Mobby Dick" book and use the each number in the message as the Nth number in the book
* If the number is large enough, and this where large prime numbers are handy, the reulting number
* may be hugue and can be used as a key for the Xor encryption seen in Secret Code Tutorial 6
*
* The console application that follow will just prove the concept
* It uses the Prime class described in Tutorial: Secret Code VII - Prime Numbers
*/
/*
* the class that generates randomly P and Y for the previous described formula
*/
public class ExchangeKey {
private int y; // the agreed number for equation Y ** x mod(P)
private int secret; // the secret number used
// p as BigInteger
private BigInteger bigP;
// just to keep the BigInteger to display how big the number can be
// protected for the GUI to access them (too lazy to write getters() :-) )
protected BigInteger yPowerSecret;
protected BigInteger valuePowerSecret;
/*
* Constructor used by both Alice and Bernard
*/
public ExchangeKey(int y, int p, int secret) {
this.y = y;
setP(p);
this.secret = secret;
}
/*
* Empty constructor that will use 0
*/
public ExchangeKey() {
this(0, 0, 0);
}
/*
* To set P and create its' BigNumber
*/
public void setP(int p) {
bigP = new BigInteger("" + p);
}
/*
* Other setters
*/
public void setY(int y) {
this.y = y;
}
public void setSecret(int secret) {
this.secret = secret;
}
/*
* To generate the number that will be sent to the other
*/
int generateCodeToSend() {
// we have to calculate Y ** secret that can yield a very big number so use a BigInteger object
BigInteger bigY = new BigInteger("" + y);
yPowerSecret = bigY.pow(secret);
// makes the modulo of it
BigInteger result = yPowerSecret.mod(bigP);
// module P which is an int the result wild be in integer range
return result.intValue();
}
/*
* To generate common Key from the number received from the other
*/
int generateCommonKey(int valueReceived) {
// we have to calculate first valueReceived ** secret
BigInteger bVal = new BigInteger("" + valueReceived);
valuePowerSecret = bVal.pow(secret);
// make the modulo out of it
BigInteger result = valuePowerSecret.mod(bigP);
return result.intValue();
}
/*
* to test the whole thing
*/
private static Scanner scan = new Scanner(System.in);
public static void main(String[] args) {
// the Y and P numbers
int y, p;
// create our Prime number generator/validator
Prime prime = new Prime();
// the secret number of Alice and Bernard
int aliceSecret, bernardSecret;
// the ExchangeKey objects of Bernard and Alice
ExchangeKey exAlice, exBernard;
// message sent to Bernard and Alice
int toBernard, toAlice;
// Alice and Bernard keys
int aKey, bKey;
//------------------------ unit test can be removed ----------------------------------
// to randomly generate our numbers
Random ran = new Random();
// create y shared by both Alice and Bernard, y randomly from 10 to 1000
y = ran.nextInt(991) + 10;
System.out.println(" shared value for Y by both Alice and Bernard is: " + y);
// now create P that must be Prime and > y
p = prime.getPrimeGreaterOrEqual(y + 100);
System.out.println(" shared value for P by both Alice and Bernard is: " + p);
// the secret number of Alice and Bernard
// generate Alice and Benard secret
aliceSecret = prime.getPrimeGreaterOrEqual(ran.nextInt(990) + 10);
bernardSecret = prime.getPrimeGreaterOrEqual(ran.nextInt(990) + 10);
System.out.println("Alice secret is: " + aliceSecret + ". Bernard secret is " + bernardSecret + ".");
// create both ExchangeKey object
exAlice = new ExchangeKey(y, p, aliceSecret);
exBernard = new ExchangeKey(y, p, bernardSecret);
// Value Alice will send to Bernard
toBernard = exAlice.generateCodeToSend();
System.out.println(" Value to send to Bernard: " + toBernard + " from: " + exAlice.yPowerSecret);
// Value Bernard will send to Alice
toAlice = exBernard.generateCodeToSend();
System.out.println(" Value to send to Alice: " + toAlice + " from: " + exBernard.yPowerSecret);
// the key
bKey = exBernard.generateCommonKey(toBernard);
aKey = exAlice.generateCommonKey(toAlice);
System.out.println("Key calculated by Bernard: " + bKey + " from: " + exBernard.valuePowerSecret);
System.out.println("Key calculated by Alice: " + aKey + " from: " + exAlice.valuePowerSecret);
if(aKey == bKey)
System.out.println("Yes it works !!!");
else
System.out.println("Oups... something wrong");
//-------------------------------- end unit test ------------------------------------
// entering value for Y the getIntInput() method validates that it is an int > 0
y = getIntInput("Enter value for Y: ");
// getting the prime number
p = 0;
while(true) {
p = getIntInput("Enter a value for prime number p: ");
// validate that P is > Y
if(p <= y) {
System.out.println("The prime number P must be > Y: " + y);
continue;
}
// validate that it is a prime
if(prime.isPrime(p))
break; // OK we are done
// print a message that the input number is not a prime
System.out.println(p + " is NOT a prime number");
// suggest the one just after it
System.out.println("May I suggest: " + prime.getPrimeGreaterOrEqual(p) + " ?");
}
// prompt for Alice secret
aliceSecret = getIntInput("Enter Alice's secret number: ");
bernardSecret = getIntInput("Enter Bernard's secret number: ");
// create both Exchange objects and get the value to send
exAlice = new ExchangeKey(y, p, aliceSecret);
exBernard = new ExchangeKey(y, p, bernardSecret);
toBernard = exAlice.generateCodeToSend();
toAlice = exBernard.generateCodeToSend();
System.out.println("Message that Bernard sends to Alice: " + toAlice);
System.out.println("Message that Alice sends to Bernard: " + toBernard);
// test if the generated key is the same
aKey = exAlice.generateCommonKey(toAlice);
bKey = exBernard.generateCommonKey(toBernard);
System.out.println("Key calculated by Bernard: " + bKey);
System.out.println("Key calculated by Alice: " + aKey);
if(aKey == bKey)
System.out.println("Yes it works !!!");
else
System.out.println("Oups... something wrong");
}
/*
* To input a valid Integer from user
*/
private static int getIntInput(String prompt) {
// loop until valid Input
while(true) {
// prompt user with the prompt received as parameter
System.out.print(prompt);
// read from user as string
String str = scan.nextLine();
// try to convert to int
try {
int n = Integer.parseInt(str);
// if an int > 0 return it
if(n > 0)
return n;
System.out.println("the number should be > 0");
}
catch(Exception e) {
System.out.println("Please enter an integer");
}
}
}
}
ExchangeKeyGui.java
import java.awt.*;
import javax.swing.*;
import javax.swing.event.*;
/**
* A GUI that use the ExchangeKey class to exchange keys between two users
* The GUI will display the different steps in generating the keys
*/
public class ExchangeKeyGui extends JFrame {
private static final long serialVersionUID = 1L;
// the ExchangeKey of Alice and Bernard
private ExchangeKey exBernard, exAlice;
// to validate if the number is prime
private Prime prime = new Prime();
// the Y and P fields
private JTextField yText, pText;
// The secret number of Alice and Bernard
private JTextField aliceSecretText, bernardSecretText;
// The message for Y valid, P valid, secretAliceValid, secretBernardValid
private JLabel yValidLabel, pValidLabel, aliceValidLabel, bernardValidLabel;
// The first and second operation performed
private JLabel aliceFirstOperation, aliceSecondOperation, bernardFirstOperation, bernardSecondOperation;
// the BigNumber generated by the operations
private JLabel aliceYPowerSecret, bernardYPowerSecret;
private JLabel alicePowerBernard, bernardPowerAlice;
// the number sent by Alice to Bernard and Benard to Alice
private JLabel aliceToBernard, bernardToAlice;
// the key they generate
private JLabel aliceKey, bernardKey;
// valid label color
private Color darkGreen = new Color(0, 125, 0);
/**
* Constructor
*/
ExchangeKeyGui() {
super("Exchanging keys");
setLayout(new BorderLayout());
// we will use a GridLayout to store all our GUI components
JPanel centerPanel = new JPanel(new GridLayout(20,1, 2, 2));
// the listener for all TextFields
DocumentListener dl = new KeyListener();
// the Y to input
centerPanel.add(createCenteredLabel("Y shared by Alice and Bernard"));
yText = new JTextField(50);
yText.getDocument().addDocumentListener(dl);
// the label saying if it is valid
yValidLabel = new JLabel("Must be a number");
setLabelCharac(yValidLabel);
// put them on a row
centerPanel.add(twoColumnPanel(yText, yValidLabel));
// the P to input
centerPanel.add(createCenteredLabel("P shared by Alice and Bernard. Should be a prime > then Y"));
pText = new JTextField(50);
pText.getDocument().addDocumentListener(dl);
// the label saying if it is valid
pValidLabel = new JLabel("Should be a prime > Y");
setLabelCharac(pValidLabel);
// put them on a row
centerPanel.add(twoColumnPanel(pText, pValidLabel));
// Alice's secret number
centerPanel.add(createCenteredLabel("Alice's secret number"));
aliceSecretText = new JTextField(50);
aliceSecretText.getDocument().addDocumentListener(dl);
// the label if valid
aliceValidLabel = new JLabel(" Must be a number");
// put them in a row
setLabelCharac(aliceValidLabel);
centerPanel.add(twoColumnPanel(aliceSecretText, aliceValidLabel));
// Bernard's secret number
centerPanel.add(createCenteredLabel("Bernard's secret number"));
bernardSecretText = new JTextField(50);
bernardSecretText.getDocument().addDocumentListener(dl);
// the label if valid
bernardValidLabel = new JLabel(" Must be a number");
// put them in a row
setLabelCharac(bernardValidLabel);
centerPanel.add(twoColumnPanel(bernardSecretText, bernardValidLabel));
// firstOperation by Alice
aliceFirstOperation = createCenteredLabel("Alice Y ** her Secret Number");
centerPanel.add(aliceFirstOperation);
aliceYPowerSecret = new JLabel("");
centerPanel.add(aliceYPowerSecret);
// the message that Alice will send to Bernard
aliceToBernard = createCenteredLabel("");
centerPanel.add(twoColumnPanel(createCenteredLabel("Alice % P that will be send to Bernard:"), aliceToBernard));
// firstOperation by Bernard
bernardFirstOperation = createCenteredLabel("Bernard Y ** his Secret Number");
centerPanel.add(bernardFirstOperation);
bernardYPowerSecret = new JLabel("");
centerPanel.add(bernardYPowerSecret);
// the message that Alice will send to Bernard
bernardToAlice = createCenteredLabel("");
centerPanel.add(twoColumnPanel(createCenteredLabel("Bernard % P that will be send to Alice:"), bernardToAlice));
// applying the second operation for Alice
aliceSecondOperation = createCenteredLabel("Alice: from Bernard value ** her Secret Number");
centerPanel.add(aliceSecondOperation);
alicePowerBernard = new JLabel();
centerPanel.add(alicePowerBernard);
// applying the second operation for Bernard
bernardSecondOperation = createCenteredLabel("Bernard: from Alice value ** his Secret Number");
centerPanel.add(bernardSecondOperation);
bernardPowerAlice = new JLabel();
centerPanel.add(bernardPowerAlice);
// the results displayed on 4 columns
centerPanel.add(createCenteredLabel("Alice and Bernard applying % P to second operation"));
// a Panel with 4 columns to display he key that Bernard and Alice will generate
// applying the second operation
JPanel fourColumn = new JPanel(new GridLayout(1, 4));
fourColumn.add(createCenteredLabel("Alice's key:"));
// the label to display Alice's key in RED
aliceKey = new JLabel();
setLabelCharac(aliceKey);
fourColumn.add(aliceKey);
fourColumn.add(createCenteredLabel("Bernard's key:"));
// the label to display Bernard's key in RED
bernardKey = new JLabel();
setLabelCharac(bernardKey);
fourColumn.add(bernardKey);
centerPanel.add(fourColumn);
// creating both ExchangeObject with 0,0,0 values we will set the Y, P and secret values later
exBernard = new ExchangeKey();
exAlice = new ExchangeKey();
// finishing up
add(centerPanel, BorderLayout.CENTER);
// to display a gap
JLabel header = createCenteredLabel("Enter the 4 values and see how other values changed when you changed them");
header.setForeground(darkGreen);
add(header, BorderLayout.NORTH);
add(new JLabel(" "), BorderLayout.EAST);
add(new JLabel(" "), BorderLayout.WEST);
JLabel bottom = createCenteredLabel("Check the 2 key values in red they should be equal");
bottom.setForeground(darkGreen);
add(bottom, BorderLayout.SOUTH);
// standard operation to show the JFrame
this.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
setBounds(30, 30, 500, 500);
setVisible(true);
}
/**
* A method to create a JLabel with foreground color Blue and with text centered
*/
private JLabel createCenteredLabel(String text) {
JLabel label = new JLabel(text);
label.setHorizontalAlignment(SwingConstants.CENTER);
label.setForeground(Color.BLUE);
return label;
}
/**
* One of the JTextField has changed validate the whole thing
*/
private void updateKeyString() {
// assume success
boolean allInputValid = true;
// check the Y value
int y = checkInput(yText, yValidLabel);
if(y == -1) {
allInputValid = false;
// set Y to 3 to test P
y = 3;
}
else {
exAlice.setY(y);
exBernard.setY(y);
yValidLabel.setText(y + " is valid.");
yValidLabel.setForeground(darkGreen);
}
// check the Prime number value
int p = checkInput(pText, pValidLabel);
if(p == -1) {
allInputValid = false;
}
else {
// check that is prime
if(!prime.isPrime(p)) {
pValidLabel.setText("Should be a prime number");
pValidLabel.setForeground(Color.RED);
allInputValid = false;
}
// check that it is > Y
if(allInputValid) {
if(p > y) {
// update both Alice and Bernard ExchangeKey object with the valid value
exAlice.setP(p);
exBernard.setP(p);
pValidLabel.setText(p + " is valid.");
pValidLabel.setForeground(darkGreen);
}
else {
pValidLabel.setText("P must be > Y");
pValidLabel.setForeground(Color.RED);
allInputValid = false;
}
}
}
// check Alice secret number
int aliceSecret = checkInput(aliceSecretText, aliceValidLabel);
if(aliceSecret >= 3) {
exAlice.setSecret(aliceSecret);
aliceValidLabel.setText(aliceSecret + " is valid.");
aliceValidLabel.setForeground(darkGreen);
}
else {
allInputValid = false;
}
// check Bernard secret number
int bernardSecret = checkInput(bernardSecretText, bernardValidLabel);
if(bernardSecret >= 3) {
exBernard.setSecret(bernardSecret);
bernardValidLabel.setText(bernardSecret + " is valid.");
bernardValidLabel.setForeground(darkGreen);
}
else {
allInputValid = false;
}
// if all the inputs are valid perform the calculations
if(allInputValid) {
// perform the first "encoding" operations
int toBernard = exAlice.generateCodeToSend();
int toAlice = exBernard.generateCodeToSend();
aliceToBernard.setText("" + toBernard);
bernardToAlice.setText("" + toAlice);
bernardYPowerSecret.setText(exBernard.yPowerSecret.toString());
aliceYPowerSecret.setText(exAlice.yPowerSecret.toString());
// perform the second operations with the value received from the other one
int keyB = exBernard.generateCommonKey(toBernard);
int keyA = exAlice.generateCommonKey(toAlice);
bernardKey.setText("" + keyB);
aliceKey.setText("" + keyA);
bernardPowerAlice.setText(exBernard.valuePowerSecret.toString());
alicePowerBernard.setText(exAlice.valuePowerSecret.toString());
}
else { // so clear the fields
// Bernard's
bernardPowerAlice.setText("");
bernardYPowerSecret.setText("");
bernardKey.setText("");
// Alice's
alicePowerBernard.setText("");
aliceYPowerSecret.setText("");
aliceKey.setText("");
}
}
/*
* Check that a JTextField contains a numeric value and returns it
* and set its corresponding JLabel to must be a number and set it in RED
*/
private int checkInput(JTextField tf, JLabel label) {
// test that the textfiled is not empty
String text = tf.getText().trim();
if(text.length() == 0) {
label.setText("Must be a number");
label.setForeground(Color.RED);
return -1;
}
// try to convert it to an int
try {
int n = Integer.parseInt(text);
if(n < 3) {
label.setText("Must be >= 3");
label.setForeground(Color.RED);
return -1;
}
// ok valid value (numeric and >=3) return it
return n;
}
catch(Exception e) { // invalid number
label.setText("Must be a number");
label.setForeground(Color.RED);
return -1;
}
}
/*
* To set a JLabel as opaque, white/red, centered
*/
private void setLabelCharac(JLabel label) {
label.setOpaque(true);
label.setBackground(Color.WHITE);
// initial foreground color (not valid)
label.setForeground(Color.RED);
label.setHorizontalAlignment(SwingConstants.CENTER);
}
/*
* To create a JPanel with a GridLayout(1,2) from 2 JComponent
*/
private JPanel twoColumnPanel(JComponent a, JComponent B)/> {
// a GridLayout on 2 column
JPanel p = new JPanel(new GridLayout(1,2, 2, 2));
// add them to the GridLayout 2 columns
p.add(a);
p.add(B)/>;
// and return that panel
return p;
}
/**
* To start the GUI
*/
public static void main(String[] args) {
new ExchangeKeyGui();
}
/**
* A listener to be informed whenever the any JTextField is changed
*/
private class KeyListener implements DocumentListener {
@Override
public void changedUpdate(DocumentEvent arg0) {
updateKeyString();
}
@Override
public void insertUpdate(DocumentEvent arg0) {
updateKeyString();
}
@Override
public void removeUpdate(DocumentEvent arg0) {
updateKeyString();
}
}
}
Now if you haven't pick the Prime class from the Tutorial VII here it is again
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));
}
}
MultiQuote
| 