This article is cited in
2 papers
Discrete logarithm in an arbitrary quotient ring of polynomials of one variable over a finite field
A. V. Markelova
Abstract:
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.
UDC:
512.62 Received: 15.09.2009
DOI:
10.4213/dm1099