Discrete logarithm in an arbitrary quotient ring of polynomials of one variable over a finite field
А. В. Маркелова · Discrete Mathematics and Applications · 2010
We consider the question of solvability and solution of the congruence relation a n ( x ) ≡ b ( x ) (mod 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 ) ≡ b ( x ) (mod ƒ α ( x )) reduces to the solution of the congruence a n ( x ) ≡ b ( x ) (mod ƒ( 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 ) ≡ b ( x ) (mod ƒ i ( x )), but the question of solvability reduces to checking the solvability of congruences of the form a n ( x ) ≡ b ( x ) (mod ƒ i ( x )ƒ j ( x )), where ƒ i ( x ) and ƒ j ( x ) are irreducible divisors of F ( x ). For the moduli of the form ƒ i ( x )ƒ 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 ]/(ƒ α ( x )) and a chain ring represented in the form , 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.