I'm trying to factor a polynomial in GF(2^128) using Sage. So I have a polynomial of the form
c_0 * Q^0 + c_1 * Q^1 + c_2 * Q^2 + ... + c_n * Q^n
All coefficients c_i are in GF(2^128) and therefore are polynomials themselves. I'm trying to factor this polynomial but am getting an odd result. For example:
_.<x> = GF(2)[] F.<x> = GF(2^128, modulus = X^128 + X^7 + X^2 + X + 1) R.= PolynomialRing(F) c0 = x^12 + x^7 + x + 1 c1 = x^19 + x^7 + x + 1 c2 = x^126 + x^37 c3 = x^99 poly = (c0 * Q^0) + (c1 * Q^1) + (c2 * Q^2) + (c3 * Q^3) print(poly) print(poly.factor())
The polynomial looks fine:
x^99*Q^3 + (x^126 + x^37)*Q^2 + (x^19 + x^7 + x + 1)*Q + x^12 + x^7 + x + 1
But the factorization is somehow a sum of Q and c terms instead of a sum of their products:
(x^99) * (Q + x^127 + x^123 + x^122 + x^121 + x^119 + x^117 + x^116 + x^114 + x^112 + x^111 + x^109 + x^108 + x^107 + x^106 + x^105 + x^103 + x^100 + x^97 + x^96 + x^95 + x^94 + x^92 + x^91 + x^86 + x^82 + x^81 + x^77 + x^74 + x^73 + x^67 + x^64 + x^63 + x^61 + x^60 + x^59 + x^57 + x^56 + x^55 + x^53 + x^52 + x^50 + x^49 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^42 + x^41 + x^40 + x^39 + x^38 + x^37 + x^33 + x^31 + x^27 + x^26 + x^25 + x^24 + x^21 + x^18 + x^17 + x^15 + x^14 + x^13 + x^12 + x^10 + x^9 + x^7 + x^6 + x^5 + x^3 + x^2 + 1) * (Q + x^127 + x^125 + x^123 + x^117 + x^113 + x^111 + x^110 + x^109 + x^106 + x^105 + x^104 + x^103 + x^99 + x^98 + x^96 + x^95 + x^94 + x^92 + x^91 + x^90 + x^86 + x^83 + x^82 + x^77 + x^76 + x^74 + x^71 + x^69 + x^68 + x^65 + x^64 + x^58 + x^53 + x^52 + x^50 + x^48 + x^47 + x^43 + x^42 + x^41 + x^38 + x^36 + x^35 + x^34 + x^31 + x^30 + x^29 + x^28 + x^26 + x^25 + x^22 + x^21 + x^20 + x^19 + x^18 + x^16 + x^13 + x^12 + x^11 + x^10 + x^7 + x^5 + x^3 + x^2) * (Q + x^127 + x^126 + x^125 + x^122 + x^121 + x^116 + x^110 + x^109 + x^108 + x^105 + x^103 + x^101 + x^100 + x^99 + x^97 + x^95 + x^94 + x^93 + x^92 + x^91 + x^88 + x^87 + x^86 + x^85 + x^83 + x^80 + x^78 + x^73 + x^72 + x^71 + x^70 + x^68 + x^66 + x^65 + x^63 + x^61 + x^60 + x^59 + x^58 + x^57 + x^56 + x^55 + x^49 + x^46 + x^45 + x^44 + x^40 + x^39 + x^37 + x^36 + x^35 + x^34 + x^33 + x^30 + x^29 + x^28 + x^24 + x^22 + x^20 + x^19 + x^17 + x^16 + x^15 + x^14 + x^11 + x^9 + x^5 + x + 1)
How do I get the factorization in a form where each factor looks like the original polynomial form I used?
