Theorem on the permutation of coefficients of a polynomial belonging to an ideal ring

$p = a\cdot P$

where P is the permutation matrix, is also an element of the ideal Iₚ, and the cardinalities of Iₐ and Iₚ are the same if Iₚ is the ideal with the minimum cardinality among all ideals containing p(x).

Proof

Consider the polynomial:

, where b(x) is an arbitrary element of the field extension. Obviously, the set Iₚ of all c(x) is an ideal. Let's consider its power. To do this, we write c(x) for an arbitrary b(x) in vector form:

$c = p \cdot b = a \cdot P \cdot B$

, where B is a matrix representing multiplication by the polynomial b(x). And consider element a':

$a'=c \cdot P^{-1} = a \cdot P \cdot B \cdot P^{-1}$

Let us show that a'(x) will belong to Iₐ. For this, it is necessary and sufficient that the matrix, which is the product of the last three, be a matrix of multiplication by some polynomial in the field extension. Note that matrix D is similar to matrix B, where

$D = P \cdot B \cdot P^{-1}$

This means that D is the operation of multiplication by the polynomial b(x) expressed in another basis. This means a' belongs to the same ideal as a. But since this is true for any b(x), and multiplication by the matrix P⁻¹ is a bijection, then the power of Iₚ is not greater than the power of Iₐ.

Carrying out similar reasoning for the polynomial p, we can obtain that the power of Iₐ is not greater than the power of Iₚ, which means that these ideals are of equal power.

Let me note that if we use not a permutation matrix as a matrix P, but any invertible matrix, then we will also obtain the ideal element Iₚ when multiplying the vector a by it.

Where to use?

Probably the most difficult question in this article. For example, you can use this property to construct a new cyclic code from an existing one: as you know, cyclic codes can be represented as polynomials, then from one generating polynomial you can get another. And this property can already be used in cryptography, for example, in systems similar to McEliece: instead of transmitting a generating polynomial that can correct t errors, transmit a generating polynomial that corrects t' errors, where t' < t. Then you can add more errors to the message than the code transmitted in the public key can correct, but the receiving party will still be able to decrypt the message.

Conclusion

This may be a well-known theorem that has passed me by, but its potential use in cryptography is quite interesting: there are ciphers based on linear codes (the aforementioned McEliece), in which the difficulty of decrypting a message is achieved by introducing errors into the encoded message. And introducing more errors than an attacker can correct ruins most attacks on a given cryptosystem. And from the theorem proved above, it can follow that to obtain a code that corrects fewer errors, it is enough to rearrange some coefficients in the generating polynomial of the code (with the exception of the free term and the coefficient at the maximum degree of the polynomial). In this way, the cryptographic strength of the McEliece system can be increased.