Probabilistic algorithm for testing primality
From MaRDI portal
Publication:1135871
DOI10.1016/0022-314X(80)90084-0zbMath0426.10006WikidataQ21950792 ScholiaQ21950792MaRDI QIDQ1135871
Publication date: 1980
Published in: Journal of Number Theory (Search for Journal in Brave)
Related Items
From Monte Carlo to quantum computation, Randomized algorithms in combinatorial optimization: A survey, A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers, GCD calculation in the search task of pseudoprime and strong pseudoprime numbers, Improvements to RSA key generation and CRT on embedded devices, A simple approach for generating RSA keys, Generating quasi-random sequences from semi-random sources, Reductions among number theoretic problems, Primes in quadratic unique factorization domains, Compositeness test with nodal curves, Improved error bounds for the Fermat primality test on random inputs, Fast generation of prime numbers and secure public-key cryptographic parameters., Optimal ancilla-free Pauli+V circuits for axial rotations, Computation of prime numbers by using a probabilistic algorithm, A deterministic algorithm for the discrete logarithm problem in a semigroup, A connection between random variables and latin \(k\)-cubes, Strong pseudoprimes to the first eight prime bases, Probabilistic quantifiers and games, The generation of random numbers that are probably prime, On the oracle complexity of factoring integers, Simple Constructions of Almost k-wise Independent Random Variables, The Probability that a Random Probable Prime is Composite, Simulating BPP using a general weak random source, All congruences below stability-preserving fair testing or CFFD, Machines that perform measurements, Algorithmic theory of free solvable groups: randomized computations., Strong pseudoprimes to twelve prime bases, On the distribution of Atkin and Elkies primes, A signature scheme from the finite field isomorphism problem, Algorithms for the Multiplication Table Problem, Efficient RSA key generation and threshold Paillier in the two-party setting, On testing for zero polynomials by a set of points with bounded precision., Equality in computer algebra and beyond., Expander graphs and their applications, On completely factoring any integer efficiently in a single run of an order-finding algorithm, Classifying the computational complexity of problems, A new probabilistic primality test, Groups of prime degree and the Bateman-Horn conjecture, A generalization of Miller’s primality theorem, An intelligent choice of witnesses in the Miller-Rabin primality test. Reinforcement learning approach, Recent developments in primality testing, Finding strong pseudoprimes to several bases, Frobenius pseudoprimes, On practical aspects of the Miller-Rabin primality test, The influence of computers in the development of number theory, Efficient multiple-precision integer division algorithm, Knottedness is in NP, modulo GRH, Primality testing and factoring, An appraisal of computational complexity for operations researchers, Determining periodicity: a case study of a functional specification, On a problem posed by Steve Smale, Constructive complexity, Statistical Evidence for Small Generating Sets, The Factorization of the Ninth Fermat Number, A heuristic irreducibility test for univariate polynomials, The Miller–Rabin test with randomized exponents, A monad for randomized algorithms, Resilient dynamic programming, The error probability of the Miller-Rabin primality test, Scheduling with neural networks -- the case of the Hubble Space Telescope, Pseudorandom generators for space-bounded computation, On the effectiveness of a generalization of Miller's primality theorem, A deterministic version of Pollard’s $p-1$ algorithm, Two kinds of strong pseudoprimes up to $10^{36}$, Complexity classes of equivalence problems revisited, Integer factoring and compositeness witnesses, Finding strong pseudoprimes to several bases. II, Realistic analysis of some randomized algorithms, A framework for deterministic primality proving using elliptic curves with complex multiplication, Rabin-Miller Primality Test: Composite Numbers Which Pass It, An unconditional improvement to the running time of the quadratic Frobenius test, Fault Attacks on RSA Public Keys: Left-To-Right Implementations Are Also Vulnerable, Quantum algorithms for algebraic problems, Information and computation: Classical and quantum aspects, Smale’s 17th problem: Average polynomial time to compute affine and projective solutions, Realizing Hash-and-Sign Signatures under Standard Assumptions, Construction of strong elliptic curves suitable for cryptographic applications, On Constructing 1-1 One-Way Functions, A note on Rabin's probabilistic primality test, Prime-number algorithm for public-key systems, A probable prime test with high confidence, $$P\mathop{ =}\limits^{?}NP$$, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, On the number of primality witnesses of composite integers, Efficient, Robust and Constant-Round Distributed RSA Key Generation, Primality tests, linear recurrent sequences and the Pell equation, A probabilistic algorithm for updating files over a communication link, Computing (and Life) Is All about Tradeoffs, Generalized strong pseudoprime tests and applications, On the Number of Elliptic Pseudoprimes, Note on class number parity of an abelian field of prime conductor, The Rabin-Monier theorem for Lucas pseudoprimes, Strong pseudoprimes to base 2, Universal tests for nonuniform distributions, Algebraic algorithms in GF(q), Identifying half-twists using randomized algorithm methods., Infinite Sets of Primes with Fast Primality Tests and Quick Generation of Large Primes, A new primality test for natural integers, Primality testing with fewer random bits, A one-parameter quadratic-base version of the Baillie-PSW probable prime test, Hidden multiscale order in the primes, RECYCLING RANDOM BITS IN PARALLEL, The geometry of Bayesian programming, Indivisibility of the class number of a real abelian field of prime conductor, On a modification of the Lucas primality test, Certifying giant nonprimes, Breaking SIDH in polynomial time, Locally verifiable signature and key aggregation, 1994–1995 Winter Meeting of the Association for Symbolic Logic, \textsc{Rings}: an efficient Java/Scala library for polynomial rings, Interactions of computational complexity theory and mathematics, Computing Elliptic Curves over $$\mathbb{Q}$$ : Bad Reduction at One Prime, Computing elliptic curves over $\mathbb {Q}$, Further investigations with the strong probable prime test, A quantum differentiation ofk-SAT instances, The structure factor of primes, Notes on some new kinds of pseudoprimes, Detecting dynamical changes in time series by using the Jensen Shannon divergence, Finding 𝐶₃-strong pseudoprimes, First direct implementation of a true random source on programmable hardware, A lower bound for primality, The computational complexity of recognizing permutation functions, Multiparty generation of an RSA modulus, Strengthening the Baillie-PSW primality test, Computers as a Source of A Posteriori Knowledge in Mathematics, Idempotent Factorizations in the Cryptography Classroom, Multiparty generation of an RSA modulus
Cites Work
