RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2010 Volume 22, Issue 2, Pages 120–132 (Mi dm1099)

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


 English version:
Discrete Mathematics and Applications, 2010, 20:2, 231–246

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024