ufctrhint

ufctrhint(poly,hint)

:: Factorizes uni-variate polynomial poly over the rational number field when the degrees of its factors are known to be some integer multiples of hint.

return

list

poly

uni-variate polynomial with rational coefficients

hint

non-negative integer

• By any reason, if the degree of all the irreducible factors of poly is known to be some multiples of hint, factors can be computed more efficiently by the knowledge than fctr().
• When hint is 1, ufctrhint() is the same as fctr() for uni-variate polynomials. An typical application where ufctrhint() is effective: Consider the case where poly is a norm (See section Algebraic numbers) of a certain polynomial over an extension field with its extension degree d, and it is square free; Then, every irreducible factor has a degree that is a multiple of d.

[10] A=t^9-15*t^6-87*t^3-125;               
t^9-15*t^6-87*t^3-125
0msec
[11] N=res(t,subst(A,t,x-2*t),A);           
-x^81+1215*x^78-567405*x^75+139519665*x^72-19360343142*x^69+1720634125410*x^66
-88249977024390*x^63-4856095669551930*x^60+1999385245240571421*x^57
-15579689952590251515*x^54+15956967531741971462865*x^51
...
+140395588720353973535526123612661444550659875*x^6
+10122324287343155430042768923500799484375*x^3
+139262743444407310133459021182733314453125
980msec + gc : 250msec
[12] sqfr(N);
[[-1,1],[x^81-1215*x^78+567405*x^75-139519665*x^72+19360343142*x^69
-1720634125410*x^66+88249977024390*x^63+4856095669551930*x^60
-1999385245240571421*x^57+15579689952590251515*x^54
...
-10122324287343155430042768923500799484375*x^3
-139262743444407310133459021182733314453125,1]]
20msec
[13] fctr(N);                               
[[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
[x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
+296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
[x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3+31524548679,1],
[x^18+10773*x^12+2784051*x^6+307546875,1]]
167.050sec + gc : 1.890sec
[14] ufctrhint(N,9);
[[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
[x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
+296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
[x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3+31524548679,1],
[x^18+10773*x^12+2784051*x^6+307546875,1]]
119.340sec + gc : 1.300sec

References

section fctr, sqfr.

Go to the first, previous, next, last section, table of contents.