{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:39:07Z","timestamp":1776724747129,"version":"3.51.2"},"reference-count":7,"publisher":"American Mathematical Society (AMS)","issue":"224","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    In this paper we propose an algorithm for evaluation of logarithms in the finite fields\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper F Subscript p Sub Superscript n\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>F<\/mml:mi>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:msup>\n                                <mml:mi>p<\/mml:mi>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:msup>\n                            <\/mml:mrow>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">F_{p^n}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , where the number\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"p Superscript n Baseline minus 1\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msup>\n                              <mml:mi>p<\/mml:mi>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>\n                              \u2212\n                              \n                            <\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">p^n-1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    has a small primitive factor\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"r\">\n                        <mml:semantics>\n                          <mml:mi>r<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">r<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . The heuristic estimate of the complexity of the algorithm is equal to\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"exp left-parenthesis left-parenthesis c plus o left-parenthesis 1 right-parenthesis right-parenthesis left-parenthesis log p r log squared r right-parenthesis Superscript 1 slash 3 Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>exp<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>c<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>o<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>p<\/mml:mi>\n                            <mml:mspace width=\"thinmathspace\"\/>\n                            <mml:mi>r<\/mml:mi>\n                            <mml:msup>\n                              <mml:mi>log<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>r<\/mml:mi>\n                            <mml:msup>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mn>1<\/mml:mn>\n                                <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                  <mml:mo>\/<\/mml:mo>\n                                <\/mml:mrow>\n                                <mml:mn>3<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\exp ((c+o(1))(\\log p\\,r\\log ^2r)^{1\/3})<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , where\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    grows to\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal infinity\">\n                        <mml:semantics>\n                          <mml:mi mathvariant=\"normal\">\n                            \u221e\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\infty<\/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=\"p\">\n                        <mml:semantics>\n                          <mml:mi>p<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">p<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is limited by a polynomial in\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . The evaluation of logarithms is founded on a new congruence of the kind of D. Coppersmith,\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper C left-parenthesis x right-parenthesis Superscript k Baseline identical-to upper D left-parenthesis x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>C<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:msup>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <mml:mi>k<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>\n                              \u2261\n                              \n                            <\/mml:mo>\n                            <mml:mi>D<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">C(x)^k\\equiv D(x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , which has a great deal of solutions\u2014pairs of polynomials\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper C left-parenthesis x right-parenthesis comma upper D left-parenthesis x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>C<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>D<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">C(x),D(x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    of small degrees.\n                  <\/p>","DOI":"10.1090\/s0025-5718-98-00969-7","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"1679-1689","source":"Crossref","is-referenced-by-count":8,"title":["An algorithm for evaluation of discrete logarithms in some nonprime finite fields"],"prefix":"10.1090","volume":"67","author":[{"given":"Igor","family":"Semaev","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1998]]},"reference":[{"issue":"6","key":"1","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/tit.1976.1055638","article-title":"New directions in cryptography","volume":"IT-22","author":"Diffie, Whitfield","year":"1976","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"1","key":"2","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"},{"key":"3","volume-title":"20th Annual Symposium on Foundations of Computer Science","year":"1979"},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/3-540-39757-4_20","article-title":"Discrete logarithms in finite fields and their cryptographic significance","author":"Odlyzko, A. M.","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/3540160760"},{"issue":"4","key":"5","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1109\/TIT.1984.1056941","article-title":"Fast evaluation of logarithms in fields of characteristic two","volume":"30","author":"Coppersmith, Don","year":"1984","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"4","key":"6","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/BF01137738","article-title":"On the number of small solutions of a linear homogeneous congruence","volume":"50","author":"Semaev, I. A.","year":"1991","journal-title":"Mat. Zametki","ISSN":"https:\/\/id.crossref.org\/issn\/0025-567X","issn-type":"print"},{"key":"7","doi-asserted-by":"crossref","unstructured":"O. Schirokauer, D. Weber and T. Denny, Discrete logarithms: the effectiveness of the index calculus method, Algorithmic number theory, Lecture notes in computer science; vol. 1122, Springer, Berlin and New York, 1996, pp. 337\u2013361.","DOI":"10.1007\/3-540-61581-4_66"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00969-7\/S0025-5718-98-00969-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00969-7\/S0025-5718-98-00969-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:51:59Z","timestamp":1776721919000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00969-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"references-count":7,"journal-issue":{"issue":"224","published-print":{"date-parts":[[1998,10]]}},"alternative-id":["S0025-5718-98-00969-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-98-00969-7","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":[[1998]]}}}