{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:42:14Z","timestamp":1776847334982,"version":"3.51.2"},"reference-count":5,"publisher":"American Mathematical Society (AMS)","issue":"213","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Recently, Damg\u00e5rd, Landrock and Pomerance described a procedure in which a\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                    -bit odd number is chosen at random and subjected to\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"t\">\n                        <mml:semantics>\n                          <mml:mi>t<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">t<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    random strong probable prime tests. If the chosen number passes all\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"t\">\n                        <mml:semantics>\n                          <mml:mi>t<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">t<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    tests, then the procedure will return that number; otherwise, another\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                    -bit odd integer is selected and then tested. The procedure ends when a number that passes all\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"t\">\n                        <mml:semantics>\n                          <mml:mi>t<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">t<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    tests is found. Let\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"p Subscript k comma t\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>p<\/mml:mi>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi>k<\/mml:mi>\n                              <mml:mo>,<\/mml:mo>\n                              <mml:mi>t<\/mml:mi>\n                            <\/mml:mrow>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">p_{k,t}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    denote the probability that such a number is composite. The authors above have shown that\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"p Subscript k comma t Baseline less-than-or-equal-to 4 Superscript negative t\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msub>\n                              <mml:mi>p<\/mml:mi>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi>k<\/mml:mi>\n                                <mml:mo>,<\/mml:mo>\n                                <mml:mi>t<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msub>\n                            <mml:mo>\n                              \u2264\n                              \n                            <\/mml:mo>\n                            <mml:msup>\n                              <mml:mn>4<\/mml:mn>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mo>\n                                  \u2212\n                                  \n                                <\/mml:mo>\n                                <mml:mi>t<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">p_{k,t}\\le 4^{-t}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    when\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"k greater-than-or-equal-to 51\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>\n                              \u2265\n                              \n                            <\/mml:mo>\n                            <mml:mn>51<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">k\\ge 51<\/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=\"t greater-than-or-equal-to 1\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>t<\/mml:mi>\n                            <mml:mo>\n                              \u2265\n                              \n                            <\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">t\\ge 1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . In this paper we will show that this is in fact valid for all\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"k greater-than-or-equal-to 2\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>\n                              \u2265\n                              \n                            <\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">k\\ge 2<\/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=\"t greater-than-or-equal-to 1\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>t<\/mml:mi>\n                            <mml:mo>\n                              \u2265\n                              \n                            <\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">t\\ge 1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    .\n                  <\/p>","DOI":"10.1090\/s0025-5718-96-00695-3","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"373-381","source":"Crossref","is-referenced-by-count":7,"title":["Further investigations with the strong probable prime test"],"prefix":"10.1090","volume":"65","author":[{"suffix":"Jr.","given":"Ronald","family":"Burthe","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1996]]},"reference":[{"key":"1","isbn-type":"print","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/3-540-47721-7_32","article-title":"Two observations on probabilistic primality testing","author":"Beauchemin, Pierre","year":"1987","ISBN":"https:\/\/id.crossref.org\/isbn\/3540180478"},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF00206325","article-title":"The generation of random numbers that are probably prime","volume":"1","author":"Beauchemin, Pierre","year":"1988","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"issue":"203","key":"3","doi-asserted-by":"publisher","first-page":"177","DOI":"10.2307\/2152945","article-title":"Average case error estimates for the strong probable prime test","volume":"61","author":"Damg\u00e5rd, Ivan","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"4","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0304-3975(80)90007-9","article-title":"Evaluation and comparison of two efficient probabilistic primality testing algorithms","volume":"12","author":"Monier, Louis","year":"1980","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"1","key":"5","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","article-title":"Probabilistic algorithm for testing primality","volume":"12","author":"Rabin, Michael O.","year":"1980","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00695-3\/S0025-5718-96-00695-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00695-3\/S0025-5718-96-00695-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:02:34Z","timestamp":1776718954000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00695-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"references-count":5,"journal-issue":{"issue":"213","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["S0025-5718-96-00695-3"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-96-00695-3","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":[[1996]]}}}