Revision history [back]

Finding the roots of a quartic in GF(p)[x], roots are not correct

I'm trying to implement point halving in Secp255K1 from the paper

https://arxiv.org/pdf/0706.4379.pdf

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
q =  115792089237316195423570985008687907852837564279074904382605163141518161494337

R = PolynomialRing(GF(p),'x')

# x-coordinate of Q where Q = [2]P
qx =  Integer(84538659774007663836420160802839342215744092791779235474817172502887599548487)

g = (2 *x + qx)*(4*(x^3+7)) - (3*x^2)^2


fr = g.roots()

print(fr)


#One of the roots
t = 82764486716702815285605477501188164702466527314352175978120539775788537185277


gg = ((2 *t + qx)*(4*(t^3+7)) - (3*t^2)^2 ) % p

print( "Test root =", gg)

print("\np = ", p)

All the roots contain sqrt(1/7). below one of them.

   (-sqrt(1/7)*sqrt(84538659774007663836420160802839342215744092791779235474817172502887599548487*49^(2/3) - 7*49^(1/3) - 1208359250574819481534600080392050605105087726810769820677796001845964969340249259244945328508262182991854365774319030049384798743132808313732414554357442504885087643109348338916273438084667558118997277395074665220381651943716674620*49^(2/3)/sqrt(49^(2/3) + 7146784996385421511995375187185600364500640046755442503138794024029777351843969475778650820373992863145285880253980604219684490748086217167422326263989169*49^(1/3) - 591770618418053646854941125619875395510208649542454648323720207520213196839409) + 100054989949395901167935252620598405103008960654576195043943116336416882925815572660901111485235900084034002323555728459075582870473207040343912567695848366) - 1/7*sqrt(49^(2/3)*(49^(2/3) + 7146784996385421511995375187185600364500640046755442503138794024029777351843969475778650820373992863145285880253980604219684490748086217167422326263989169*49^(1/3) - 591770618418053646854941125619875395510208649542454648323720207520213196839409)) + 84538659774007663836420160802839342215744092791779235474817172502887599548487, 1)

Normally, I was expecting one root in mod p and an irreducible of degree 3. The expected root is t and it satisfies the equation.

Is this a simplification problem? Or something else?

Finding the roots of a quartic in GF(p)[x], roots are not correct

I'm trying to implement point halving in ~~Secp255K1~~ Secp256K1 from the ~~paper~~ article;

https://arxiv.org/pdf/0706.4379.pdf

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
q =  115792089237316195423570985008687907852837564279074904382605163141518161494337

R = PolynomialRing(GF(p),'x')

# x-coordinate of Q where Q = [2]P
qx =  Integer(84538659774007663836420160802839342215744092791779235474817172502887599548487)

g = (2 *x + qx)*(4*(x^3+7)) - (3*x^2)^2


fr = g.roots()

print(fr)


#One of the roots
t = 82764486716702815285605477501188164702466527314352175978120539775788537185277


gg = ((2 *t + qx)*(4*(t^3+7)) - (3*t^2)^2 ) % p

print( "Test root =", gg)

print("\np = ", p)

All the roots contain sqrt(1/7). below one of them.

   (-sqrt(1/7)*sqrt(84538659774007663836420160802839342215744092791779235474817172502887599548487*49^(2/3) - 7*49^(1/3) - 1208359250574819481534600080392050605105087726810769820677796001845964969340249259244945328508262182991854365774319030049384798743132808313732414554357442504885087643109348338916273438084667558118997277395074665220381651943716674620*49^(2/3)/sqrt(49^(2/3) + 7146784996385421511995375187185600364500640046755442503138794024029777351843969475778650820373992863145285880253980604219684490748086217167422326263989169*49^(1/3) - 591770618418053646854941125619875395510208649542454648323720207520213196839409) + 100054989949395901167935252620598405103008960654576195043943116336416882925815572660901111485235900084034002323555728459075582870473207040343912567695848366) - 1/7*sqrt(49^(2/3)*(49^(2/3) + 7146784996385421511995375187185600364500640046755442503138794024029777351843969475778650820373992863145285880253980604219684490748086217167422326263989169*49^(1/3) - 591770618418053646854941125619875395510208649542454648323720207520213196839409)) + 84538659774007663836420160802839342215744092791779235474817172502887599548487, 1)

Normally, I was expecting one root in mod p and an irreducible of degree 3. The expected root is t and it satisfies the equation.

Is this a simplification problem? Or something else?