The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
A Fast Monte-Carlo Test for Primality
Abstract
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 < n - 2$, and the Jacobi symbol $\delta = (a /n)$. If $\varepsilon = 6$, decide that n is prime. If either $\gcd (a,n) > 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 $< 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 $< 2^{-m}$(if n is composite) and with multiprecision arithmetic cost $< 6m\log _2 n$.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The art of computer programming. Vol.2: Seminumerical algorithms
Knuth, D. E. (1981) · Virtual Defense Library (Ministerio de Defensa) · Cited by 1,232
Cited by
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
Goldwasser, S., Micali, S., & Rivest, R. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217017 · Cited by 2,804
Universal classes of hash functions
Carter, J. L., & Wegman, M. N. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90044-8 · Cited by 2,519
Expander graphs and their applications
Hoory, S., Linial, N., & Wigderson, A. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01126-8 · Cited by 1,723
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,322
Efficient randomized pattern-matching algorithms
Karp, R. M., & Rabin, M. O. (1987) · IBM Journal of Research and Development · doi:10.1147/rd.312.0249 · Cited by 1,269
Probabilistic algorithms for sparse polynomials
Zippel, R. (1979) · Lecture Notes in Computer Science · doi:10.1007/3-540-09519-5_73 · Cited by 1,101
A Simple Unpredictable Pseudo-Random Number Generator
Blum, L., Blum, M., & Shub, M. (1986) · SIAM Journal on Computing · doi:10.1137/0215025 · Cited by 1,036
Algorithmic Information Theory
Chaitin, G. J. (1977) · IBM Journal of Research and Development · doi:10.1147/rd.214.0350 · Cited by 982
Minimum disclosure proofs of knowledge
Brassard, G., Chaum, D., & Crépeau, C. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90005-0 · Cited by 959
Agrawal, M., Kayal, N., & Saxena, N. (2004) · Annals of Mathematics · doi:10.4007/annals.2004.160.781 · Cited by 931
Probabilistic algorithm for testing primality
Rabin, M. O. (1980) · Journal of Number Theory · doi:10.1016/0022-314x(80)90084-0 · Cited by 863
The NP-completeness column: An ongoing guide
Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 794
Trading group theory for randomness
Babai, L. (1985) · Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 · doi:10.1145/22145.22192 · Cited by 772
Micali, S., Rabin, M., & Vadhan, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814584 · Cited by 716
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992) · Journal of the ACM · doi:10.1145/146585.146605 · Cited by 711
Computational Complexity of Probabilistic Turing Machines
Gill, J. (1977) · SIAM Journal on Computing · doi:10.1137/0206049 · Cited by 689
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
Babai, L., & Moran, S. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90028-1 · Cited by 589
Computationally Private Information Retrieval with Polylogarithmic Communication
Cachin, C., Micali, S., & Stadler, M. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_28 · Cited by 579
Fast probabilistic algorithms for hamiltonian circuits and matchings
Angluin, D., & Valiant, L. G. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90045-x · Cited by 570
A Catalog of Complexity Classes
JOHNSON, D. S. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50007-2 · Cited by 556
Simple Constructions of Almost k‐wise Independent Random Variables
Alon, N., Goldreich, O., Håstad, J., & Peralta, R. (1992) · Random Structures & Algorithms · doi:10.1002/rsa.3240030308 · Cited by 556
Coin flipping by telephone a protocol for solving impossible problems
Blum, M. (1983) · ACM SIGACT News · doi:10.1145/1008908.1008911 · Cited by 518
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · doi:10.21236/ada606588 · Cited by 465
A complexity theoretic approach to randomness
Sipser, M. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808762 · Cited by 460
Blum, M., De Santis, A., Micali, S., & Persiano, G. (1991) · SIAM Journal on Computing · doi:10.1137/0220068 · Cited by 427
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424
Universal classes of hash functions (Extended Abstract)
Carter, J. L., & Wegman, M. N. (1977) · Proceedings of the ninth annual ACM symposium on Theory of computing - STOC '77 · doi:10.1145/800105.803400 · Cited by 350
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
The status of the P versus NP problem
Fortnow, L. (2009) · Communications of the ACM · doi:10.1145/1562164.1562186 · Cited by 321
Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes
Camenisch, J., & Michels, M. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_8 · Cited by 299
Desmedt, Y. G. (1994) · European Transactions on Telecommunications · doi:10.1002/ett.4460050407 · Cited by 292
Generating quasi-random sequences from semi-random sources
Santha, M., & Vazirani, U. V. (1986) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(86)90044-9 · Cited by 256
Metadata
- Authors
- Solovay, R., & Strassen, V.
- Venue
- SIAM Journal on Computing
- Published
- 1977-03
- Volume
- 6
- Issue
- 1
- Pages
- 84-85
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W1964053266
- Cited by
- 635
- References
- 1
- FWCI
- 23.06
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.