Discrete logarithm for a range
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Are there any efficient algorithms for solving the following problem?
Let $b leq m < n$, what is the smallest value for $k geq 1$ such that $m^k$ mod $n$ is in the range $[0,b)$.
A variant on this which would also be of interest is what is the smallest value for $k$ such that $mx^k$ mod $n$ is in the range $[0,b)$ for a given $x$ (for general values of $x$ or for specific values or having a specific property).
discrete-logarithms
add a comment |Â
up vote
0
down vote
favorite
Are there any efficient algorithms for solving the following problem?
Let $b leq m < n$, what is the smallest value for $k geq 1$ such that $m^k$ mod $n$ is in the range $[0,b)$.
A variant on this which would also be of interest is what is the smallest value for $k$ such that $mx^k$ mod $n$ is in the range $[0,b)$ for a given $x$ (for general values of $x$ or for specific values or having a specific property).
discrete-logarithms
You can always take $k=0$ for $m>1.$
â gammatester
Sep 5 at 13:46
I will add on $k geq 1$ to the problem definition.
â MotiN
Sep 5 at 14:11
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Are there any efficient algorithms for solving the following problem?
Let $b leq m < n$, what is the smallest value for $k geq 1$ such that $m^k$ mod $n$ is in the range $[0,b)$.
A variant on this which would also be of interest is what is the smallest value for $k$ such that $mx^k$ mod $n$ is in the range $[0,b)$ for a given $x$ (for general values of $x$ or for specific values or having a specific property).
discrete-logarithms
Are there any efficient algorithms for solving the following problem?
Let $b leq m < n$, what is the smallest value for $k geq 1$ such that $m^k$ mod $n$ is in the range $[0,b)$.
A variant on this which would also be of interest is what is the smallest value for $k$ such that $mx^k$ mod $n$ is in the range $[0,b)$ for a given $x$ (for general values of $x$ or for specific values or having a specific property).
discrete-logarithms
discrete-logarithms
edited Sep 5 at 14:11
asked Sep 5 at 9:43
MotiN
17510
17510
You can always take $k=0$ for $m>1.$
â gammatester
Sep 5 at 13:46
I will add on $k geq 1$ to the problem definition.
â MotiN
Sep 5 at 14:11
add a comment |Â
You can always take $k=0$ for $m>1.$
â gammatester
Sep 5 at 13:46
I will add on $k geq 1$ to the problem definition.
â MotiN
Sep 5 at 14:11
You can always take $k=0$ for $m>1.$
â gammatester
Sep 5 at 13:46
You can always take $k=0$ for $m>1.$
â gammatester
Sep 5 at 13:46
I will add on $k geq 1$ to the problem definition.
â MotiN
Sep 5 at 14:11
I will add on $k geq 1$ to the problem definition.
â MotiN
Sep 5 at 14:11
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2906080%2fdiscrete-logarithm-for-a-range%23new-answer', 'question_page');
);
Post as a guest
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
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
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
You can always take $k=0$ for $m>1.$
â gammatester
Sep 5 at 13:46
I will add on $k geq 1$ to the problem definition.
â MotiN
Sep 5 at 14:11