  We give a quantum algorithm for solving a shifted multiplicative character
problem over Z/nZ and finite fields. We show that the algorithm can be
interpreted as a matrix factorization or as solving a deconvolution problem and
give sufficient conditions for a shift problem to be solved efficiently by our
algorithm. We also show that combining the shift problem with the hidden
subgroup problem results in a hidden coset problem. This naturally captures the
redundancy in the shift due to the periodic structure of multiplicative
characters over Z/nZ.
