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) ```