有限域上的椭圆曲线群的点乘运算实现

以y²=x³+x+7 p=17 Q(1,3)为例：

public class test {

	private int X, Y;

	private int p = 17, k, a = 1, b = 7, x1 = 1, y1 = 3, modV;

	public int mod(int f) {
		int z = f / 17;
		int mo = f - (z * 17);
		if (mo >= 0)
			return mo;
		else
			return mo + p;
	}

	public int extendedEuclid(int e, int modValue) {
		int i;
		int over = e;
		for (i = 1; i < modValue;) {
			over = over % modValue;
			if (over == 1) {
				return i;
			} else {
				if (over + e <= modValue) {
					do {
						i++;
						over += e;
					} while (over + e <= modValue);
				} else {
					i++;
					over += e;
				}
			}
		}
		return 0;
	}

	public void dp(int x, int y, int times) {
		if (times >= 2) {
			//System.out.println("111");
			modV = extendedEuclid(2 * y, p);
			//System.out.println(modV);
			k = mod(((3 * x * x + a) * modV));
			X = mod(((k * k) - 2 * x));
			Y = mod((-y + k * (x - X)));
			x = X;
			y = Y;
		}
		for (int d = times - 2; d != 0; d--) {
			int m, n;
			modV = extendedEuclid(X - x1, p);
			//System.out.println(modV);
			k = mod((Y - y1) * modV);
			m = mod((k * k) - x1 - X);
			n = mod(((-y1) + (k * (x1 - m))));
			X = m;
			Y = n;
		}
		System.out.println(X + "," + Y);
		//System.out.println(k);

	}

	public static void main(String args[]) {
		test e1 = new test();
		e1.dp(1, 3, 2);
	}
}

——END——