I was an idiot and was thinking that a small base didn't matter
because the exponentiation would quickly make the number the same size
as the modulus. But, of course, the small base continues to make
multiplications unrealistically cheap throughout the computation.

R=golang-dev, r
CC=golang-dev
https://golang.org/cl/6649048