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 (83)
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 Number of False Witnesses for a Composite Number ⋮ 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 ⋮ How real is incomputability in physics? ⋮ On types of elliptic pseudoprimes ⋮ An improved Monte Carlo factorization algorithm ⋮ A note on Rabin's nearest-neighbor algorithm ⋮ Polynomial algorithms for primality testing in algebraic number fieldswith class number 1 ⋮ 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
This page was built for publication: A Fast Monte-Carlo Test for Primality
