A Fast Monte-Carlo Test for Primality
From MaRDI portal
Publication:4113883
DOI10.1137/0206006zbMath0345.10002WikidataQ56446479 ScholiaQ56446479MaRDI QIDQ4113883
Robert M. Solovay, Volker Strassen
Publication date: 1977
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0206006
Related Items
Some Observations on Primality Testing, Determining periodicity: a case study of a functional specification, Factoring polynomials over finite fields: A survey, Primality testing, A lower bound for primality, The computational complexity of recognizing permutation functions, A probabilistic lower bound for checking disjointness of sets, Probabilistic Turing machines and recursively enumerable Dedekind cuts, Efficient, perfect polynomial random number generators, Irreducibility of multivariate polynomials, Generating quasi-random sequences from semi-random sources, Approximation to measurable functions and its relation to probabilistic computation, On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes, A nonlinear public key cryptosystem, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, Minimum disclosure proofs of knowledge, The generation of random permutations on the fly, Probabilistic quantifiers and games, The generation of random numbers that are probably prime, Fast verification, testing, and generation of large primes, Probabilistic algorithm for testing primality, Fast probabilistic algorithms for Hamiltonian circuits and matchings, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Non deterministic polynomial optimization problems and their approximations, Discrete extremal problems, Semantics of probabilistic programs, Recent developments in primality testing, Some observations on the probabilistic algorithms and NP-hard problems, An introduction to randomized algorithms, A heuristic irreducibility test for univariate polynomials, Nested annealing: A provable improvement to simulated annealing, Scheduling with neural networks -- the case of the Hubble Space Telescope, A note on Rabin's nearest-neighbor algorithm, Universal classes of hash functions, Primality testing with fewer random bits, Verification of the Miller-Rabin probabilistic primality test., On testing for zero polynomials by a set of points with bounded precision., Dynamical analysis of a class of Euclidean algorithms., A probabilistic algorithm for updating files over a communication link, Generalized strong pseudoprime tests and applications, Predicting zero coefficients in formal power series computations., Computational complexity of uniform quantum circuit families and quantum Turing machines, Estimation of singular values of very large matrices using random sampling, Randomised algorithms, The time-precision tradeoff problem on on-line probabilistic Turing machines, One complexity theorist's view of quantum computing, From Monte Carlo to quantum computation, Fast generation of prime numbers and secure public-key cryptographic parameters., A connection between random variables and latin \(k\)-cubes, Homomorphic public-key cryptosystems and encrypting Boolean circuits, Error-bounded probabilistic computations between MA and AM, WHAT IS QUANTUM COMPUTATION?, A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields, A relation between correctness and randomness in the computation of probabilistic algorithms, Expander graphs and their applications, A generalization of Miller’s primality theorem, Explicit Bounds for Primality Testing and Related Problems, Classifying the computational complexity of problems, Some remarks concerning the M.I.T. public-key cryptosystem, An improved Monte Carlo factorization algorithm, A note on Rabin's probabilistic primality test, Asymptotically Fast Factorization of Integers
