Realistic analysis of some randomized algorithms

DOI10.1016/0022-0000(91)90038-7zbMATH Open0724.11069OpenAlexW1985217658MaRDI QIDQ2277019FDOQ2277019

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

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

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)

Cites Work

• Title not available (Why is that?)
• Factoring integers with elliptic curves
• Title not available (Why is that?)
• Probabilistic algorithm for testing primality
• Riemann's hypothesis and tests for primality
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
• Title not available (Why is that?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Equations over finite fields. An elementary approach
• A Simple Unpredictable Pseudo-Random Number Generator
• On the power of two-point based sampling
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some properties of the cyclotomic polynomial
• Multidimensional numerical integration using pseudorandom numbers
• Title not available (Why is that?)
• Evaluation and comparison of two efficient probabilistic primality testing algorithms
• Title not available (Why is that?)
• On using deterministic functions to reduce randomness in probabilistic algorithms
• Expanders, randomness, or time versus space
• Title not available (Why is that?)
• Provably good pattern generators for a random pattern test

Cited In (10)

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

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)