Page 1 of 1

Secret Code IX - Exchanging keys Rate Topic: -----

#1 pbl  Icon User is offline

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

Reputation: 8328
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Posted 03 October 2010 - 09:18 PM

In this tutorial we will see how two persons can exchange a key over the internet even if their communication/messages are monitored by a third party.

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));
	}
}



Is This A Good Question/Topic? 2
  • +

Page 1 of 1