ミラーアルゴリズム

package x3_1;

//miller's algorithm for pairing
//using simplified miller's algorithm
//2007.8.24 tyouiifan

import java.math.BigInteger;
import java.security.spec.ECPoint;

public class Miller_Algorithm {
	static BigInteger A, B, p;

	// the value to set an elictip curve y^3=x^2+Ax+B
	static ECPoint P, Q;

	// the input point on the elictip curve
	// ECPoint Q = Elictip_Adder.ECpointAdder(A, B, P1, P2); //help of
	// PointAdder
	static BigInteger f = new BigInteger("1");

	// answer for pairing

	public static BigInteger Miller(ECPoint P, ECPoint Q, BigInteger r,
			int k, BigInteger A, BigInteger B, BigInteger p) {
		setA(A);
		setB(B);
		setP(p);
		// P is from E(Fq)[r], Q is from E(Fqk)
		// f=1
		// V=P
		ECPoint V = P;
		int t = r.bitLength();
		// r is shwon (10010101...1)2=(t-1 to 0) in binnary. t-1 bit Integer.
		// for (t-1 down to 0)
		for (int i = t - 1; i >= 0; i--) {
			// f = (f^2)*l(V,V)(Q) //l(P,Q) is a line cross to P and Q
			// l(v,v) is the tangent line to Eliptic curve y^2=x^3+Ax+B
			// l(v,v)(Q) mean input the point Q (X,Y) to the tangent line y=ax+b
			f = f.multiply(f).multiply(tangentLine(V, Q));
			// V = 2V
			V = Elictip_Adder.ECpointAdder(A, B, p, V, V);
			// if (ri==1){
			if (r.testBit(i)) {
				// f = f*l(V,P)(Q)
				f = f.multiply(PointLine(V, P, Q));
				// V = V + P
				V = Elictip_Adder.ECpointAdder(A, B, p, V, P);
				// }
			}
			// }
		}
		// f = f^(((q^k)-1)/r)
		int pow = (int) Math.pow(Double.valueOf(2), k);
		int finalPower = (pow -1)/Integer.valueOf(r.toString());
		f = f.pow(finalPower);
		return f;
		// return f is from Fqk
	}

	public static BigInteger PointLine(ECPoint V, ECPoint P, ECPoint Q) {
		// ax+by+c=0 for V,P.
		// input Q(xq,yq) for above polynomial.
		BigInteger a, b, c;
		BigInteger vx = V.getAffineX();
		BigInteger vy = V.getAffineY();
		BigInteger px = P.getAffineX();
		BigInteger py = P.getAffineY();
		BigInteger qx = Q.getAffineX();
		BigInteger qy = Q.getAffineY();

		// (vx-px)y=-(vy-py)x-c is the same polynomial to above.
		// (vx-px)y+(py-vy)x=-c
		// a = py-vy
		a = py.subtract(vy);
		// b = vx-px
		b = vx.subtract(px);
		// c = -((vx-px)y+(py-vy)x) = -(ax+by)
		c = a.multiply(vx).add(b.multiply(vy)).negate();

		// (vx-px)y+(py-vy)x+c=0 is same to ax+by+c=0

		// to culculate answer of Q for above polynomial.
		BigInteger output;
		output = a.multiply(qx).add(b.multiply(qy)).add(c);

		return output;
	}

	public static BigInteger tangentLine(ECPoint V, ECPoint Q) {
		// ax+by+c=0 for V,P.
		// input Q(xq,yq) for above polynomial.

		BigInteger a, b, c;
		BigInteger vx = V.getAffineX();
		BigInteger vy = V.getAffineY();
		BigInteger qx = Q.getAffineX();
		BigInteger qy = Q.getAffineY();

		// slope:y'=(3*vx^2+A)/vy
		// (3*vx^2+A)x+(-vy)*y+c=0
		// a = (3*vx^2+A)
		a = vx.multiply(vx).multiply(new BigInteger("3")).add(A);
		// b = -vy
		b = vy.negate();
		// c = -(ax+by)
		c = a.multiply(vx).add(b.multiply(vy)).negate();

		BigInteger output;
		output = a.multiply(qx).add(b.multiply(qy)).add(c);

		return output.mod(p);
	}

	public static BigInteger getA() {
		return A;
	}

	public static void setA(BigInteger a) {
		A = a;
	}

	public static BigInteger getB() {
		return B;
	}

	public static void setB(BigInteger b) {
		B = b;
	}

	public static ECPoint getP() {
		return P;
	}

	public static void setP(ECPoint p) {
		P = p;
	}

	public static ECPoint getQ() {
		return Q;
	}

	public static void setQ(ECPoint q) {
		Q = q;
	}

	public static void setP(BigInteger p) {
		Miller_Algorithm.p = p;
	}
}