package org.bouncycastle.math.ec;

import java.math.BigInteger;

public class ECAlgorithms
{
    public static ECPoint sumOfTwoMultiplies(ECPoint P, BigInteger a,
        ECPoint Q, BigInteger b)
    {
        ECCurve cp = P.getCurve();
        Q = importPoint(cp, Q);

        // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick
        if (cp instanceof ECCurve.F2m)
        {
            ECCurve.F2m f2mCurve = (ECCurve.F2m)cp;
            if (f2mCurve.isKoblitz())
            {
                return P.multiply(a).add(Q.multiply(b));
            }
        }

        return implShamirsTrick(P, a, Q, b);
    }

    /*
     * "Shamir's Trick", originally due to E. G. Straus
     * (Addition chains of vectors. American Mathematical Monthly,
     * 71(7):806-808, Aug./Sept. 1964)
     * <pre>
     * Input: The points P, Q, scalar k = (km?, ... , k1, k0)
     * and scalar l = (lm?, ... , l1, l0).
     * Output: R = k * P + l * Q.
     * 1: Z <- P + Q
     * 2: R <- O
     * 3: for i from m-1 down to 0 do
     * 4:        R <- R + R        {point doubling}
     * 5:        if (ki = 1) and (li = 0) then R <- R + P end if
     * 6:        if (ki = 0) and (li = 1) then R <- R + Q end if
     * 7:        if (ki = 1) and (li = 1) then R <- R + Z end if
     * 8: end for
     * 9: return R
     * </pre>
     */
    public static ECPoint shamirsTrick(ECPoint P, BigInteger k,
        ECPoint Q, BigInteger l)
    {
        ECCurve cp = P.getCurve();
        Q = importPoint(cp, Q);

        return implShamirsTrick(P, k, Q, l);
    }

    private static ECPoint importPoint(ECCurve c, ECPoint Q)
    {
        ECCurve cq = Q.getCurve();
        if (!c.equals(cq))
        {
            throw new IllegalArgumentException("P and Q must be on same curve");
        }
        return c.importPoint(Q);
    }

    private static ECPoint implShamirsTrick(ECPoint P, BigInteger k,
        ECPoint Q, BigInteger l)
    {
        P = P.normalize();
        Q = Q.normalize();
        ECPoint Z = P.add(Q).normalize();

        int m = Math.max(k.bitLength(), l.bitLength());
        ECPoint R = P.getCurve().getInfinity();

        for (int i = m - 1; i >= 0; --i)
        {
            if (k.testBit(i))
            {
                if (l.testBit(i))
                {
                    R = R.twicePlus(Z);
                }
                else
                {
                    R = R.twicePlus(P);
                }
            }
            else
            {
                if (l.testBit(i))
                {
                    R = R.twicePlus(Q);
                }
                else
                {
                    R = R.twice();
                }
            }
        }

        return R;
    }
}

@@ -1986,32 +1986,33 @@
  Q.normalize();%0A
+%0A
         ECPoint 
@@ -2015,148 +2015,175 @@
 int 
-Z = P.add(Q).normalize();%0A%0A        int m = Math.max(k.bitLength(), l.bitLength());%0A        ECPoint R = P.getCurve().getInfinity
+infinity = P.getCurve().getInfinity();%0A%0A        // TODO conjugate co-Z addition (ZADDC) can return both of these%0A        ECPoint PaddQ = P.add(Q).normalize
 ();%0A
-%0A
         
 for 
@@ -2182,292 +2182,323 @@
     
-for (int i = m - 1; i %3E= 0; --i)%0A        %7B%0A            if (k.testBit(i))%0A            %7B%0A                if (l.testBit(i))%0A                %7B%0A                    R = R.twicePlus(Z);%0A                %7D%0A                else%0A                %7B%0A                    R = R.twicePlus(P
+ECPoint PsubQ = P.subtract(Q).normalize();%0A%0A        ECPoint%5B%5D points = new ECPoint%5B%5D %7B%0A            PaddQ.negate(), P.negate(), PsubQ.negate(),%0A            Q.negate(), infinity, Q,%0A            PsubQ, P, PaddQ %7D;%0A%0A        byte%5B%5D kNaf = WNafUtil.generateNaf(k);%0A        byte%5B%5D lNaf = WNafUtil.generateNaf(l
 );%0A
+%0A
         
     
@@ -2497,278 +2497,315 @@
     
-        %7D%0A            %7D%0A            else%0A            %7B%0A                if (l.testBit(i))%0A                %7B%0A                    R = R.twicePlus(Q);%0A                %7D%0A                else%0A                %7B%0A                    R = R.twice();%0A                %7D%0A            %7D
+ECPoint R = infinity;%0A%0A        int i = Math.max(kNaf.length, lNaf.length);%0A        while (--i %3E= 0)%0A        %7B%0A            int kni = i %3C kNaf.length ? kNaf%5Bi%5D + 1 : 1;%0A            int lni = i %3C lNaf.length ? lNaf%5Bi%5D + 1 : 1;%0A%0A            int index = kni * 3 + lni;%0A            R = R.twicePlus(points%5Bindex%5D);
 %0A   

Implement "Shamir's trick" using NAF form of the scalars