Gaussian approach

asked 2017-11-08 09:17:23 +0100

this post is marked as community wiki

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 flag offensive close merge delete

Comments

Could you please tell us which result do you expect from the given example ?

tmonteil gravatar imagetmonteil ( 2017-11-08 10:55:26 +0100 )edit

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
5*a + 2
sage: f1 - (5*a+2)*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)

dan_fulea gravatar imagedan_fulea ( 2017-11-08 13:04:45 +0100 )edit