  In this paper we make a step towards a time and space efficient algorithm for
the hidden shift problem for groups of the form $\mathbb{Z}_k^n$. We give a
solution to the case when $k$ is a power of 2, which has polynomial running
time in $n$, and only uses quadratic classical, and linear quantum space in
$n\log (k)$. It can be a useful tool in the general case of the hidden shift
and hidden subgroup problems too, since one of the main algorithms made to
solve them can use this algorithm as a subroutine in its recursive steps,
making it more efficient in some instances.
