雅可比坐标中的椭圆曲线加法

Question

我尝试在一个素域上的椭圆曲线上添加两个点，将这些点从仿射/到仿射坐标进行转换，但无法得到正确的结果（我正在测试的曲线具有a=0）。 有人能看出问题在哪里吗？

// From Affine
BigInteger X1=P.x;
BigInteger Y1=P.y;
BigInteger Z1=BigInteger.ONE;

BigInteger X2=Q.x;
BigInteger Y2=Q.y;
BigInteger Z2=BigInteger.ONE;

// Point addition in Jacobian coordinates for a=0
// see http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl
BigInteger Z1Z1 = Z1.multiply(Z1);
BigInteger Z2Z2 = Z2.multiply(Z2);
BigInteger U1   = X1.multiply(Z2Z2);
BigInteger U2   = X2.multiply(Z1Z1);
BigInteger S1   = Y1.multiply(Z2).multiply(Z2Z2);
BigInteger S2   = Y2.multiply(Z1).multiply(Z1Z1);
BigInteger H    = U2.subtract(U1);
BigInteger I    = H.add(H).multiply(H.add(H));
BigInteger J    = H.multiply(I);
BigInteger r    = S2.subtract(S1).add(S2.subtract(S1));
BigInteger V    = U1.multiply(I);
BigInteger X3   = r.multiply(r).subtract(J).subtract(V.add(V)).mod(FIELD);
BigInteger Y3   = r.multiply(V.subtract(X3)).subtract(S1.add(S1).multiply(J)).mod(FIELD);
BigInteger Z3   = Z1.add(Z2).multiply(Z1.add(Z2)).subtract(Z1Z1).subtract(Z2Z2).multiply(H).mod(FIELD);

//To affine
BigInteger Z3Z3 = Z3.multiply(Z3);
BigInteger Z3Z3Z3 = Z3Z3.multiply(Z3);

return new Point(X3.divide(Z3Z3),Y3.divide(Z3Z3Z3));

- user1454590

---

验证 BigInteger.ONE == 1，是正确的吗？所以 Z1Z1 = Z1^2=1=Z2Z2=Z2^2=1... 然后 U1=X1，U2=X2，S1=Y1，等等... 我有遗漏什么吗？ - abiessu

这个除法不正确。你需要计算模 FIELD 的乘法逆元。这个操作非常昂贵，应该只在标量乘法结束时执行一次，而不是每次进行加倍/加法后执行。使用公式 z^{-1} = ModPow(z, FIELD-2, FIELD)。 - CodesInChaos

是的，BigIntegerOne == 1。实际上，应该使用乘法逆元而不是除法。很好发现。我会尝试一下并报告结果。 - user1454590

成功了！谢谢CodesInChaos。 - user1454590

@CodesInChaos 麻烦您不吝赐教，把您的评论发表为回答吧。您的回答总是直戳问题的痛点，但不幸的是它们总是隐藏在评论里。这使得问题仍然处于开放状态，而实际上已经有了答案。也许我应该做一个自动的“代码”回答生成器，“正如Codes在他的评论中所说：“除法可能不正确。您需要计算模FIELD乘法逆元。这个操作非常耗费时间，应该只在标量乘法结束后执行一次，而不是在每次加倍/加法后执行。”... :) - Maarten Bodewes

Answer 1

CodesInChaos 说：

除法可能不正确。您需要计算模 FIELD 下的乘法逆元。这个操作非常昂贵，应该在标量乘法结束时仅执行一次，而不是每次加倍/相加后执行。使用 z^{-1} = ModPow(z, FIELD-2, FIELD)。

- Maarten Bodewes