// OK

package kryptoScript;

//
// java/EllipticCurves_d.java // 
// Copyright (c) 2002 Silke Thomas
//
// last change: 24.3.2002
// last change: 11.12.2007 KR
//

// uses "mod" (multiply a and b modulo c) from Helpers.class

import java.awt.*;
import java.applet.*;
import java.lang.*;
import java.awt.event.*;
import java.util.*;

public class EllipticCurves_e extends Applet
implements ActionListener{
	
	long a, b, test, x, y, z, p;
	KeyField aField, bField, pField, xField, yField;
	TextField abTestField, pTestField, xyTestField;
	TextArea pointArea, resPointArea, addPointArea, multPointArea;
	Label nLabel, lLabel;
	Button abTestButton, pTestButton, lsgButton,
		pointButton, xyTestButton, multButton;
	Panel panel = new Panel();
	boolean longToBitDone = true, abTestDone = false,
		pTestDone = false, xyTestDone = false;
	String newline = System.getProperty("line.separator");
	EllPoint alpha = new EllPoint();
	Vector points = new Vector();
	Vector multVector = new Vector();
	
	
// layout   
	public void init() {
		setLayout(new GridBagLayout()); GridBagConstraints c, grid;

	    
		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 0;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST; 
		Panel p0 = new Panel();
		p0.add(new Label("Choose p:"));
		p0.add(pField = new KeyField("11", 4));
		p0.add(pTestButton = new Button("Test of p"));
		p0.add(pTestField = new TextField("",44));
		pTestField.setEditable(false);
		add(p0, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 1;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p2 = new Panel();
		p2.add(new Label("Choose A:"));
		p2.add(aField = new KeyField("1", 4));
		p2.add(new Label("and  B:"));
		p2.add(bField = new KeyField("6", 4));
		p2.add(new Label(" such that (4 * A^3 + 27 * B^2) is not a multiple of p."));
		add(p2, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 2;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p4 = new Panel();
		p4.add(abTestButton = new Button("Test of A and B"));
		p4.add(abTestField = new TextField("",55));
		abTestField.setEditable(false);
		add(p4, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 3;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p6 = new Panel();
		p6.add(new Label("Solving of the defining equality"));
		p6.add(lsgButton = new Button("Solve"));
		add(p6, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 4;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p8 = new Panel();
		p8.add(pointArea = new TextArea("",13,80));
		pointArea.setEditable(false);
		add(p8, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 5;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p9 = new Panel();
		p9.add(new Label("Computing the points of E:"));
		p9.add(pointButton = new Button("Computing"));
		add(p9, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 6;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p11 = new Panel();
		p11.add(resPointArea = new TextArea("",6,80));
		resPointArea.setEditable(false);
		add(p11, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 7;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p12 = new Panel();
		p12.add(new Label("Computing the multiples of the point (x, y) of E"));
		add(p12, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 8;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p13 = new Panel();
		p13.add(new Label("Choose x:"));
		p13.add(xField = new KeyField("2", 4));
		p13.add(new Label("and  y:"));
		p13.add(yField = new KeyField("7", 4));
		p13.add(new Label(" such that alpha = (x, y) is in E"));
		add(p13, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 9;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p15 = new Panel();
		p15.add(xyTestButton = new Button("Test of alpha"));
		p15.add(xyTestField = new TextField("",55));
		xyTestField.setEditable(false);
		add(p15, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 10;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p17 = new Panel();
		p17.add(multButton = new Button("Start"));
		add(p17, c);

		c = new GridBagConstraints();
		c.gridx = 0; c.gridy = 11;
		c.gridwidth = 1; c.gridheight = 1;
		c.anchor = GridBagConstraints.WEST;
		Panel p18 = new Panel();
		p18.add(multPointArea = new TextArea("",5,80));
		multPointArea.setEditable(false);
		add(p18, c);
      
// register listeners
		aField.addActionListener(this);
		bField.addActionListener(this);
		pField.addActionListener(this);
		xField.addActionListener(this);
		yField.addActionListener(this);
		abTestField.addActionListener(this);
		abTestButton.addActionListener(this);
		pTestField.addActionListener(this);
		xyTestButton.addActionListener(this);
		xyTestField.addActionListener(this);
		pTestButton.addActionListener(this);
		lsgButton.addActionListener(this);
		pointButton.addActionListener(this);
		multButton.addActionListener(this);
	}

// listen, dispatch
	public void actionPerformed(ActionEvent e) {
		Object source = e.getSource();
		String command = e.getActionCommand();

		if (command.equals("Test of p")) {
			getp();
		}
		if (command.equals("Test of A and B")) {
			getab();
		}
		if ((command.equals("Solve")) &&
		    (pTestDone) && (abTestDone)) {
			computePoints();
		}   
		if ((command.equals("Computing")) &&
		    (pTestDone) && (abTestDone)) {
			showPoints();
		}   
		if ((command.equals("Test of alpha")) &&
		    (pTestDone) && (abTestDone)) {
			getxy();
		}
		if ((command.equals("Start")) &&
		    (pTestDone) && (abTestDone) && (xyTestDone)) {
			showMult();
		}

	}
   
   
	// greatest common divisor
	public long Gcd(long left, long right) {
		if (!( left > right)) {return -1;}
      
		long q = (int)Math.floor((double)(left/right)); //trunc?
		long rest = left - q * right;
		while (rest != 0) {
			left = right;
			right = rest;
			q = (int)Math.floor((double)(left/right)); //trunc?
			rest = left - q * right;
		}
		return right;
	}

// prime number test
	public boolean isPrime(long num) {
		boolean prime = true;
		if ((num < 2) | ((num % 2 ==0) && (num != 2))) { return false; }
		long root = (int)Math.sqrt((double)num);
		long i = 3;
		while (i <= root && prime) {
			if (num % i == 0) {
				prime = false;
			}
			i += 2;
		}
		return prime;
	}
   
// computes  b^(-1) (mod n)
	public long extEuclid(long b, long n) {
		if (b == 0) { return -1; }
		if ((b == -1) | (n == -1)) { return -1; }

		long n0 = n;
		long b0 = b;
		long t0 = 0;
		long t = 1;
		long q = (int)Math.floor((double)(n0/b0)); // trunc?
		long r = n0 - q * b0;
		while (r > 0) {
			long temp = t0 - q * t;
			if (temp >= 0) temp = temp % n;
			if (temp < 0) temp = n - ((-temp) % n);
			t0 = t;
			t = temp;
			n0 = b0;
			b0 = r;
			q = (long)Math.floor((double)(n0/b0));
			r = n0 - q * b0;
		}
		if (b0 != 1) {
			return -1;
		}
		else {
			return t;
		}
	}

// gets and tests p	
	public void getp() {
		p = pField.getLongKey();
		if (! isPrime(p)) {
			pTestField.setText(p + " is not prime.");
		} else {
			pTestField.setText("OK, " + p + " is prime.");
			pTestDone = true;
		}
	}
	
// gets and tests A and B
	public void getab() {
		a = aField.getLongKey();
		b = bField.getLongKey();
		test = ((4 * a * a * a) + (27 * b * b)) % p ; 
		
		if (test == 0) {
			abTestField.setText("(4 * A^3 + 27 * B^2) is a multiple of " + p);
		} else {
			abTestField.setText("OK, (4 * A^3 + 27 * B^2) is not a multiple of " + p + ".");
			abTestDone = true;
		}
	}

// computes the points on the elliptic curve E
	public void computePoints() {
		pointArea.setText("x \t  x^3 + " + a + " * x + "
				  + b + " mod (" + p
				  + ")\t in QR(" + p + ")? \t y\n");
		
		for (int i = 0; i < p; i++) {
			long z = ((long) Math.pow(i, 3) + (a * i) + b) % p;
			pointArea.append("\n" + i + "\t \t" + z + "\t\t");
			long eulerTest = ((long) Math.pow(z, ((p - 1)/ 2)))
				% p;
			if ((eulerTest == 1)||(z == 0)){
				pointArea.append("yes \t\t");
				for (int j = 0; j < p; j++) {
					long quad = (j * j) % p;
					if (quad == z) {
						pointArea.append(j + "  ");
						EllPoint ePoint =
							new EllPoint();
						ePoint.setCar(i);
						ePoint.setCdr(j);
						points.addElement(ePoint);
					}
				}
			} else {
				pointArea.append("no");
			}
		}
	}

// display the points
	public void showPoints() {
		resPointArea.setText("Damit ergeben sich the following points: \n");
		for (int k = 0; k < points.size(); k++) {
			if ((k % 3) == 0) resPointArea.append("\n");
			resPointArea.append("P" + k);
			if (k < 10) resPointArea.append("  ");
			resPointArea.append(" = " + points.elementAt(k));
			resPointArea.append("\t\t");
		}
	}

// addition of two points of the elliptic curve
	public EllPoint addPoints(EllPoint p1, EllPoint p2) {
		long x1 = p1.getCar();
		long y1 = p1.getCdr();
		long x2 = p2.getCar();
		long y2 = p2.getCdr();
		long zaehler, tmp, nenner, lambda, x3, y3;
		EllPoint resPoint = new EllPoint();
		
		if ((x1 == 666) && (y1 == 666)) {
			return p2;
		} else if ((x2 == 666) && (y2 == 666)) {
			return p1;
		} else if ((x1 == x2) && (y1 == p-y2)) {
			x3 = 666;
			y3 = 666;
		} else if ((x1 == x2) && (y1 == y2)) {
			zaehler = ((3 * x1 * x1) + a) % p;
			tmp = (2 * y1) % p;
			nenner = extEuclid(tmp, p);
			lambda = (zaehler * nenner) % p;
			x3 = (lambda * lambda - x1 - x2) % p;
 			if (x3 < 0) x3 += p;
			y3 = (lambda * (x1 - x3) - y1) % p;
 			if (y3 < 0) y3 += p;
		} else {
			zaehler = (y2 - y1) % p;
			if (zaehler < 0) zaehler += p;
			tmp = (x2 - x1) % p;
			if (tmp < 0) tmp += p;
			nenner = extEuclid(tmp, p);
			lambda = (zaehler * nenner) % p;
			x3 = (lambda * lambda - x1 - x2) % p;
 			if (x3 < 0) x3 += p;
			y3 = (lambda * (x1 - x3) - y1) % p;
 			if (y3 < 0) y3 += p;
		}
		resPoint.setCar(x3);
		resPoint.setCdr(y3);
		return resPoint;
	}

//gets and tests (x, y)
	public void getxy() {
		alpha.setCar(xField.getLongKey());
		alpha.setCdr(yField.getLongKey());

		EllPoint toTest = new EllPoint();
		
		for (int i = 0; i < points.size(); i++) {
			toTest = (EllPoint) points.elementAt(i);
			if (toTest.equals(alpha)) {
				xyTestField.setText("OK, alpha is in E");
				makeMultVector(alpha, points.size());
				xyTestDone = true; 
				return;
			}
		}
		xyTestField.setText("alpha is not in E");
	}

// computes the multiples of the point ep on the elliptic curve E 	
	public Vector makeMultVector(EllPoint ep, int howOften) {
		EllPoint nep = ep;
		Vector testVector = new Vector();

		multVector.removeAllElements();
		
		for (int k = 0; k < howOften; k++) {
			multVector.addElement(nep);
			testVector.addElement(nep);
			nep = addPoints(nep, ep);
		}
		return testVector;
	}

// displays the multiples	
	public void showMult() {
		for (int k = 0; k < multVector.size(); k++) {
			if ((k % 3) == 0) multPointArea.append("\n");
			if (k < 9) multPointArea.append("  ");
			multPointArea.append((k + 1) + " * P = " +
					     multVector.elementAt(k));
			multPointArea.append("\t");
		}
	}
}