Discrete logarithm in an arbitrary quotient ring of polynomials of one variable over a~finite field

A. V. Markelova

Diskretnaya Matematika, Tome 22 (2010) no. 2, pp. 120-132

Résumé

We consider the question of solvability and solution of the congruence relation $a^n(x)\equiv b(x)\pmod{F(x)}$ over a finite field for an arbitrary polynomial $F(x)$. In the case where $F(x)$ is a power of an irreducible polynomial, we give an algorithm of lifting of the solution, that is, the solution of the congruence $$ a^n(x)\equiv b(x)\pmod{f^\alpha(x)} $$ reduces to the solution of the congruence $a^n(x)\equiv b(x)\pmod{f(x)}$. For this case we obtain necessary and sufficient conditions for solvability of exponential congruences. If $F(x)$ is not a power of an irreducible polynomial, then the solution, as before, reduces to the solution of congruences of the form $a^n(x)\equiv b(x)\pmod{f_i(x)}$, but the question of solvability reduces to checking the solvability of congruences of the form $$ a^n(x)\equiv b(x)\pmod{f_i(x)f_j(x)}, $$ where $f_i(x)$ and $f_j(x)$ are irreducible divisors of $F(x)$. For the moduli of the form $f_i(x)f_j(x)$ the result is obtained for some special cases. In addition, we describe a constructive isomorphism of the quotient ring of polynomials $R=GF(p^m)[x]/(f^\alpha(x))$ and a chain ring represented in the form $\overline R=GF(p^r)[x]/(x^t)$, so that the results obtained for polynomials are extended to finite chain rings of prime characteristics. In particular, for the chain rings represented in the form $GF(p^r)[x]/(x^t)$ we give necessary and sufficient conditions for solvability of exponential congruences.