Question on using endomorphism on secp256k1 and negative results

Question

I have read section 3.5 (algorithm 3.7) in "Guide to Elliptic Curve Cryptography", and have been trying to implement endomorphism on secpt256k1 to speed up calculating $kP$ by changing it into 2 point multiplication operations over half-size bit widths of k with a final point add. I tried to implement this in Python first to make sure I had the equations correct.

I can follow algorithm 3.7 to calculate $k_1$ and $k_2$, but for some values of k input I will get a negative $k_2$.

Does this mean when I evaluate $kP = k_1P + k_2φ(P)$, where $φ(P) : (x, y) →(βx, y)$ , I have to either convert $k_2$ to positive by doing $k_2' = n - k_2$ where $n$ is the curve order (this would not make sense as now $k_2$ would be the same bit size of $k$), or do I calculate $k_2φ(P)$ and then find the inverse of this point (just negate the Y coordinate) before adding it to $k_1P$?

This is my code I wrote (I am also not sure if all these operations should be mod n or not).

I do a final check to see if the values match what they should in the textbook ($k = k_1 +k_2λ$ mod n).

But I also have the problem of regardless of $k_2$ being negative (and so I would do the final inversion), the result I calculate from $kP$ does not match the result when I don't use endomorphism (I am using the double-add algorithm for the two point multiplications, not point or NAF, if this makes a difference). I was wondering if anyone knows why?

def decompose_mult(k):
        curve_n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
        lam = 37718080363155996902926221483475020450927657555482586988616620542887997980018
        beta = 55594575648329892869085402983802832744385952214688224221778511981742606582254
        a1 = 64502973549206556628585045361533709077
        a2 = 367917413016453100223835821029139468248
        b2 = 64502973549206556628585045361533709077
        b1_neg = 303414439467246543595250775667605759171

        c1 = (b2*k) // curve_n
        c2 = (b1_neg*k) // curve_n

        c1_a1 = (c1*a1) % curve_n
        c2_a2 = (c2*a2) % curve_n

        c1_b1 = (c1*b1_neg) % curve_n
        c2_b2 = (c2*b2) % curve_n

        k1 = (k - (c1_a1) - (c2_a2)) 
        k2 = c1_b1 - c2_b2

        print ("k1 ", k1, " bits ", k1.bit_length())
        print ("k2 ", k2, " bits ", k2.bit_length())

        k_test = (k1 + k2*lam) % curve_n
        if (k_test == k):
                print("Values matched")
        else:
                print("Values MISMATCHED")
                print ("k_test ", k_test)
                print ("k ", k)
```

Answer 1

Do you mean Algorithm 3.77 on p. 129?

The algorithm has an explicit case for whether $k_{j,i} > 0$ or not, in the loop in step 8.2. Obviously a conditional like this is bad news for fast constant-time arithmetic if taken naively. But as you noted, you can simply do a conditional subtraction in the coordinate field to negate the point, and then do the point addition unconditionally.