Mixing
Is there an efficient way to compute the square root of modulo prime?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Is there a reasonably simple way to find the square root of $a$ modulo $p$ where $p$ is an odd prime?
If the odd prime is small number it seems you can do this by brute force. HOwever if we want to solve something like x^2=2 mod 103 (whose solution is 38 and 65 mod 103) is pretty cumbersome because we have a non-linear Diophantine equation x^2=2+101y. Is there an efficient and quick method to solve something of this kind? If I try primitive roots then the first primitive root is 5 not 2 so that does not help.
elementary-number-theory
asked Jul 15 at 11:07
matqkks
1,09511631
add a comment |Â
up vote
2
down vote
favorite
Is there a reasonably simple way to find the square root of $a$ modulo $p$ where $p$ is an odd prime?
If the odd prime is small number it seems you can do this by brute force. HOwever if we want to solve something like x^2=2 mod 103 (whose solution is 38 and 65 mod 103) is pretty cumbersome because we have a non-linear Diophantine equation x^2=2+101y. Is there an efficient and quick method to solve something of this kind? If I try primitive roots then the first primitive root is 5 not 2 so that does not help.
elementary-number-theory
asked Jul 15 at 11:07
matqkks
1,09511631
1
Please see here on MO.
– TheSimpliFire
Jul 15 at 11:22
1
Do you know how to do this if p is 3 mod 4? In that case it's very easy: just raise a to the (p+1)/4 modulo p. (Of course this only works if a has a square root mod p.) The above link seems to be showing that it's always efficient, but it is definitely more complicated in the case that p is 1 mod 4.
– CJD
Jul 15 at 11:47
@cjd, fyi. What if you try tovtwke the square root of a residue $r bmod p$ that isn't a quadratic residue? With $pequiv 3bmod 4$ the $r^(p+1)/4$ formula gives instead a square root of $-r$.
– Oscar Lanzi
Jul 15 at 12:33
Tonelli–Shanks algorithm
– Count Iblis
Jul 15 at 14:36
1
The easy case $p equiv 3 bmod 4$ has been discussed in previous Questions, but there is perhaps room on Math.SE for a comprehensive Answer for $p equiv 1 bmod 4$ (not just the link to the Wikipedia article, as there are competing algorithms).
– hardmath
Jul 15 at 19:20
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Is there a reasonably simple way to find the square root of $a$ modulo $p$ where $p$ is an odd prime?
If the odd prime is small number it seems you can do this by brute force. HOwever if we want to solve something like x^2=2 mod 103 (whose solution is 38 and 65 mod 103) is pretty cumbersome because we have a non-linear Diophantine equation x^2=2+101y. Is there an efficient and quick method to solve something of this kind? If I try primitive roots then the first primitive root is 5 not 2 so that does not help.
elementary-number-theory
asked Jul 15 at 11:07
matqkks
1,09511631
Is there a reasonably simple way to find the square root of $a$ modulo $p$ where $p$ is an odd prime?
If the odd prime is small number it seems you can do this by brute force. HOwever if we want to solve something like x^2=2 mod 103 (whose solution is 38 and 65 mod 103) is pretty cumbersome because we have a non-linear Diophantine equation x^2=2+101y. Is there an efficient and quick method to solve something of this kind? If I try primitive roots then the first primitive root is 5 not 2 so that does not help.
elementary-number-theory
asked Jul 15 at 11:07
matqkks
1,09511631
edited Jul 15 at 18:46
asked Jul 15 at 11:07
matqkks
1,09511631
asked Jul 15 at 11:07
matqkks
1,09511631
asked Jul 15 at 11:07
matqkks
1,09511631
1,09511631
1
Please see here on MO.
– TheSimpliFire
Jul 15 at 11:22
1
Do you know how to do this if p is 3 mod 4? In that case it's very easy: just raise a to the (p+1)/4 modulo p. (Of course this only works if a has a square root mod p.) The above link seems to be showing that it's always efficient, but it is definitely more complicated in the case that p is 1 mod 4.
– CJD
Jul 15 at 11:47
@cjd, fyi. What if you try tovtwke the square root of a residue $r bmod p$ that isn't a quadratic residue? With $pequiv 3bmod 4$ the $r^(p+1)/4$ formula gives instead a square root of $-r$.
– Oscar Lanzi
Jul 15 at 12:33
Tonelli–Shanks algorithm
– Count Iblis
Jul 15 at 14:36
1
The easy case $p equiv 3 bmod 4$ has been discussed in previous Questions, but there is perhaps room on Math.SE for a comprehensive Answer for $p equiv 1 bmod 4$ (not just the link to the Wikipedia article, as there are competing algorithms).
– hardmath
Jul 15 at 19:20
add a comment |Â
1
Please see here on MO.
– TheSimpliFire
Jul 15 at 11:22
1
Do you know how to do this if p is 3 mod 4? In that case it's very easy: just raise a to the (p+1)/4 modulo p. (Of course this only works if a has a square root mod p.) The above link seems to be showing that it's always efficient, but it is definitely more complicated in the case that p is 1 mod 4.
– CJD
Jul 15 at 11:47
@cjd, fyi. What if you try tovtwke the square root of a residue $r bmod p$ that isn't a quadratic residue? With $pequiv 3bmod 4$ the $r^(p+1)/4$ formula gives instead a square root of $-r$.
– Oscar Lanzi
Jul 15 at 12:33
Tonelli–Shanks algorithm
– Count Iblis
Jul 15 at 14:36
1
The easy case $p equiv 3 bmod 4$ has been discussed in previous Questions, but there is perhaps room on Math.SE for a comprehensive Answer for $p equiv 1 bmod 4$ (not just the link to the Wikipedia article, as there are competing algorithms).
– hardmath
Jul 15 at 19:20
1
1
Please see here on MO.
– TheSimpliFire
Jul 15 at 11:22
Please see here on MO.
– TheSimpliFire
Jul 15 at 11:22
1
1
Do you know how to do this if p is 3 mod 4? In that case it's very easy: just raise a to the (p+1)/4 modulo p. (Of course this only works if a has a square root mod p.) The above link seems to be showing that it's always efficient, but it is definitely more complicated in the case that p is 1 mod 4.
– CJD
Jul 15 at 11:47
Do you know how to do this if p is 3 mod 4? In that case it's very easy: just raise a to the (p+1)/4 modulo p. (Of course this only works if a has a square root mod p.) The above link seems to be showing that it's always efficient, but it is definitely more complicated in the case that p is 1 mod 4.
– CJD
Jul 15 at 11:47
@cjd, fyi. What if you try tovtwke the square root of a residue $r bmod p$ that isn't a quadratic residue? With $pequiv 3bmod 4$ the $r^(p+1)/4$ formula gives instead a square root of $-r$.
– Oscar Lanzi
Jul 15 at 12:33
@cjd, fyi. What if you try tovtwke the square root of a residue $r bmod p$ that isn't a quadratic residue? With $pequiv 3bmod 4$ the $r^(p+1)/4$ formula gives instead a square root of $-r$.
– Oscar Lanzi
Jul 15 at 12:33
Tonelli–Shanks algorithm
– Count Iblis
Jul 15 at 14:36
Tonelli–Shanks algorithm
– Count Iblis
Jul 15 at 14:36
1
1
The easy case $p equiv 3 bmod 4$ has been discussed in previous Questions, but there is perhaps room on Math.SE for a comprehensive Answer for $p equiv 1 bmod 4$ (not just the link to the Wikipedia article, as there are competing algorithms).
– hardmath
Jul 15 at 19:20
The easy case $p equiv 3 bmod 4$ has been discussed in previous Questions, but there is perhaps room on Math.SE for a comprehensive Answer for $p equiv 1 bmod 4$ (not just the link to the Wikipedia article, as there are competing algorithms).
– hardmath
Jul 15 at 19:20
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
Partial answer:
If $p=4n-1$, then let $b = a^fracp+14$. Then $b^2=a^fracp+12=a^fracp-12aequiv a$ because of Euler's criterion.
answered Jul 15 at 12:09
lhf
156k9160367
add a comment |Â
up vote
1
down vote
Let $p$ be an odd prime and we can say whether an integer $a$, $ane0(mboxmod)p,$ has a square root mod $p$ or not by
$$mboxa is begincasesmboxa quadratic residue if $a^fracp-12equiv 1(mboxmod p)$ \mboxa quadratic nonresidue if $a^fracp-12equiv -1(mboxmod p)$endcases$$
answered Jul 15 at 11:48
Key Flex
4,406525
2
That doesn't compute the square root.
– Lord Shark the Unknown
Jul 15 at 11:55
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Partial answer:
If $p=4n-1$, then let $b = a^fracp+14$. Then $b^2=a^fracp+12=a^fracp-12aequiv a$ because of Euler's criterion.
answered Jul 15 at 12:09
lhf
156k9160367
add a comment |Â
up vote
3
down vote
Partial answer:
If $p=4n-1$, then let $b = a^fracp+14$. Then $b^2=a^fracp+12=a^fracp-12aequiv a$ because of Euler's criterion.
answered Jul 15 at 12:09
lhf
156k9160367
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Partial answer:
If $p=4n-1$, then let $b = a^fracp+14$. Then $b^2=a^fracp+12=a^fracp-12aequiv a$ because of Euler's criterion.
answered Jul 15 at 12:09
lhf
156k9160367
Partial answer:
If $p=4n-1$, then let $b = a^fracp+14$. Then $b^2=a^fracp+12=a^fracp-12aequiv a$ because of Euler's criterion.
answered Jul 15 at 12:09
lhf
156k9160367
answered Jul 15 at 12:09
lhf
156k9160367
answered Jul 15 at 12:09
lhf
156k9160367
answered Jul 15 at 12:09
lhf
156k9160367
156k9160367
add a comment |Â
add a comment |Â
up vote
1
down vote
Let $p$ be an odd prime and we can say whether an integer $a$, $ane0(mboxmod)p,$ has a square root mod $p$ or not by
$$mboxa is begincasesmboxa quadratic residue if $a^fracp-12equiv 1(mboxmod p)$ \mboxa quadratic nonresidue if $a^fracp-12equiv -1(mboxmod p)$endcases$$
answered Jul 15 at 11:48
Key Flex
4,406525
2
That doesn't compute the square root.
– Lord Shark the Unknown
Jul 15 at 11:55
add a comment |Â
up vote
1
down vote
Let $p$ be an odd prime and we can say whether an integer $a$, $ane0(mboxmod)p,$ has a square root mod $p$ or not by
$$mboxa is begincasesmboxa quadratic residue if $a^fracp-12equiv 1(mboxmod p)$ \mboxa quadratic nonresidue if $a^fracp-12equiv -1(mboxmod p)$endcases$$
answered Jul 15 at 11:48
Key Flex
4,406525
2
That doesn't compute the square root.
– Lord Shark the Unknown
Jul 15 at 11:55
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Let $p$ be an odd prime and we can say whether an integer $a$, $ane0(mboxmod)p,$ has a square root mod $p$ or not by
$$mboxa is begincasesmboxa quadratic residue if $a^fracp-12equiv 1(mboxmod p)$ \mboxa quadratic nonresidue if $a^fracp-12equiv -1(mboxmod p)$endcases$$
answered Jul 15 at 11:48
Key Flex
4,406525
Let $p$ be an odd prime and we can say whether an integer $a$, $ane0(mboxmod)p,$ has a square root mod $p$ or not by
$$mboxa is begincasesmboxa quadratic residue if $a^fracp-12equiv 1(mboxmod p)$ \mboxa quadratic nonresidue if $a^fracp-12equiv -1(mboxmod p)$endcases$$
answered Jul 15 at 11:48
Key Flex
4,406525
edited Jul 15 at 12:02
answered Jul 15 at 11:48
Key Flex
4,406525
answered Jul 15 at 11:48
Key Flex
4,406525
answered Jul 15 at 11:48
Key Flex
4,406525
4,406525
2
That doesn't compute the square root.
– Lord Shark the Unknown
Jul 15 at 11:55
add a comment |Â
2
That doesn't compute the square root.
– Lord Shark the Unknown
Jul 15 at 11:55
2
2
That doesn't compute the square root.
– Lord Shark the Unknown
Jul 15 at 11:55
That doesn't compute the square root.
– Lord Shark the Unknown
Jul 15 at 11:55
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%2f2852403%2fis-there-an-efficient-way-to-compute-the-square-root-of-modulo-prime%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
1
Please see here on MO.
– TheSimpliFire
Jul 15 at 11:22
1
Do you know how to do this if p is 3 mod 4? In that case it's very easy: just raise a to the (p+1)/4 modulo p. (Of course this only works if a has a square root mod p.) The above link seems to be showing that it's always efficient, but it is definitely more complicated in the case that p is 1 mod 4.
– CJD
Jul 15 at 11:47
@cjd, fyi. What if you try tovtwke the square root of a residue $r bmod p$ that isn't a quadratic residue? With $pequiv 3bmod 4$ the $r^(p+1)/4$ formula gives instead a square root of $-r$.
– Oscar Lanzi
Jul 15 at 12:33
Tonelli–Shanks algorithm
– Count Iblis
Jul 15 at 14:36
1
The easy case $p equiv 3 bmod 4$ has been discussed in previous Questions, but there is perhaps room on Math.SE for a comprehensive Answer for $p equiv 1 bmod 4$ (not just the link to the Wikipedia article, as there are competing algorithms).
– hardmath
Jul 15 at 19:20