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)  

This article is cited in 2 scientific papers (total 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.

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
Received: 15.09.2009

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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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. Ştiinţe Repub. Mold. Mat., 2016, no. 2, 40–44  mathnet
    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  isi
  • Дискретная математика
    Number of views:
    This page:372
    Full text:95
    References:28
    First page:19

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020