Ask Your Question
0

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

asked 2023-11-07 21:04:38 +0100

klx gravatar image

updated 2023-11-07 21:07:38 +0100

I'm trying to implement point halving in Secp256K1 from the 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?

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
2

answered 2023-11-07 21:29:45 +0100

Max Alekseyev gravatar image

updated 2023-11-07 21:33:06 +0100

You did not define x and thus it is considered a symbolic variable rather than a polynomial variable over GF(p). A simple way to fix this is to change R = PolynomialRing(GF(p),'x') into R.<x> = PolynomialRing(GF(p)). Then you'll get roots in GF(p).

edit flag offensive delete link more

Comments

Great, thanks.

klx gravatar imageklx ( 2023-11-07 21:33:38 +0100 )edit
1

answered 2023-11-07 21:58:25 +0100

azerbajdzan gravatar image
R(g).roots()

[(82764486716702815285605477501188164702466527314352175978120539775788537185277, 1)]

You computed roots over rationals instead over modulus p.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-11-07 21:04:38 +0100

Seen: 177 times

Last updated: Nov 07 '23