10.12 Remarks and exercises

10.12.1 RSA

10.12.2 More complexity classes

10.12.3 Implementing reflections

10.12.4 Grover’s optimality

10.12.5 Picking out a single state

Prove that, for any y\in\{0,1\}^n, \sum_{x\in\{0,1\}^n} (-1)^{x\cdot y} = \begin{cases} 0 &\text{if $y\neq0$;} \\2^n &\text{if $y=0$.} \end{cases}

10.12.6 Writing an integer as a power

1. Show that R=21 cannot be written in the form a^b for integers a\geqslant 1 and b\geqslant 2.
2. Generalise this to a method that could work in \mathcal{O}(L^3) for any value of R that is L bits long.²³⁶

---

236. Hint: since R is L bits long, R<2^L, and so b<L.↩︎