1

If I take an example, I can observe that it is the case, but I am not able to understand why an exponentially rising function x^r would hit say x^r (mod N) periodically.

r is a variable here, and x and N are given inputs.

Example: N = 21, x = 2, then period is 6.

2^6(mod21) = 1, 2^12(mod21) = 1.

shul
  • 109
  • 9
  • 1
    How many values can $x^r$ take mod $N$? At some point, it has to get back to some place it was previously. – robjohn Nov 15 '18 at 17:11
  • @robjohn r is any positive integer, N and x are inputs. – shul Nov 15 '18 at 17:17
  • @adekate: Yes. $2^r$ can take at most $21$ values $\bmod{21}$. That means that given $22$ values of $r$, $2^r$ must equal some earlier $2^{r-p}$ $\bmod{21}$. – robjohn Nov 15 '18 at 17:26
  • OK, I misunderstood. In your example, the period is $6$ because $2^6\equiv1\pmod{21}$ – saulspatz Nov 15 '18 at 17:31
  • @robjohn How do you say that 2^r mod21 can take at most 21 values? As its period is 6, I think it can at most take 6 values. – shul Nov 15 '18 at 17:36
  • 1
    @adekate: it can take at most $21$ values since there are only $21$ distinct residue classes mod $21$. As it turns out there are fewer before $2^r$ actually repeats, but the fact that there are only $21$ residue classes, puts an upper limit on things (see Pigeonhole Principle). – robjohn Nov 15 '18 at 17:38
  • @robjohn I can visualize for m(modN), m being any positive integer, that it has 21 residue class and period 21. But my concern is how x^r hits only the possible 6 classes and that to periodically, it is an exponential function. – shul Nov 15 '18 at 17:59
  • 1
    @adekate: the multiplicative group mod $21$ has $12$ elements, so it turns out that the period of any element mod $21$ will divide $12$. To find out the period of a particular element, one usually has to check that element. Note that $6^r$ has period $2$ and $4^r$ has period $3$. – robjohn Nov 15 '18 at 18:06

0 Answers0