  RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskr. Mat.: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Diskr. Mat., 2010, Volume 22, Issue 2, Pages 120–132 (Mi dm1099)  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.

DOI: https://doi.org/10.4213/dm1099  Full text: PDF file (158 kB) References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2010, 20:2, 231–246 Bibliographic databases:   UDC: 512.62

Citation: A. V. Markelova, “Discrete logarithm in an arbitrary quotient ring of polynomials of one variable over a finite field”, Diskr. Mat., 22:2 (2010), 120–132; Discrete Math. Appl., 20:2 (2010), 231–246 Citation in format AMSBIB
\Bibitem{Mar10} \by A.~V.~Markelova \paper Discrete logarithm in an arbitrary quotient ring of polynomials of one variable over a~finite field \jour Diskr. Mat. \yr 2010 \vol 22 \issue 2 \pages 120--132 \mathnet{http://mi.mathnet.ru/dm1099} \crossref{https://doi.org/10.4213/dm1099} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2730132} \elib{http://elibrary.ru/item.asp?id=20730339} \transl \jour Discrete Math. Appl. \yr 2010 \vol 20 \issue 2 \pages 231--246 \crossref{https://doi.org/10.1515/DMA.2010.014} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77952961852} 

• http://mi.mathnet.ru/eng/dm1099
• https://doi.org/10.4213/dm1099
• http://mi.mathnet.ru/eng/dm/v22/i2/p120

 SHARE:      Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. S. V. Vostokov, R. P. Vostokova, I. A. Budanaev, “Asymmetric ID-based encryption system, using an explicit pairing function of the reciprocity law”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2016, no. 2, 40–44 2. Vostokov S.V., Vostokova R.P., “Encryption System Using the Explicit Reciprocity Law”, 2016 Xv International Symposium Problems of Redundancy in Information and Control Systems (Redundancy), International Symposium Problems of Redundancy in Information and Control Systems, IEEE, 2016, 175–176 • Number of views: This page: 372 Full text: 95 References: 28 First page: 19 Contact us: math-net2020_01 [at] mi-ras ru Terms of Use Registration Logotypes © Steklov Mathematical Institute RAS, 2020