  We give an algorithm for the hidden subgroup problem for the dihedral group
$D_N$, or equivalently the cyclic hidden shift problem, that supersedes our
first algorithm and is suggested by Regev's algorithm. It runs in
$\exp(O(\sqrt{\log N}))$ quantum time and uses $\exp(O(\sqrt{\log N}))$
classical space, but only $O(\log N)$ quantum space. The algorithm also runs
faster with quantumly addressable classical space than with fully classical
space. In the hidden shift form, which is more natural for this algorithm
regardless, it can also make use of multiple hidden shifts. It can also be
extended with two parameters that trade classical space and classical time for
quantum time. At the extreme space-saving end, the algorithm becomes Regev's
algorithm. At the other end, if the algorithm is allowed classical memory with
quantum random access, then many trade-offs between classical and quantum time
are possible.
