1
$\begingroup$

This PDF explains that on certain elliptic curves, there exists ZVP (Zero Value Points) that cause zero value registers during the scalar-to-point multiplication (i.e during the double operation or the add operation, one of the intermediate results will be equal to 0).

As stated in the title, I'm looking for a way to solve the polynomial (5x^4 + 2ax^2 - 4bx + a^2 = 0) over the galois field of the curve SECP256R1. After trying out in numpy, I found the galois library which can facilitate modular arithmetic with polynomials etc... But the problem is that the root finding algorithm implemented in the library is the Chien's method, which can (and in my case is) be very computationally intensive and slow.

Even if I use the factoring methods available to me in the library (square free factorization, distinct degree factorization and Cantor-Zassenhaus algorithm) , they barely facilitate the computation...

I've been searching the internet and reading different papers on the internet to find a better solution but it seems like I can't find one... Do I have to just let my computer do its thing and wait a very long time? Or is there a way (either mathematically or coding wise) that I can take in order to speed up the process?

Anything is useful, thanks a lot for your time!

Below is the code I'm using (Python):

import galois
from tinyec import registry, ec

def turn_monic(f):
    #print(f"Polynomial before:\n  {f}")
    coefs = f.coefficients()
    #print(coefs)
    if coefs[0] != 1:
        #print(coefs/coefs[0]
        inv_coef = pow(int(coefs[0]), -1, int(p))
        f = galois.Poly((coefs*inv_coef), field=GF)
    #print(f"Polynomial after:\n  {f}")
return f

if __name__ == '__main__':
    curve = registry.get_curve('secp256r1')
    a = curve.a
    b = curve.b
    p = curve.field.p
    n = curve.field.n
    order = int(0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551)

#Initialize Field
GF = galois.GF(p)

#Initialize Polynomial B
B = galois.Poly([5, 0, (2*a)%p, (-4*b)%p, (a**2)%p], field=GF)

#B_coeffs = [5, 0, (2*a)%p, (-4*b)%p, (a**2)%p]

#B_coeffs.reverse()

#I thought about multi-processing/multi-threading for faster calculations but I am a completely noob to this subject... If you have any good ressources feel free to share them! :D
#multi_thread_8(B_coeffs, p)

#Turns B into a monic polynomial   
B = turn_monic(B)

#Factors B using the mentionned methods
factors = B.factors()
print(factors)

#Finds the roots for each polynomials/monomials in factors
for factor in factors[0]:
    roots = factor.roots()
    print(roots)
$\endgroup$
3
  • $\begingroup$ I don't see a relation between $5x^4+2ax^2-4bx+a^2 \equiv 0\pmod p$ where $p$ is from secp256r1, and "find the Zero Value Points on secp256r1 curve" as in the title. Doesn't the later go $x^3+ax+b\equiv 0\pmod p$ ? Update: ah I see that the linked paper is about "points which take the zero-value registers in the addition formula of Jacobian coordinate implementation", rather than points $(x,0)$, which explains the discrepancy. $\endgroup$
    – fgrieu
    Apr 12 at 15:17
  • $\begingroup$ sagecell.sagemath.org/… $\endgroup$
    – kelalaka
    Apr 12 at 17:57
  • $\begingroup$ Can the techniques for solving quartic equations work, by treating division as multiplication by inverse and treating roots as multivalued roots mod $p$? Divide all terms by $5$ and this equation is a "depressed quartic" already. $\endgroup$
    – Myria
    Apr 12 at 20:41

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.