  We use lookup tables to design faster algorithms for important algebraic
problems over finite fields. These faster algorithms, which only use arithmetic
operations and lookup table operations, may help to explain the difficulty of
determining the complexities of these important problems. Our results over a
constant-sized finite field are as follows.
  The Walsh-Hadamard transform of a vector of length $N$ can be computed using
$O(N \log N / \log \log N)$ bit operations. This generalizes to any transform
defined as a Kronecker power of a fixed matrix. By comparison, the Fast
Walsh-Hadamard transform (similar to the Fast Fourier transform) uses $O(N \log
N)$ arithmetic operations, which is believed to be optimal up to constant
factors.
  Any algebraic algorithm for multiplying two $N \times N$ matrices using
$O(N^\omega)$ operations can be converted into an algorithm using $O(N^\omega /
(\log N)^{\omega/2 - 1})$ bit operations. For example, Strassen's algorithm can
be converted into an algorithm using $O(N^{2.81} / (\log N)^{0.4})$ bit
operations. It remains an open problem with practical implications to determine
the smallest constant $c$ such that Strassen's algorithm can be implemented to
use $c \cdot N^{2.81} + o(N^{2.81})$ arithmetic operations; using a lookup
table allows one to save a super-constant factor in bit operations.
