Mixing
Distinguishing between the square roots of a quadratic residue
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
For a prime $p$, given $g$, $x = g^2rpmod p$, and $y$ such that $y^2 equiv x pmod p$, is it possible to determine if $y equiv g^r pmod p$ without calculating the discrete logarithm? Comparing numbers by size doesn't seem to help.
For example, with $p = 107$, $g = 2$, and $x = 2^92 equiv 33 pmod 107$, the square roots are $56$ and $51 mod p$. Is there a way to determine that $56 equiv 2^46$ just from the values of $p,g,x$ without computing/knowing r?
EDIT: Could this be possible if r is restricted to some range? like $0leq r < frac p2$ or $frac p2 leq r < p$? Thanks!
number-theory modular-arithmetic
asked Jul 31 at 12:30
Robert Smiths
544
add a comment |Â
up vote
4
down vote
favorite
For a prime $p$, given $g$, $x = g^2rpmod p$, and $y$ such that $y^2 equiv x pmod p$, is it possible to determine if $y equiv g^r pmod p$ without calculating the discrete logarithm? Comparing numbers by size doesn't seem to help.
For example, with $p = 107$, $g = 2$, and $x = 2^92 equiv 33 pmod 107$, the square roots are $56$ and $51 mod p$. Is there a way to determine that $56 equiv 2^46$ just from the values of $p,g,x$ without computing/knowing r?
EDIT: Could this be possible if r is restricted to some range? like $0leq r < frac p2$ or $frac p2 leq r < p$? Thanks!
number-theory modular-arithmetic
asked Jul 31 at 12:30
Robert Smiths
544
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
For a prime $p$, given $g$, $x = g^2rpmod p$, and $y$ such that $y^2 equiv x pmod p$, is it possible to determine if $y equiv g^r pmod p$ without calculating the discrete logarithm? Comparing numbers by size doesn't seem to help.
For example, with $p = 107$, $g = 2$, and $x = 2^92 equiv 33 pmod 107$, the square roots are $56$ and $51 mod p$. Is there a way to determine that $56 equiv 2^46$ just from the values of $p,g,x$ without computing/knowing r?
EDIT: Could this be possible if r is restricted to some range? like $0leq r < frac p2$ or $frac p2 leq r < p$? Thanks!
number-theory modular-arithmetic
asked Jul 31 at 12:30
Robert Smiths
544
For a prime $p$, given $g$, $x = g^2rpmod p$, and $y$ such that $y^2 equiv x pmod p$, is it possible to determine if $y equiv g^r pmod p$ without calculating the discrete logarithm? Comparing numbers by size doesn't seem to help.
For example, with $p = 107$, $g = 2$, and $x = 2^92 equiv 33 pmod 107$, the square roots are $56$ and $51 mod p$. Is there a way to determine that $56 equiv 2^46$ just from the values of $p,g,x$ without computing/knowing r?
EDIT: Could this be possible if r is restricted to some range? like $0leq r < frac p2$ or $frac p2 leq r < p$? Thanks!
number-theory modular-arithmetic
asked Jul 31 at 12:30
Robert Smiths
544
edited Aug 1 at 1:12
asked Jul 31 at 12:30
Robert Smiths
544
asked Jul 31 at 12:30
Robert Smiths
544
asked Jul 31 at 12:30
Robert Smiths
544
544
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
No. Suppose that you can find "true" (with respect to $g$) square root in $T(p)$ time (denote "true" square root of $x$ as $f_g (x)$). Then you can find discrete logarithm (for simplicity, let it take values $1, 2, ldots, p - 1$ instead of usual choice $0, 1, ldots, p - 2$) of any non-zero remainder modulo $p$ in $O(T(p) mathrmpoly(log p))$ time:
$log_g x = begincases 1 &mbox if $x = g$ \ 2 log_g f_g(x) &mbox if $x$ is a quadratic residue \
2 log_g f_g(gx) - 1 &mbox if $x$ is a quadratic non-residue and is not equal to $g$ endcases$.
Notice that $log_g f_g (x) = dfraclog_g x2$ and $log_g f_g(gx) = dfraclog_g x + 12$, so computation of $log_g x$ using this recursive formula halts in $O(log p)$ iterations. Also, making each recursive call takes
$O(mathrmpoly(log p))$ time.
(Checking whether number is quadratic residue or not can be easily done in $O(mathrmpoly(log p))$ time, for example one may calculate $x^(p-1)/2 !!! mod ! p$ and check whether it is $1$ or $-1$).
answered Jul 31 at 23:16
Kaban-5
463
add a comment |Â
up vote
5
down vote
(I'm assuming $p$ is odd)
No; the answer to your question depends crucially on what you have chosen for $r$.
In your example you took $r = 46$ so that $y=56$ was the right answer, but you could just as easily have taken $r = 99$ instead, which would make $y=51$ the right answer. You could also have chosen $r=152$, but that gives the same result as $r=46$.
If you want to do something like restrict $r$ to the range $0 < r < fracp2$, I strongly disbelieve there is a general way to distinguish which of the two square you're asking for without basically computing $r$.
answered Jul 31 at 12:40
Hurkyl
107k9112253
Just confirming, if I restrict $r$, you disbelieve there is a general way?
– Robert Smiths
Jul 31 at 19:15
add a comment |Â
up vote
3
down vote
If $y^2 equiv (g^r)^2 pmod p$ then $y equiv pm g^r pmod p$, because $Bbb Z/pBbb Z$ is a field.
answered Jul 31 at 12:38
Kenny Lau
17.7k2156
(-1) although this is true, it doesn't really answer the question and should be a comment. There isn't even a clear evidence that the OP wasn't aware of that.
– Arnaud Mortier
Jul 31 at 23:24
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
No. Suppose that you can find "true" (with respect to $g$) square root in $T(p)$ time (denote "true" square root of $x$ as $f_g (x)$). Then you can find discrete logarithm (for simplicity, let it take values $1, 2, ldots, p - 1$ instead of usual choice $0, 1, ldots, p - 2$) of any non-zero remainder modulo $p$ in $O(T(p) mathrmpoly(log p))$ time:
$log_g x = begincases 1 &mbox if $x = g$ \ 2 log_g f_g(x) &mbox if $x$ is a quadratic residue \
2 log_g f_g(gx) - 1 &mbox if $x$ is a quadratic non-residue and is not equal to $g$ endcases$.
Notice that $log_g f_g (x) = dfraclog_g x2$ and $log_g f_g(gx) = dfraclog_g x + 12$, so computation of $log_g x$ using this recursive formula halts in $O(log p)$ iterations. Also, making each recursive call takes
$O(mathrmpoly(log p))$ time.
(Checking whether number is quadratic residue or not can be easily done in $O(mathrmpoly(log p))$ time, for example one may calculate $x^(p-1)/2 !!! mod ! p$ and check whether it is $1$ or $-1$).
answered Jul 31 at 23:16
Kaban-5
463
add a comment |Â
up vote
3
down vote
accepted
No. Suppose that you can find "true" (with respect to $g$) square root in $T(p)$ time (denote "true" square root of $x$ as $f_g (x)$). Then you can find discrete logarithm (for simplicity, let it take values $1, 2, ldots, p - 1$ instead of usual choice $0, 1, ldots, p - 2$) of any non-zero remainder modulo $p$ in $O(T(p) mathrmpoly(log p))$ time:
$log_g x = begincases 1 &mbox if $x = g$ \ 2 log_g f_g(x) &mbox if $x$ is a quadratic residue \
2 log_g f_g(gx) - 1 &mbox if $x$ is a quadratic non-residue and is not equal to $g$ endcases$.
Notice that $log_g f_g (x) = dfraclog_g x2$ and $log_g f_g(gx) = dfraclog_g x + 12$, so computation of $log_g x$ using this recursive formula halts in $O(log p)$ iterations. Also, making each recursive call takes
$O(mathrmpoly(log p))$ time.
(Checking whether number is quadratic residue or not can be easily done in $O(mathrmpoly(log p))$ time, for example one may calculate $x^(p-1)/2 !!! mod ! p$ and check whether it is $1$ or $-1$).
answered Jul 31 at 23:16
Kaban-5
463
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
No. Suppose that you can find "true" (with respect to $g$) square root in $T(p)$ time (denote "true" square root of $x$ as $f_g (x)$). Then you can find discrete logarithm (for simplicity, let it take values $1, 2, ldots, p - 1$ instead of usual choice $0, 1, ldots, p - 2$) of any non-zero remainder modulo $p$ in $O(T(p) mathrmpoly(log p))$ time:
$log_g x = begincases 1 &mbox if $x = g$ \ 2 log_g f_g(x) &mbox if $x$ is a quadratic residue \
2 log_g f_g(gx) - 1 &mbox if $x$ is a quadratic non-residue and is not equal to $g$ endcases$.
Notice that $log_g f_g (x) = dfraclog_g x2$ and $log_g f_g(gx) = dfraclog_g x + 12$, so computation of $log_g x$ using this recursive formula halts in $O(log p)$ iterations. Also, making each recursive call takes
$O(mathrmpoly(log p))$ time.
(Checking whether number is quadratic residue or not can be easily done in $O(mathrmpoly(log p))$ time, for example one may calculate $x^(p-1)/2 !!! mod ! p$ and check whether it is $1$ or $-1$).
answered Jul 31 at 23:16
Kaban-5
463
No. Suppose that you can find "true" (with respect to $g$) square root in $T(p)$ time (denote "true" square root of $x$ as $f_g (x)$). Then you can find discrete logarithm (for simplicity, let it take values $1, 2, ldots, p - 1$ instead of usual choice $0, 1, ldots, p - 2$) of any non-zero remainder modulo $p$ in $O(T(p) mathrmpoly(log p))$ time:
$log_g x = begincases 1 &mbox if $x = g$ \ 2 log_g f_g(x) &mbox if $x$ is a quadratic residue \
2 log_g f_g(gx) - 1 &mbox if $x$ is a quadratic non-residue and is not equal to $g$ endcases$.
Notice that $log_g f_g (x) = dfraclog_g x2$ and $log_g f_g(gx) = dfraclog_g x + 12$, so computation of $log_g x$ using this recursive formula halts in $O(log p)$ iterations. Also, making each recursive call takes
$O(mathrmpoly(log p))$ time.
(Checking whether number is quadratic residue or not can be easily done in $O(mathrmpoly(log p))$ time, for example one may calculate $x^(p-1)/2 !!! mod ! p$ and check whether it is $1$ or $-1$).
answered Jul 31 at 23:16
Kaban-5
463
edited Jul 31 at 23:33
answered Jul 31 at 23:16
Kaban-5
463
answered Jul 31 at 23:16
Kaban-5
463
answered Jul 31 at 23:16
Kaban-5
463
463
add a comment |Â
add a comment |Â
up vote
5
down vote
(I'm assuming $p$ is odd)
No; the answer to your question depends crucially on what you have chosen for $r$.
In your example you took $r = 46$ so that $y=56$ was the right answer, but you could just as easily have taken $r = 99$ instead, which would make $y=51$ the right answer. You could also have chosen $r=152$, but that gives the same result as $r=46$.
If you want to do something like restrict $r$ to the range $0 < r < fracp2$, I strongly disbelieve there is a general way to distinguish which of the two square you're asking for without basically computing $r$.
answered Jul 31 at 12:40
Hurkyl
107k9112253
Just confirming, if I restrict $r$, you disbelieve there is a general way?
– Robert Smiths
Jul 31 at 19:15
add a comment |Â
up vote
5
down vote
(I'm assuming $p$ is odd)
No; the answer to your question depends crucially on what you have chosen for $r$.
In your example you took $r = 46$ so that $y=56$ was the right answer, but you could just as easily have taken $r = 99$ instead, which would make $y=51$ the right answer. You could also have chosen $r=152$, but that gives the same result as $r=46$.
If you want to do something like restrict $r$ to the range $0 < r < fracp2$, I strongly disbelieve there is a general way to distinguish which of the two square you're asking for without basically computing $r$.
answered Jul 31 at 12:40
Hurkyl
107k9112253
Just confirming, if I restrict $r$, you disbelieve there is a general way?
– Robert Smiths
Jul 31 at 19:15
add a comment |Â
up vote
5
down vote
up vote
5
down vote
(I'm assuming $p$ is odd)
No; the answer to your question depends crucially on what you have chosen for $r$.
In your example you took $r = 46$ so that $y=56$ was the right answer, but you could just as easily have taken $r = 99$ instead, which would make $y=51$ the right answer. You could also have chosen $r=152$, but that gives the same result as $r=46$.
If you want to do something like restrict $r$ to the range $0 < r < fracp2$, I strongly disbelieve there is a general way to distinguish which of the two square you're asking for without basically computing $r$.
answered Jul 31 at 12:40
Hurkyl
107k9112253
(I'm assuming $p$ is odd)
No; the answer to your question depends crucially on what you have chosen for $r$.
In your example you took $r = 46$ so that $y=56$ was the right answer, but you could just as easily have taken $r = 99$ instead, which would make $y=51$ the right answer. You could also have chosen $r=152$, but that gives the same result as $r=46$.
If you want to do something like restrict $r$ to the range $0 < r < fracp2$, I strongly disbelieve there is a general way to distinguish which of the two square you're asking for without basically computing $r$.
answered Jul 31 at 12:40
Hurkyl
107k9112253
answered Jul 31 at 12:40
Hurkyl
107k9112253
answered Jul 31 at 12:40
Hurkyl
107k9112253
answered Jul 31 at 12:40
Hurkyl
107k9112253
107k9112253
Just confirming, if I restrict $r$, you disbelieve there is a general way?
– Robert Smiths
Jul 31 at 19:15
add a comment |Â
Just confirming, if I restrict $r$, you disbelieve there is a general way?
– Robert Smiths
Jul 31 at 19:15
Just confirming, if I restrict $r$, you disbelieve there is a general way?
– Robert Smiths
Jul 31 at 19:15
Just confirming, if I restrict $r$, you disbelieve there is a general way?
– Robert Smiths
Jul 31 at 19:15
add a comment |Â
up vote
3
down vote
If $y^2 equiv (g^r)^2 pmod p$ then $y equiv pm g^r pmod p$, because $Bbb Z/pBbb Z$ is a field.
answered Jul 31 at 12:38
Kenny Lau
17.7k2156
(-1) although this is true, it doesn't really answer the question and should be a comment. There isn't even a clear evidence that the OP wasn't aware of that.
– Arnaud Mortier
Jul 31 at 23:24
add a comment |Â
up vote
3
down vote
If $y^2 equiv (g^r)^2 pmod p$ then $y equiv pm g^r pmod p$, because $Bbb Z/pBbb Z$ is a field.
answered Jul 31 at 12:38
Kenny Lau
17.7k2156
(-1) although this is true, it doesn't really answer the question and should be a comment. There isn't even a clear evidence that the OP wasn't aware of that.
– Arnaud Mortier
Jul 31 at 23:24
add a comment |Â
up vote
3
down vote
up vote
3
down vote
If $y^2 equiv (g^r)^2 pmod p$ then $y equiv pm g^r pmod p$, because $Bbb Z/pBbb Z$ is a field.
answered Jul 31 at 12:38
Kenny Lau
17.7k2156
If $y^2 equiv (g^r)^2 pmod p$ then $y equiv pm g^r pmod p$, because $Bbb Z/pBbb Z$ is a field.
answered Jul 31 at 12:38
Kenny Lau
17.7k2156
answered Jul 31 at 12:38
Kenny Lau
17.7k2156
answered Jul 31 at 12:38
Kenny Lau
17.7k2156
answered Jul 31 at 12:38
Kenny Lau
17.7k2156
17.7k2156
(-1) although this is true, it doesn't really answer the question and should be a comment. There isn't even a clear evidence that the OP wasn't aware of that.
– Arnaud Mortier
Jul 31 at 23:24
add a comment |Â
(-1) although this is true, it doesn't really answer the question and should be a comment. There isn't even a clear evidence that the OP wasn't aware of that.
– Arnaud Mortier
Jul 31 at 23:24
(-1) although this is true, it doesn't really answer the question and should be a comment. There isn't even a clear evidence that the OP wasn't aware of that.
– Arnaud Mortier
Jul 31 at 23:24
(-1) although this is true, it doesn't really answer the question and should be a comment. There isn't even a clear evidence that the OP wasn't aware of that.
– Arnaud Mortier
Jul 31 at 23:24
add a comment |Â
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%2f2867994%2fdistinguishing-between-the-square-roots-of-a-quadratic-residue%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