Realistic analysis of some randomized algorithms

DOI10.1016/0022-0000(91)90038-7MaRDI QIDQ2277019zbMATH OpenOpenAlexFDO

Authors Eric Bach

Publication date 1991

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(91)90038-7

zbMATH Keywords

algorithmscomplexitybibliographyalgebraic curvesrandom numbersCipolla-Lehmer algorithmMiller primality testsTonelli-Shanks method

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Finite ground fields in algebraic geometry (14G15)

Recommendations

• Toward a theory of Pollard's rho method
• Factoring polynomials using fewer random bits
• Primality testing and Abelian varieties over finite fields
• Primality testing with fewer random bits
• scientific article; zbMATH DE number 1303185

Cites work

• scientific article; zbMATH DE number 4014840 (Why is no real title available?)
• scientific article; zbMATH DE number 3855273 (Why is no real title available?)
• scientific article; zbMATH DE number 3912454 (Why is no real title available?)
• scientific article; zbMATH DE number 3177790 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3480679 (Why is no real title available?)
• scientific article; zbMATH DE number 3479047 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 3225125 (Why is no real title available?)
• scientific article; zbMATH DE number 3228666 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A Simple Unpredictable Pseudo-Random Number Generator
• Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
• Equations over finite fields. An elementary approach
• Estimation de la fonction de Tchebychef θ sur le k-ième nombre premier et grandes valeurs de la fonction ω(n) nombre de diviseurs premiers de n
• Evaluation and comparison of two efficient probabilistic primality testing algorithms
• Expanders, randomness, or time versus space
• Factoring integers with elliptic curves
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Multidimensional numerical integration using pseudorandom numbers
• On the power of two-point based sampling
• On using deterministic functions to reduce randomness in probabilistic algorithms
• Probabilistic algorithm for testing primality
• Provably good pattern generators for a random pattern test
• Riemann's hypothesis and tests for primality
• Some properties of the cyclotomic polynomial

Cited in

(10)

• Randomized algorithms in number theory
• Analysis of a randomized rendezvous algorithm
• Quasi-random rumor spreading: reducing randomness can be costly
• 1998 Spring Meeting of the Association for Symbolic Logic
• Primality testing with fewer random bits
• On some probabilistic aspects around modular methods
• On pseudorandomness in families of sequences derived from the Legendre symbol
• Weil bounds for singular curves
• A time-randomness tradeoff for quasi-random rumour spreading
• On the computation of rational points of a hypersurface over a finite field

This page was built for publication: Realistic analysis of some randomized algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277019)