{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:58:51Z","timestamp":1776805131982,"version":"3.51.2"},"reference-count":4,"publisher":"American Mathematical Society (AMS)","issue":"319","license":[{"start":{"date-parts":[[2019,12,31]],"date-time":"2019-12-31T00:00:00Z","timestamp":1577750400000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00c3\u00a1 Agentura ?esk\u00c3\u00a9 Republiky","doi-asserted-by":"publisher","award":["18-19087S 301-13\/201843"],"award-info":[{"award-number":["18-19087S 301-13\/201843"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00c3\u00a1 Agentura ?esk\u00c3\u00a9 Republiky","doi-asserted-by":"publisher","award":["ERC-669891"],"award-info":[{"award-number":["ERC-669891"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["18-19087S 301-13\/201843"],"award-info":[{"award-number":["18-19087S 301-13\/201843"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC-669891"],"award-info":[{"award-number":["ERC-669891"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    In this paper, we revisit the ZigZag strategy of Granger, Kleinjung, and Zumbr\u00e4gel. In particular, we provide a new algorithm and proof for the so-called degree\u00a02 elimination step. This allows us to provide a stronger theorem concerning discrete logarithm computations in small characteristic fields\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"double-struck upper F Subscript q Sub Superscript k 0 k\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:msup>\n                                <mml:mi>q<\/mml:mi>\n                                <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                  <mml:msub>\n                                    <mml:mi>k<\/mml:mi>\n                                    <mml:mn>0<\/mml:mn>\n                                  <\/mml:msub>\n                                  <mml:mi>k<\/mml:mi>\n                                <\/mml:mrow>\n                              <\/mml:msup>\n                            <\/mml:mrow>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {F}_{q^{k_0k}}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    with\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"k\">\n                        <mml:semantics>\n                          <mml:mi>k<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">k<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    close to\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"q\">\n                        <mml:semantics>\n                          <mml:mi>q<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">q<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"k 0\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mn>0<\/mml:mn>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">k_0<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    a small integer. As in the aforementioned paper, we rely on the existence of two polynomials\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"h 0\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>h<\/mml:mi>\n                            <mml:mn>0<\/mml:mn>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">h_0<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"h 1\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>h<\/mml:mi>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">h_1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    of degree\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"2\">\n                        <mml:semantics>\n                          <mml:mn>2<\/mml:mn>\n                          <mml:annotation encoding=\"application\/x-tex\">2<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    providing a convenient representation of the finite field\u00a0\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"double-struck upper F Subscript q Sub Superscript k 0 k\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:msup>\n                                <mml:mi>q<\/mml:mi>\n                                <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                  <mml:msub>\n                                    <mml:mi>k<\/mml:mi>\n                                    <mml:mn>0<\/mml:mn>\n                                  <\/mml:msub>\n                                  <mml:mi>k<\/mml:mi>\n                                <\/mml:mrow>\n                              <\/mml:msup>\n                            <\/mml:mrow>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {F}_{q^{k_0k}}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    .\n                  <\/p>","DOI":"10.1090\/mcom\/3404","type":"journal-article","created":{"date-parts":[[2018,10,10]],"date-time":"2018-10-10T11:53:11Z","timestamp":1539172391000},"page":"2485-2496","source":"Crossref","is-referenced-by-count":1,"title":["A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms"],"prefix":"10.1090","volume":"88","author":[{"given":"Faruk","family":"G\u00f6lo\u011flu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Joux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2018,12,31]]},"reference":[{"issue":"203","key":"1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2152932","article-title":"A subexponential algorithm for discrete logarithms over all finite fields","volume":"61","author":"Adleman, Leonard M.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"2","unstructured":"R. Granger, T. Kleinjung, and J. Zumbr\u00e4gel, On the discrete logarithm problem in finite fields of fixed characteristic, Cryptology ePrint Archive, Report 2015\/685, 2015."},{"key":"3","isbn-type":"print","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/978-3-662-45611-8_20","article-title":"Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms: simplified setting for small characteristic finite fields","author":"Joux, Antoine","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9783662456118"},{"issue":"1","key":"4","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1109\/tit.1978.1055817","article-title":"An improved algorithm for computing logarithms over \ud835\udc3a\ud835\udc39(\ud835\udc5d) and its cryptographic significance","volume":"IT-24","author":"Pohlig, Stephen C.","year":"1978","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-319\/S0025-5718-2018-03404-4\/mcom3404_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2019-88-319\/S0025-5718-2018-03404-4\/S0025-5718-2018-03404-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-319\/S0025-5718-2018-03404-4\/S0025-5718-2018-03404-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:15:03Z","timestamp":1776802503000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-319\/S0025-5718-2018-03404-4\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,31]]},"references-count":4,"journal-issue":{"issue":"319","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["S0025-5718-2018-03404-4"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3404","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2018,12,31]]}}}