ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 22 Oct 2016 08:50:32 -0500Roots of Polynomial over Finite Field - Characteristic Polynomialhttps://ask.sagemath.org/question/35211/roots-of-polynomial-over-finite-field-characteristic-polynomial/ 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.Fri, 21 Oct 2016 09:01:46 -0500https://ask.sagemath.org/question/35211/roots-of-polynomial-over-finite-field-characteristic-polynomial/Answer by 00Luca00 for <p>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$.</p>
<p>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$.</p>
<p>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$:</p>
<pre><code>E = EllipticCurve(GF(733387), [0,0,0,0,7])
</code></pre>
<p>$P$ and $Q$ are such that $Q = e * P$</p>
<pre><code>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
</code></pre>
<p>output 164753 which is of order 6 as wanted in $\mathbb{F_{p}}$</p>
<pre><code>print k(primroot^5+primroot^4+primroot^3+primroot^2+primroot+1)
</code></pre>
<p>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}}$ ?</p>
<p>since $s_{\phi}$ should be found as a root of the polynomial modulo $l$ I created it in the polynomial ring modulo $l$</p>
<pre><code>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()
</code></pre>
<p>here lies my problem. The root that sage outputs are:</p>
<pre><code>[(-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)]
</code></pre>
<p>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.</p>
<p>My source for this is the "Handbook of Elliptic and Hyperelliptic Curve Cryptography" section 15.2.1.</p>
<p>I would be happy for any advice of maybe different souces that treat this algorithm.</p>
https://ask.sagemath.org/question/35211/roots-of-polynomial-over-finite-field-characteristic-polynomial/?answer=35224#post-id-35224If 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!Sat, 22 Oct 2016 08:50:32 -0500https://ask.sagemath.org/question/35211/roots-of-polynomial-over-finite-field-characteristic-polynomial/?answer=35224#post-id-35224