factorization on number fields

edit

The final message of the question is to find the roots. (Not to avoid an error, i had to wait some time, no result and no error were shown.)

Sometimes is better to break somehow / anyhow the polynomials, if possible, so that the algorithms used certainly use the simpler pieces. (We always suppose this is the case, but...)

The following code uses as input a polynomial Q, note that the posted P is related to Q via:

# P = 2 * Q( 100*x ) / 10^48

The following code then finds the roots in the given field without waiting. The trick was to use the intermediate field obtained from the posted polynomial by substituting x^4 to a new variable.

The code is:

R.<x> = QQ[]
Q = ( x^24
      - 883116*x^22
      + 324590112*x^21
      - 285713714286*x^20
      + 33723614276352*x^19
      + 3102013084659300*x^18
      + 445789446082108128*x^17
      - 421500204770774287041*x^16
      - 16120562835322015160832*x^15
      + 20145390309802772107188264*x^14
      - 932226629114457181763294400*x^13
      - 294558998097158263590094201284*x^12
      + 21319700218834773478137466641408*x^11
      + 2405517295281267454415232607265256*x^10
      - 285080670593325925608677261082933312*x^9
      + 2045234688515536966051746765640431375*x^8
      + 805389978318933406294127581790367693312*x^7
      - 47949179186160272725332449686311468857724*x^6
      + 3638421581533823675174220761338599421694112*x^5
      - 336279729800773977232689809647138550783236014*x^4
      + 16845991238074111617967344867690856855723219200*x^3
      - 464257217174251871337457449547186235096443854156*x^2
      + 6593972161118962514282103708472178719452377024352*x
      - 30099620598750107945851944211328293200688722593391 )

# P = 2 * Q( 100*x ) / 10^48

L.<u> = NumberField( x^4  - 7*x^3  + 48*x^2 - 7*x   + 1)
K.<t> = NumberField( x^16 - 7*x^12 + 48*x^8 - 7*x^4 + 1)
emb   = [ emb for emb in L.embeddings(K) if emb(u) == t^4 ][0]

RL.<X> = L[]
RK.<Y> = K[]

print "Q has the following roots in L:"
for root in Q.roots( ring=L, multiplicities=False ):
    print root

print "\nQ has the following factors in L[X]:"
for f, mul in RL(Q).factor():
    print
    print f

    fcoeffs = f.coefficients( sparse=False )
    g = sum( [ emb( fcoeffs[k] ) * Y^k for k in range(len(fcoeffs)) ] )
    print "image of f is g, the following polynomial:"
    print g
    print "roots of g in K:"
    for root in g.roots( ring=K, multiplicities=False ):
        print root

The results are not shown here.

But in order to see why it works, here is the intermediate step:

sage: for f, mul in RL(Q).factor():
....:     print f
....:     
X - 15/4*u^3 - 123/4
X - 3/4*u^3 - 351/4
X + 3/4*u^3 + 615/4
X + 15/4*u^3 + 4707/4
X^2 + (-24*u^3 + 168*u^2 - 1128*u + 150)*X + 2448*u^3 - 17136*u^2 + 115056*u - 7479
X^2 + (-u^3 - 275)*X + 102*u^3 + 35871
X^2 + (u^3 + 47)*X - 102*u^3 + 3027
X^2 + (24*u^3 - 168*u^2 + 1128*u - 18)*X - 2448*u^3 + 17136*u^2 - 115056*u + 9657
X^4 - 948*X^3 + 25974*X^2 + 10203948*X - 81103599
X^4 + (-84*u^3 + 576*u^2 - 4032*u + 216)*X^3 + (3024*u^3 - 20736*u^2 + 145152*u - 15930)*X^2 + (474012*u^3 - 3250368*u^2 + 22752576*u + 3635496)*X + 9330552*u^3 - 63980928*u^2 + 447866496*u - 210398391
X^4 + (84*u^3 - 576*u^2 + 4032*u - 384)*X^3 + (-3024*u^3 + 20736*u^2 - 145152*u + 5670)*X^2 + (-474012*u^3 + 3250368*u^2 - 22752576*u + 7021296)*X - 9330552*u^3 + 63980928*u^2 - 447866496*u - 143751591

Now pari has a much simpler job to find the roots. The above factors over L are moved to polynomials over K, their roots are calculated immediately...