  This work presents a new, simple O(log^2|G|) algorithm, the Fibonacci cube
algorithm, for producing random group elements in black box groups. After the
initial O(log^2|G|) group operations, epsilon-uniform random elements are
produced using O((log 1/epsilon)log|G|) operations each. This is the first
major advance over the ten year old result of Babai [Babai91], which had
required O(log^5|G|) group operations. Preliminary experimental results show
the Fibonacci cube algorithm to be competitive with the product replacement
algorithm.
  The new result leads to an amusing reversal of the state of affairs for
permutation group algorithms. In the past, the fastest random generation for
permutation groups was achieved as an application of permutation group
membership algorithms and used deep knowledge about permutation
representations. The new black box random generation algorithm is also valid
for permutation groups, while using no knowledge that is specific to
permutation representations. As an application, we demonstrate a new algorithm
for permutation group membership that is asymptotically faster than all
previously known algorithms.
