{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:48:36Z","timestamp":1776797316163,"version":"3.51.2"},"reference-count":18,"publisher":"American Mathematical Society (AMS)","issue":"291","license":[{"start":{"date-parts":[[2015,6,10]],"date-time":"2015-06-10T00:00:00Z","timestamp":1433894400000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    In this paper we generalize the classical Proth\u2019s theorem and the Miller-Rabin test for integers of the form\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper N equals upper K p Superscript n Baseline plus 1\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mi>K<\/mml:mi>\n                            <mml:msup>\n                              <mml:mi>p<\/mml:mi>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">N=Kp^n+1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . For these families, we present variations on the classical Pocklington\u2019s results and, in particular, a primality test whose computational complexity is\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"ModifyingAbove upper O With tilde left-parenthesis log squared upper N right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mover>\n                                <mml:mi>O<\/mml:mi>\n                                <mml:mo>\n                                  ~\n                                  \n                                <\/mml:mo>\n                              <\/mml:mover>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\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>N<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\widetilde {O}(\\log ^2 N)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and, what is more important, that requires only one modular exponentiation modulo\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper 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                    similar to that of Fermat\u2019s test.\n                  <\/p>","DOI":"10.1090\/s0025-5718-2014-02849-4","type":"journal-article","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T08:35:11Z","timestamp":1402389311000},"page":"505-512","source":"Crossref","is-referenced-by-count":4,"title":["A primality test for \ud835\udc3e\ud835\udc5d\u207f+1 numbers"],"prefix":"10.1090","volume":"84","author":[{"given":"Jos\u00e9","family":"Grau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio","family":"Oller-Marc\u00e9n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Sadornil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2014,6,10]]},"reference":[{"issue":"7","key":"1","doi-asserted-by":"publisher","first-page":"1923","DOI":"10.1090\/S0002-9939-99-04786-3","article-title":"Cubic reciprocity and generalised Lucas-Lehmer tests for primality of \ud835\udc34\u22c53\u207f\u00b11","volume":"127","author":"Berrizbeitia, Pedro","year":"1999","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1006\/jsco.1999.0343","article-title":"Generalized strong pseudoprime tests and applications","volume":"30","author":"Berrizbeitia, Pedro","year":"2000","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"107","DOI":"10.4064\/aa110-2-1","article-title":"A generalization of Proth\u2019s theorem","volume":"110","author":"Berrizbeitia, Pedro","year":"2003","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"2","key":"4","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1090\/S0002-9939-01-06100-7","article-title":"Deterministic primality test for numbers of the form \ud835\udc34\u00b2\u22c53\u207f+1,\ud835\udc5b\u22653 odd","volume":"130","author":"Berrizbeitia, Pedro","year":"2002","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"issue":"9","key":"5","doi-asserted-by":"publisher","first-page":"3095","DOI":"10.1090\/S0002-9939-08-09303-9","article-title":"A generalization of Miller\u2019s primality theorem","volume":"136","author":"Berrizbeitia, Pedro","year":"2008","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1090\/fic\/041\/07","article-title":"Cubic reciprocity and explicit primality tests for \u210e\u22c53^{\ud835\udc58}\u00b11","author":"Bosma, Wieb","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0821833537"},{"key":"7","doi-asserted-by":"publisher","first-page":"620","DOI":"10.2307\/2005583","article-title":"New primality criteria and factorizations of 2^{\ud835\udc5a}\u00b11","volume":"29","author":"Brillhart, John","year":"1975","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"8","isbn-type":"print","volume-title":"Prime numbers","author":"Crandall, Richard","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387252827","edition":"2"},{"issue":"276","key":"9","doi-asserted-by":"publisher","first-page":"2315","DOI":"10.1090\/S0025-5718-2011-02489-0","article-title":"An \ud835\udc42\u0303(log\u00b2(\ud835\udc41)) time primality test for generalized Cullen numbers","volume":"80","author":"Grau, Jos\u00e9 Mar\u00eda","year":"2011","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/BF02074886","article-title":"Effective primality tests for integers of the forms \ud835\udc41=\ud835\udc58\u22c53\u207f+1 and \ud835\udc41=\ud835\udc58\u22c52^{\ud835\udc5a}3\u207f+1","volume":"32","author":"Guthmann, Andreas","year":"1992","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"key":"11","series-title":"Springer Monographs in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12893-0","volume-title":"Reciprocity laws","author":"Lemmermeyer, Franz","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540669574"},{"issue":"1","key":"12","first-page":"44","article-title":"Artin reciprocity and Mersenne primes","volume":"1","author":"Lenstra, H. W., Jr.","year":"2000","journal-title":"Nieuw Arch. Wiskd. (5)","ISSN":"https:\/\/id.crossref.org\/issn\/0028-9825","issn-type":"print"},{"key":"13","unstructured":"Th\u00e9ophile P\u00e9pin, Sur la Formule 2^{2\u207f}+1, C. R. Acad. Sci. Paris, 85:329\u2013331, 1877."},{"key":"14","unstructured":"H. C. Pocklington, The determination of the prime or composite nature of large numbers by fermat\u2019s theorem, Proc. Cambridge Philos. Soc., 18:29\u201330, 1914."},{"key":"15","unstructured":"Fran\u00e7ois Proth. Th\u00e9or\u00e9mes sur les nombre premiers, C. R. Acad. Sci. Paris, 87:926, 1878."},{"key":"16","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"issue":"4","key":"17","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1080\/00150517.1988.12429609","article-title":"A note on the primality of 6^{2\u207f}+1 and 10^{2\u207f}+1","volume":"26","author":"Williams, H. C.","year":"1988","journal-title":"Fibonacci Quart.","ISSN":"https:\/\/id.crossref.org\/issn\/0015-0517","issn-type":"print"},{"key":"18","doi-asserted-by":"publisher","first-page":"995","DOI":"10.2307\/2005886","article-title":"Some prime numbers of the forms 2\ud835\udc343\u207f+1 and 2\ud835\udc343\u207f-1","volume":"26","author":"Williams, H. C.","year":"1972","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2015-84-291\/S0025-5718-2014-02849-4\/S0025-5718-2014-02849-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-291\/S0025-5718-2014-02849-4\/S0025-5718-2014-02849-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:13:02Z","timestamp":1776795182000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-291\/S0025-5718-2014-02849-4\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,10]]},"references-count":18,"journal-issue":{"issue":"291","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["S0025-5718-2014-02849-4"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2014-02849-4","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":[[2014,6,10]]}}}