61 citations · 445 across the 59 of their papers we have counts for
23 papers · 1 filter
An O(M(n) log n) algorithm for the Jacobi symbol
Richard P. Brent, Paul Zimmermann
The best known algorithm to compute the Jacobi symbol of two n-bit integers runs in time O(M(n) log n), using Schönhage's fast continued fraction algorithm combined with an identit…
Multiple-precision zero-finding methods and the complexity of elementary function evaluation
Richard P. Brent
We consider methods for finding high-precision approximations to simple zeros of smooth functions. As an application, we give fast methods for evaluating the elementary functions l…
Some comments on C. S. Wallace's random number generators
Richard P. Brent
We outline some of Chris Wallace's contributions to pseudo-random number generation. In particular, we consider his idea for generating normally distributed variates without relyin…
The great trinomial hunt
Richard P. Brent, Paul Zimmermann
We describe a search for primitive trinomials of high degree and its interaction with the Great Internet Mersenne prime search (GIMPS). The search is complete for trinomials whose…
The myth of equidistribution for high-dimensional simulation
Richard P. Brent
A pseudo-random number generator (RNG) might be used to generate w-bit random samples in d dimensions if the number of state bits is at least dw. Some RNGs perform better than othe…
A Simple Approach to Error Reconciliation in Quantum Key Distribution
Richard P. Brent
We discuss the error reconciliation phase in quantum key distribution (QKD) and analyse a simple scheme in which blocks with bad parity (that is, blocks containing an odd number of…