Roots of Polynomial over Finite Field - Characteristic Polynomial

savecancel

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.