Period finding: Why x^r (mod N) is a periodic function?
up vote
0
down vote
favorite
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.
modular-arithmetic
asked Nov 15 at 17:09
adekate
248
|
show 3 more comments
up vote
0
down vote
favorite
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.
modular-arithmetic
asked Nov 15 at 17:09
adekate
248
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 at 17:11
@robjohn r is any positive integer, N and x are inputs.
– adekate
Nov 15 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 at 17:26
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 at 17:38
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 at 18:06
|
show 3 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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.
modular-arithmetic
asked Nov 15 at 17:09
adekate
248
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.
modular-arithmetic
modular-arithmetic
asked Nov 15 at 17:09
adekate
248
asked Nov 15 at 17:09
adekate
248
edited Nov 15 at 17:20
asked Nov 15 at 17:09
adekate
248
asked Nov 15 at 17:09
adekate
248
asked Nov 15 at 17:09
adekate
248
248
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 at 17:11
@robjohn r is any positive integer, N and x are inputs.
– adekate
Nov 15 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 at 17:26
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 at 17:38
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 at 18:06
|
show 3 more comments
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 at 17:11
@robjohn r is any positive integer, N and x are inputs.
– adekate
Nov 15 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 at 17:26
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 at 17:38
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 at 18:06
1
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 at 17:11
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 at 17:11
@robjohn r is any positive integer, N and x are inputs.
– adekate
Nov 15 at 17:17
@robjohn r is any positive integer, N and x are inputs.
– adekate
Nov 15 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 at 17:26
@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 at 17:26
1
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 at 17:38
@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 at 17:38
1
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 at 18:06
@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 at 18:06
|
show 3 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2999974%2fperiod-finding-why-xr-mod-n-is-a-periodic-function%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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 at 17:11
@robjohn r is any positive integer, N and x are inputs.
– adekate
Nov 15 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 at 17:26
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 at 17:38
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 at 18:06