Introduction to Cryptography with Coding Theory, 3rd Edition

25.4 Exercises

1. Consider the sequence $2^0\text{,}{2}^1\text{,}{2}^2\text{,}\dots (\text{m}\text{o}\text{d}15)$.

   1. What is the period of this sequence?

   2. Suppose you want to use Shor’s algorithm to factor $n=15.$ What value of $m$ would you take?

   3. Suppose the measurement in Shor’s algorithm yields $c=192$. What value do you obtain for $r$? Does this agree with part (a)?

   4. Use the value of $r$ from part (c) to factor 15.

2. 1. Let $0<s\le m$. Fix an integer $c_0$ with $0\le c_0<2^s$. Show that

      $${\displaystyle \sum _{\begin{array}{c}0\le c<2^m\\ c\equiv c_0(\text{mod}{2}^s)\end{array}}{e}^{\frac{2\pi icx}{2^m}}}=0$$

      if $x\cancel{\equiv }0(\text{mod}{2}^{m-s})$ and $=2^{m-s}{e}^{2\pi ix{c}_0/2^m}$ if $x\equiv 0(\text{m}\text{o}\text{d}{2}^{m-s})$. (Hint: Write $c=c_0+j{2}^s$ with $0\le j<2^{m-s}$, factor $e^{2\pi ix{c}_0/2^m}$ off the sum, and recognize what’s left as a geometric sum.)

   2. Suppose $a_0\text{,}{a}_1\text{,}\dots \text{,}{a}_{2^m-1}$ is a sequence of length $2^m$ such that $a_k=a_{k+j{2}^s}$ for all $j\text{,}k$. Show that the Fourier transform $F(x)$ of this sequence ...