{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:45:43Z","timestamp":1776725143388,"version":"3.51.2"},"reference-count":10,"publisher":"American Mathematical Society (AMS)","issue":"232","license":[{"start":{"date-parts":[[2001,2,23]],"date-time":"2001-02-23T00:00:00Z","timestamp":982886400000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Deterministic polynomial time primality criteria for\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"2 Superscript n Baseline minus 1\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msup>\n                              <mml:mn>2<\/mml:mn>\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\">2^n-1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    have been known since the work of Lucas in 1876\u20131878. Little is known, however, about the existence of deterministic polynomial time primality tests for numbers of the more general form\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper N Subscript n Baseline equals left-parenthesis p minus 1 right-parenthesis p Superscript n Baseline minus 1\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msub>\n                              <mml:mi>N<\/mml:mi>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>p<\/mml:mi>\n                            <mml:mo>\n                              \u2212\n                              \n                            <\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mspace width=\"thinmathspace\"\/>\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\">N_n=(p-1)\\,p^n-1<\/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=\"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 any fixed prime. When\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n greater-than left-parenthesis p minus 1 right-parenthesis slash 2\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>p<\/mml:mi>\n                            <mml:mo>\n                              \u2212\n                              \n                            <\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo>\/<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n&gt;(p-1)\/2<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    we show that it is always possible to produce a Lucas-like deterministic test for the primality of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper N Subscript n\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">N_n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    which requires that only\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis q left-parenthesis p plus log q right-parenthesis plus p cubed plus log upper N Subscript n Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>q<\/mml:mi>\n                            <mml:mspace width=\"thinmathspace\"\/>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>p<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>q<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>p<\/mml:mi>\n                              <mml:mn>3<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:msub>\n                              <mml:mi>N<\/mml:mi>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(q\\,(p+\\log q)+p^3+\\log N_n)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    modular multiplications be performed modulo\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper N Subscript n\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">N_n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , as long as we can find a prime\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                    of the form\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"1 plus k p\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mspace width=\"thinmathspace\"\/>\n                            <mml:mi>p<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">1+k\\, p<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    such that\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper N Subscript n Superscript k Baseline minus 1\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msubsup>\n                              <mml:mi>N<\/mml:mi>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mspace width=\"thinmathspace\"\/>\n                                <mml:mi>k<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msubsup>\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\">N_n^{\\,k}-1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is not divisible by\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                    . We also show that for all\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                    with\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"3 greater-than p greater-than 10 Superscript 7\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mn>3<\/mml:mn>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mi>p<\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:msup>\n                              <mml:mn>10<\/mml:mn>\n                              <mml:mn>7<\/mml:mn>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">3&gt;p&gt;10^7<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    such a\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                    can be found very readily, and that the most difficult case in which to find a\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                    appears, somewhat surprisingly, to be that for\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"p equals 3\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>p<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mn>3<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">p=3<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Some explanation is provided as to why this case is so difficult.\n                  <\/p>","DOI":"10.1090\/s0025-5718-00-01212-6","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:17:31Z","timestamp":1027707451000},"page":"1721-1734","source":"Crossref","is-referenced-by-count":5,"title":["Explicit primality criteria for (\ud835\udc5d-1)\ud835\udc5d\u207f-1"],"prefix":"10.1090","volume":"69","author":[{"given":"Andreas","family":"Stein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Williams","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2000,2,23]]},"reference":[{"issue":"191","key":"1","doi-asserted-by":"publisher","first-page":"355","DOI":"10.2307\/2008811","article-title":"Explicit bounds for primality testing and related problems","volume":"55","author":"Bach, Eric","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"203","key":"2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.2307\/2152938","article-title":"Explicit primality criteria for \u210e\u22c52^{\ud835\udc58}\u00b11","volume":"61","author":"Bosma, Wieb","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"3","doi-asserted-by":"crossref","unstructured":"D. H. Lehmer. An extended theory of Lucas\u2019 functions. Annals of Mathematics, 31:419\u2013448, 1930.","DOI":"10.2307\/1968235"},{"key":"4","unstructured":"E. Lucas. Nouveaux th\u00e9oremes d\u2018arithm\u00e9tique sup\u00e9rieure. Comptes Rendus Acad. des Sciences, Paris, 83:1286\u20131288, 1876."},{"key":"5","first-page":"533","article-title":"An algorithm for determining certain large primes","author":"Williams, H. C.","year":"1971"},{"key":"6","doi-asserted-by":"publisher","first-page":"585","DOI":"10.4153\/CMB-1972-101-7","article-title":"The primality of \ud835\udc41=2\ud835\udc343\u207f-1","volume":"15","author":"Williams, H. C.","year":"1972","journal-title":"Canad. Math. Bull.","ISSN":"https:\/\/id.crossref.org\/issn\/0008-4395","issn-type":"print"},{"issue":"1","key":"7","doi-asserted-by":"publisher","first-page":"7","DOI":"10.4064\/aa-39-1-7-17","article-title":"The primality of certain integers of the form 2\ud835\udc34\ud835\udc5f\u207f-1","volume":"39","author":"Williams, H. C.","year":"1981","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"2","key":"8","doi-asserted-by":"crossref","first-page":"477","DOI":"10.2140\/pjm.1982.98.477","article-title":"A class of primality tests for trinomials which includes the Lucas-Lehmer test","volume":"98","author":"Williams, H. C.","year":"1982","journal-title":"Pacific J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0030-8730","issn-type":"print"},{"issue":"177","key":"9","doi-asserted-by":"publisher","first-page":"385","DOI":"10.2307\/2007898","article-title":"Effective primality tests for some integers of the forms \ud835\udc345\u207f-1 and \ud835\udc347\u207f-1","volume":"48","author":"Williams, H. C.","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"10","unstructured":"H. C. Williams. \u00c9douard Lucas and Primality Testing, volume 22 of Canadian Mathematical Society Series of Monographs and Advanced Texts. Wiley, NY, 1998."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2000-69-232\/S0025-5718-00-01212-6\/S0025-5718-00-01212-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2000-69-232\/S0025-5718-00-01212-6\/S0025-5718-00-01212-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:27:29Z","timestamp":1776724049000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2000-69-232\/S0025-5718-00-01212-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,2,23]]},"references-count":10,"journal-issue":{"issue":"232","published-print":{"date-parts":[[2000,10]]}},"alternative-id":["S0025-5718-00-01212-6"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-00-01212-6","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":[[2000,2,23]]}}}