A Fast Monte-Carlo Test for Primality
From MaRDI portal
Publication:4113883
DOI10.1137/0206006zbMath0345.10002OpenAlexW1964053266WikidataQ56446479 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
Estimation of singular values of very large matrices using random sampling, From Monte Carlo to quantum computation, Random sampling in computational algebra: Helly numbers and violator spaces, Irreducibility of multivariate polynomials, Generating quasi-random sequences from semi-random sources, Approximation to measurable functions and its relation to probabilistic computation, Some Observations on Primality Testing, On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes, Fast generation of prime numbers and secure public-key cryptographic parameters., A nonlinear public key cryptosystem, A connection between random variables and latin \(k\)-cubes, 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, Asymptotically Fast Factorization of Integers, Fast verification, testing, and generation of large primes, Probabilistic algorithm for testing primality, Algorithmic theory of free solvable groups: randomized computations., Certifying giant nonprimes, Fast probabilistic algorithms for Hamiltonian circuits and matchings, Inexactness and a future of computing, Locally verifiable signature and key aggregation, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Verification of the Miller-Rabin probabilistic primality test., Learning a performance metric of Buchberger's algorithm, On testing for zero polynomials by a set of points with bounded precision., Dynamical analysis of a class of Euclidean algorithms., Expander graphs and their applications, Interactions of computational complexity theory and mathematics, Non deterministic polynomial optimization problems and their approximations, Discrete extremal problems, Homomorphic public-key cryptosystems and encrypting Boolean circuits, Classifying the computational complexity of problems, A new probabilistic primality test, A generalization of Miller’s primality theorem, Semantics of probabilistic programs, Recent developments in primality testing, Some observations on the probabilistic algorithms and NP-hard problems, Determining periodicity: a case study of a functional specification, On a problem posed by Steve Smale, An introduction to randomized algorithms, A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields, A heuristic irreducibility test for univariate polynomials, A monad for randomized algorithms, Nested annealing: A provable improvement to simulated annealing, The error probability of the Miller-Rabin primality test, Scheduling with neural networks -- the case of the Hubble Space Telescope, Factoring polynomials over finite fields: A survey, Primality testing, WHAT IS QUANTUM COMPUTATION?, Some remarks concerning the M.I.T. public-key cryptosystem, A lower bound for primality, A relation between correctness and randomness in the computation of probabilistic algorithms, Complexity classes of equivalence problems revisited, Error-bounded probabilistic computations between MA and AM, The computational complexity of recognizing permutation functions, Explicit Bounds for Primality Testing and Related Problems, An improved Monte Carlo factorization algorithm, A note on Rabin's nearest-neighbor algorithm, Smale’s 17th problem: Average polynomial time to compute affine and projective solutions, Universal classes of hash functions, On Constructing 1-1 One-Way Functions, A note on Rabin's probabilistic primality test, $$P\mathop{ =}\limits^{?}NP$$, Encryption Switching Protocols, A probabilistic algorithm for updating files over a communication link, Randomised algorithms, The time-precision tradeoff problem on on-line probabilistic Turing machines, Generalized strong pseudoprime tests and applications, Book Review: Inevitable randomness in discrete mathematics, A probabilistic lower bound for checking disjointness of sets, Probabilistic Turing machines and recursively enumerable Dedekind cuts, Predicting zero coefficients in formal power series computations., Efficient, perfect polynomial random number generators, Computational complexity of uniform quantum circuit families and quantum Turing machines, Primality testing with fewer random bits, One complexity theorist's view of quantum computing
