I have the following question:

What polynomial, when factored over the field $GF (2^8)$ based on the irreducible polynomial that is used in Rijndael, will factor into all the polynomials in the field?

As I understand it, the polynomial should be an irreducible polynomial and this polynomial must factor all the polynomials. How can I get this polynomial? What steps should I follow?

  • $\begingroup$ I closed this question as even after one month, it is not clear what you actually want to know. Feel free to edit it and comment if you want to have it reopened. $\endgroup$ – Paŭlo Ebermann Apr 21 '12 at 16:24

There are several questions hidden in your question.

You'll have to distinguish between the polynomial ring $\mathbb Z_2[X]$, and the factor field $GF(2^8) = \mathbb Z_2[X]/F$ (where $F$ is any irreductible polynomial of degree 8).

In $\mathbb Z_2[X]$, the only polynomial which is a factor of all others is the trivial polynomial $1$. (In general, in a (unitary) ring the set of elements with this property are called units, and this ring has just the trivial unit one.)

In $GF(2^8)$ (like in any field), every non-zero element is a unit and thus a factor of every other element, but we normally don't call them "polynomials".

But the original question actually asks something else:

What polynomial when factored over the field $GF (2^8)$ based on the irreducible polynomial that is used in Rijndael will factor into all the polynomials in the field?

The expression "factors into" can be understood as "is a multiple of" ... and "when factored over $GF(2^8)$" could be understood as "when seen as a polynomial with coefficients in $GF(2^8)$ (i.e. an element of $GF(2^8)[X]$, and then factored (into its prime divisors)". But then the expression "into all the polynomials in the field" makes no sense, as a field element is either $0$ (which is not a factor other than for itself) or a unit (which is a factor for everything), and you likely don't want $0$ as the result.

Quite likely the original question was something else, but I have no idea, what.

| improve this answer | |

Even after revision, this question makes litle sense. The OP wants a polynomial with the property that

... this polynomial must factor all the polynomials

or possibly

... will factor into all the polynomials in the field

With regard to the first, a polynomial is not an operator or algorithm that can be used to factor a polynomial (or decide that the polynomial is irreducible) and so perhaps the word into was inadvertently omitted, and this question was supposed to be identical to the second.

With regard to the second, it is worth noting that there are no polynomials in the field GF$(2^8)$ except in the sense that all the field elements can be expressed as polynomials of degree $7$ or less with binary coefficients. There are $2^8$ such polynomials ranging from $0$ or $0+0x+0x^2+\cdots+0x^7$ to $1+1x+1x^2+\cdots+1x^7$, and if factor into means a divisor of, then the only polynomial that is a divisor of all these $2^8$ polynomials is $1$, the constant polynomial.

Other possibilities might be the question

What binary polynomials factor into a product of monic linear polynomials over GF$(2^8)$?

Here, monic linear polynomial means $(x-\alpha_i)$ where $\alpha_i \in \text{GF}(2^8)$. One answer would be

All the irreducible binary polynomials of degrees $1, 2, 4$, and $8$ factor into products of linear polynomials over GF$(2^8)$.

Some people would say that GF$(2^8)$ is the splitting field of irreducible binary polynomials of degree $8$. More generally, any polynomial that is a product of any number of these irreducible polynomials (including repeats so that $[f(x)]^i[g(x]^j[h(x)]^k\cdots$ is allowed) will also factor into a product of linear polynomials over GF$(2^8)$ but might have roots with multiplicity greater than $1$.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.