1

This question is related to Shor's algorithm (for quantum computing) and its use of modular exponentiation.

In the table below, the period of the third column is obviously equal to 4. That is, its value repeats every fourth row.

What I am trying to find out is why it is that when the first value in third column is congruent with 1 then the period of the sequence is the corresponding value of 'r'.

I have searched for an answer but have had no luck. The answer is probably related to Fermat's little theorem and yet that seems unrelated (to me).

r -- 2^r -- (2^r) % 15

1 -- 2 -- 2

2 -- 4 -- 4

3 -- 8 -- 8

4 -- 16 -- 1

5 -- 32 -- 2

6 -- 64 -- 4

7 -- 128 -- 8

8 -- 256 -- 1

9 -- 512 -- 2

10 -- 1024 -- 4

11 -- 2048 -- 8

12 -- 4096 -- 1

13 -- 8192 -- 2

Bob Walance
  • 11
  • Hint: start your table one row earlier: when $r=0$, we have $2^r = 1$ which is congruent to $1$ modulo $15$. – Greg Martin Jul 19 '22 at 17:10
  • Every value of $2^r\bmod 15$ is determined by the previous value (just multiply by two and mod by fifteen). So once a value repeats, the whole sequence repeats from that value. Starting from $2^0\equiv 1$, once you get to the next $r$ for which $2^r\equiv 1$, the sequence will repeat from that $r$ the same values it produces starting from $0$. – anon Jul 19 '22 at 18:42
  • I understand now. 4-0=4, 5-1=4 and so on. Thank you, Greg and runway. – Bob Walance Jul 19 '22 at 19:20

0 Answers0