{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:45:35Z","timestamp":1787388335431,"version":"build-2736575974"},"reference-count":3,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1977,3]]},"abstract":"<jats:p>Let n be an odd integer. Take a random number a from a uniform distribution on the set $\\{1, 2,\\cdots, n -1\\}$. If a and n are relatively prime, compute the residue $\\varepsilon \\equiv a^{(n - 1)\/2}(\\bmod n)$, where $ - 1 \\leqq \\varepsilon &lt; n - 2$, and the Jacobi symbol $\\delta = (a \/n)$. If $\\varepsilon = 6$, decide that n is prime. If either $\\gcd (a,n) &gt; 1$ or $\\varepsilon \\ne \\delta $ decide that n is composite. Obviously, if n is prime, the decision made will be correct. We will show below, that for composite n the probability of an incorrect decision is $\\leqq 1 \/ 2$. The number of multiprecision operations needed for the whole procedure is $&lt; 6\\log _2 n$. m-fold repetition using independent random numbers yields a Monte-Carlo test for primality with error probabilities 0 (if n is prime) and $&lt; 2^{-m}$(if n is composite) and with multiprecision arithmetic cost $&lt; 6m\\log _2 n$.<\/jats:p>","DOI":"10.1137\/0206006","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T05:59:55Z","timestamp":1109224795000},"page":"84-85","source":"Crossref","is-referenced-by-count":390,"title":["A Fast Monte-Carlo Test for Primality"],"prefix":"10.1137","volume":"6","author":[{"given":"R.","family":"Solovay","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"V.","family":"Strassen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"The art of computer programming. Vol. 2: Seminumerical algorithms","author":"Knuth Donald E.","year":"1969"},{"key":"R2","volume-title":"An introduction to the theory of numbers","author":"Niven Ivan","year":"1966"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.2307\/2307640"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0206006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:22Z","timestamp":1787337262000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0206006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977,3]]},"references-count":3,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1977,3]]}},"alternative-id":["10.1137\/0206006"],"URL":"https:\/\/doi.org\/10.1137\/0206006","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1977,3]]}}}