# Roots of Polynomial over Finite Field - Characteristic Polynomial

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I am currently trying to implement the Pollard Rho Algorithm using the speed-up with automorphisms applied to the Bitcoin curve Secp256k1. Hence I have the elliptic curve $y^2= x^3+7$ over a finite field with order $p$ such that $p\equiv 1 (mod) 6$, and with prime cardinality $l$.

Then we have an automorphism $\phi: E \to E$ with $(x,y) \mapsto (\xi_6 x, -y)$. Then there exists an integer $s_\phi$ s.t $\forall P \in E( \mathbb{F_{p}} )$ we have $\phi (P) = s_\phi P$. To find this $s_{\phi}$ we calculate the roots of the characteristic polynomial of $\phi$ modulo $l$.

This is the step is where I am working on. I calculate with this example of an elliptic curve over $p = 733387$ with $l = 734443$:

E = EllipticCurve(GF(733387), [0,0,0,0,7])


$P$ and $Q$ are such that $Q = e * P$

P = E([117331 ,426853,1])
Q = E([614057 , 176740 , 1])
card = 734443   #(=the order of P)
k = GF(733387)
k2 = GF(734443)
primroot = k.zeta(6)
print primroot


output 164753 which is of order 6 as wanted in $\mathbb{F_{p}}$

print k(primroot^5+primroot^4+primroot^3+primroot^2+primroot+1)


Here I am not sure, but I think from the cyclotomic theory the minimal polynomial is $x^5+x^4+x^3+x^2+x+1$ for the primitve $6^{th}$ root of unity in $\mathbb{F_{p}}$ ?

since $s_{\phi}$ should be found as a root of the polynomial modulo $l$ I created it in the polynomial ring modulo $l$

Pk = PolynomialRing(k2, 'x')
print Pk
poly = (x^5+x^4+x^3+x^2+x+1)
print poly.roots()
print (poly.roots()[0][0]).parent()


here lies my problem. The root that sage outputs are:

[(-1/2*I*sqrt(3) + 1/2, 1), (1/2*I*sqrt(3) + 1/2, 1), (-1, 1), (-1/2*I*sqrt(3) - 1/2, 1), (1/2*I*sqrt(3) - 1/2, 1)]


I tried to check different questions in the forum and saw that the parent of my root is a Symbolic Ring, but I don't know what to do about it. And I can't continue calculating with my possible $s_{\phi}$. And I need my $s_{\phi}$ to continue the steps in the Pollard Rho algorithm.

My source for this is the "Handbook of Elliptic and Hyperelliptic Curve Cryptography" section 15.2.1.

I would be happy for any advice of maybe different souces that treat this algorithm.

edit retag close merge delete

Sort by ยป oldest newest most voted

If someone is facing the same problem at a point; using

R.<x> = GF(734443)[]
f = x^5+x^4+x^3+x^2+x+1
print f.roots()


gave me the roots in the form I needed!

more