# Gaussian approach

asked 2017-11-08 02:17:23 -0500 This post is a wiki. Anyone with karma >750 is welcome to improve it.

the two polynomial over field 13 , f1 and f2 f1 is degree 39 polynomial and f2 is degree 13 polynomial . i want to implement algorithm so the from f1 and f2 i will get third degree polynomial. is it possible by multiplication elimination method or gaussian approach.

p=13
K.<a>=GF(p^2);K.modulus()
R.<z> = PolynomialRing( K, sparse=True )
f1=(7*a + 2)*z^39 + (11*a + 8)*z^27 + 11*z^26 + (2*a + 6)*z^15 + 4*z^14 + (12*a + 4)*(7*a + 12)*z + 12*a + 4+ (6*a + 9)*z^3 + 11*z^2 + (a + 3)*z + 6;f1

f2=(3*a + 9)*z^13 + (10*a + 12)*z + 10;f2

edit retag close merge delete

What should the algorithm be designed and good for? I was trying to guess, but this is too hard. Because of the coincidence $3\cdot 13 = 39$ i supposed we are searching for a polynom $g=g(X)$ with $g(f_2)=f_1$ or $f_2(g)=f_1$, but both whishes cannot be fulfilled. First, $f_2$ splits in linear terms, f2.factor(), but $f_1$ does not, one way excluded. On the other way, trying to force $f_1=g(f_2)$, after we require
sage: f1 // f2^3

the $g$ must be of shape $g = (5a+2)X^3+$lower terms. But in the difference $f_1-(5a+2)f_2^3$ there is a term of degree $27$ that cannot be wiped out using $f_2^2$ and lower powers.
So again, if "the algorithm" would deliver a polynomial $g$, which is the mathematical relation connecting ...(more)