Realistic analysis of some randomized algorithms
The author considers algorithms calling for random numbers which might satisfy a condition with probability 1/2. If the first random number x fails then it is natural to try \(x\to x+1\) until the algorithm succeeds, (or maybe \(x\to \alpha x+\beta).\) We assume these trials to be ``independent, but in many cases there is a proof by the theory of algebraic curves that successive trials effectively have probability (almost) 1/2, by use of algebraic curve theory. For instance, the Cipolla-Lehmer algorithm for finding \(\sqrt{a} mod p\), for a residue a, requires that x be found such that \(x^ 2-4a\) is a nonresidue mod p. The ``bad situation is k successive failures for x, \(x+1,...,x+k-1\). Then the k equations \(Y^ 2_ 1-(X^ 2-4a),...,Y_ k^ 2-((X+k-1)^ 2- 4a)\) represent a space-curve with a point in \({\mathbb{F}}_ p\). This is generally a complete intersection (by independence of the radicals \(Y_ j)\) and there is a classical (Weil) theory for counting such points. The conclusion is that if k has the order of magnitude \((\log_ 2p)/2\) then the probability of failure is O((log p)/\(\sqrt{p})\). A similar analysis is made of the Tonelli-Shanks method for doing the same thing. Other applications including Miller primality tests are given. There is a very useful bibliography.
- 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
- 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?)
- 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
- Primality testing with fewer random bits
- Analysis of a randomized rendezvous algorithm
- Weil bounds for singular curves
- Quasi-random rumor spreading: reducing randomness can be costly
- On the computation of rational points of a hypersurface over a finite field
- On pseudorandomness in families of sequences derived from the Legendre symbol
- A time-randomness tradeoff for quasi-random rumour spreading
- Randomized algorithms in number theory
- 1998 Spring Meeting of the Association for Symbolic Logic
- On some probabilistic aspects around modular methods
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)
