{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T23:06:08Z","timestamp":1772924768690,"version":"3.50.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,6,15]],"date-time":"2020-06-15T00:00:00Z","timestamp":1592179200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,15]],"date-time":"2020-06-15T00:00:00Z","timestamp":1592179200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we consider in detail the composition of an irreducible polynomial with <jats:inline-formula><jats:alternatives><jats:tex-math>$$X^2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>X<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and suggest a recurrent construction of irreducible polynomials of fixed degree over finite fields of odd characteristics. More precisely, given an irreducible polynomial of degree <jats:italic>n<\/jats:italic> and order <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^rt$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mn>2<\/mml:mn>\n                      <mml:mi>r<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mi>t<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with <jats:italic>t<\/jats:italic> odd, the construction produces <jats:inline-formula><jats:alternatives><jats:tex-math>$$ord_t(2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>o<\/mml:mi>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:msub>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mi>t<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mn>2<\/mml:mn>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> irreducible polynomials of degree <jats:italic>n<\/jats:italic> and order <jats:italic>t<\/jats:italic>. The construction can be used for example to search irreducible polynomials with specific requirements on its coefficients.<\/jats:p>","DOI":"10.1007\/s00200-020-00439-7","type":"journal-article","created":{"date-parts":[[2020,6,15]],"date-time":"2020-06-15T15:03:58Z","timestamp":1592233438000},"page":"163-171","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A recurrent construction of irreducible polynomials of fixed degree over finite fields"],"prefix":"10.1007","volume":"33","author":[{"given":"Gohar M.","family":"Kyureghyan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Melsik K.","family":"Kyureghyan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,15]]},"reference":[{"key":"439_CR1","doi-asserted-by":"publisher","DOI":"10.1142\/9407","volume-title":"Algebraic Coding Theory","author":"E Berlekamp","year":"2015","unstructured":"Berlekamp, E.: Algebraic Coding Theory. Worls Scientific Publ. Co. Pte. Ltd., Singapore (2015)"},{"key":"439_CR2","unstructured":"Brochero Mart\u00ecnez, F.E., Reis, L., Silva, L.: Factorization of Composed Polynomials and Applications. arXiv:1901.02951"},{"issue":"1","key":"439_CR3","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1093\/qmath\/4.1.4","volume":"4","author":"L Carlitz","year":"1953","unstructured":"Carlitz, L.: Distribution of primitive roots in a finite field. Q. J. Math. Oxf. Ser. (2) 4(1), 4\u201310 (1953)","journal-title":"Q. J. Math. Oxf. Ser. (2)"},{"key":"439_CR4","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF00124895","volume":"2","author":"SD Cohen","year":"1992","unstructured":"Cohen, S.D.: The explicit construction of irreducible polynomials over finite fields. Des. Codes Cryptogr. 2, 169\u2013173 (1992)","journal-title":"Des. Codes Cryptogr."},{"key":"439_CR5","unstructured":"Cohen, S.D., Kapetanakis, G.: Finite Field Extensions with the Line or Translate Property for $r$-Primitive Elements. arXiv:1906.08046"},{"issue":"1","key":"439_CR6","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1093\/qmath\/os-8.1.308","volume":"8","author":"H Davenport","year":"1937","unstructured":"Davenport, H.: On primitive roots in finite fields. Q. J. Math. Oxf. 8(1), 308\u2013312 (1937)","journal-title":"Q. J. Math. Oxf."},{"issue":"4","key":"439_CR7","doi-asserted-by":"publisher","first-page":"981","DOI":"10.2140\/ant.2013.7.981","volume":"7","author":"P Kurlberg","year":"2013","unstructured":"Kurlberg, P., Pomerance, C.: On a problem of Arnold: the average multiplicative order of a given integer. Algebra Number Theory 7(4), 981\u2013999 (2013)","journal-title":"Algebra Number Theory"},{"issue":"1","key":"439_CR8","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S1071-5797(02)00005-9","volume":"9","author":"M Kyuregyan","year":"2003","unstructured":"Kyuregyan, M.: Recurrent methods for constructing irreducible polynomials over ${{\\mathbb{F}}_q}$ of odd characteristics. Finite Fields Appl. 9(1), 39\u201358 (2003)","journal-title":"Finite Fields Appl."},{"issue":"3","key":"439_CR9","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.ffa.2005.07.002","volume":"12","author":"M Kyuregyan","year":"2006","unstructured":"Kyuregyan, M.: Recurrent methods for constructing irreducible polynomials over ${{\\mathbb{F}}_q}$ of odd characteristics. II. Finite Fields Appl. 12(3), 357\u2013378 (2006)","journal-title":"Finite Fields Appl."},{"issue":"3","key":"439_CR10","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s10623-010-9478-5","volume":"61","author":"M Kyuregyan","year":"2011","unstructured":"Kyuregyan, M., Kyureghyan, G.: Irreducible compositions of polynomials over finite fields. Des. Codes Cryptogr. 61(3), 301\u2013314 (2011)","journal-title":"Des. Codes Cryptogr."},{"key":"439_CR11","unstructured":"Pomerance, C.: The Multiplicative Order Mod $n$, on Average. https:\/\/math.dartmouth.edu\/~carlp\/PDF\/ordertalk.pdf. Accessed Nov 2019"},{"key":"439_CR12","doi-asserted-by":"crossref","unstructured":"Pomerance, C., Shparlinski, I.E.: Smooth orders and cryptographic applications. In: Fieker, C., Kohel, D.R. (Eds.): ANTS 2002, LNCS 2369, pp. 338\u2013348 (2002)","DOI":"10.1007\/3-540-45455-1_27"},{"key":"439_CR13","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s10623-012-9647-9","volume":"69","author":"A Tuxanidy","year":"2013","unstructured":"Tuxanidy, A., Wang, Q.: Composed products and factors of cyclotomic polynomials over finite fields. Des. Codes Cryptogr. 69, 203\u2013231 (2013)","journal-title":"Des. Codes Cryptogr."}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-020-00439-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00200-020-00439-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-020-00439-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,12]],"date-time":"2022-02-12T10:02:39Z","timestamp":1644660159000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00200-020-00439-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,15]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["439"],"URL":"https:\/\/doi.org\/10.1007\/s00200-020-00439-7","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,15]]},"assertion":[{"value":"10 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}