https://www.rieselprime.de/z/index.php?title=Modular_square_root&feed=atom&action=history
Modular square root - Revision history
2024-03-28T11:02:26Z
Revision history for this page on the wiki
MediaWiki 1.31.1
https://www.rieselprime.de/z/index.php?title=Modular_square_root&diff=835&oldid=prev
Karbon at 10:38, 6 February 2019
2019-02-06T10:38:16Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 10:38, 6 February 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>A '''modular square root''' <math>r</math> of an [[integer]] number <math>a</math> modulo an integer <math>m</math> greater than 1 is an integer such that:</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>A '''modular square root''' <math>r</math> of an [[integer]] number <math>a</math> modulo an integer <math>m</math> greater than 1 is an integer such that:</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:<math>r^2 \equiv a\<del class="diffchange diffchange-inline">,</del>\pmod m</math></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<math>r^2 \equiv a\ \pmod m</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In this article we will consider the case when the modulus is [[<del class="diffchange diffchange-inline">prime number|</del>prime]]. Otherwise we can compute the square roots modulo the prime factors of <math>m</math> and then generate a solution using the Chinese Remainder Theorem.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In this article we will consider the case when the modulus is [[prime]]. Otherwise we can compute the square roots modulo the prime factors of <math>m</math> and then generate a solution using the Chinese Remainder Theorem.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>When the argument is congruent to zero, there is only one modular square root, namely zero. Otherwise, the number of square roots can be two or zero depending on whether the argument is a [[quadratic residue]] modulo <math>m</math> or not. The sum of both square roots is congruent to zero.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>When the argument is congruent to zero, there is only one modular square root, namely zero. Otherwise, the number of square roots can be two or zero depending on whether the argument is a [[quadratic residue]] modulo <math>m</math> or not. The sum of both square roots is congruent to zero.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In order to compute the square root, we will consider different cases, depending on the modulus. When this modulus is odd, we assume that the quantity <math>a^{(m-1)/2} \bmod m</math> equals 1 (otherwise there is no square root if <math>a \not\equiv 0\<del class="diffchange diffchange-inline">,</del>\pmod m</math>).</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In order to compute the square root, we will consider different cases, depending on the modulus. When this modulus is odd, we assume that the quantity <math>a^{(m-1)/2} \bmod m</math> equals 1 (otherwise there is no square root if <math>a \not\equiv 0\ \pmod m</math>).</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Modulus equal to 2===</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Modulus equal to 2===</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l12" >Line 12:</td>
<td colspan="2" class="diff-lineno">Line 12:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Modulus congruent to 3 modulo 4===</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Modulus congruent to 3 modulo 4===</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:<math>r\equiv \pm a^{(m+1)/4}\<del class="diffchange diffchange-inline">,</del>\pmod m</math></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<math>r\equiv \pm a^{(m+1)/4}\ \pmod m</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Modulus congruent to 5 modulo 8===</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Modulus congruent to 5 modulo 8===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>First compute the square root of -1 (<math>i</math>) as follows:</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>First compute the square root of -1 (<math>i</math>) as follows:</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:<math>v\equiv (2a)^{(p-5)/8}\<del class="diffchange diffchange-inline">,</del>\pmod m</math></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<math>v\equiv (2a)^{(p-5)/8}\ \pmod m</math></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:<math>i\equiv 2av^2\<del class="diffchange diffchange-inline">,</del>\pmod m</math></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<math>i\equiv 2av^2\ \pmod m</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Then compute the square root as follows:</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Then compute the square root as follows:</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:<math>r\equiv \pm av(i-1)\<del class="diffchange diffchange-inline">,</del>\pmod m</math></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<math>r\equiv \pm av(i-1)\ \pmod m</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Modulus congruent to 1 modulo 8===</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Modulus congruent to 1 modulo 8===</div></td></tr>
</table>
Karbon
https://www.rieselprime.de/z/index.php?title=Modular_square_root&diff=533&oldid=prev
Karbon: restored
2019-01-26T21:39:43Z
<p>restored</p>
<p><b>New page</b></p><div>A '''modular square root''' <math>r</math> of an [[integer]] number <math>a</math> modulo an integer <math>m</math> greater than 1 is an integer such that:<br />
:<math>r^2 \equiv a\,\pmod m</math><br />
<br />
In this article we will consider the case when the modulus is [[prime number|prime]]. Otherwise we can compute the square roots modulo the prime factors of <math>m</math> and then generate a solution using the Chinese Remainder Theorem.<br />
<br />
When the argument is congruent to zero, there is only one modular square root, namely zero. Otherwise, the number of square roots can be two or zero depending on whether the argument is a [[quadratic residue]] modulo <math>m</math> or not. The sum of both square roots is congruent to zero.<br />
<br />
In order to compute the square root, we will consider different cases, depending on the modulus. When this modulus is odd, we assume that the quantity <math>a^{(m-1)/2} \bmod m</math> equals 1 (otherwise there is no square root if <math>a \not\equiv 0\,\pmod m</math>).<br />
<br />
===Modulus equal to 2===<br />
In this case the square root is congruent to the argument <math>r</math>.<br />
<br />
===Modulus congruent to 3 modulo 4===<br />
:<math>r\equiv \pm a^{(m+1)/4}\,\pmod m</math><br />
<br />
===Modulus congruent to 5 modulo 8===<br />
First compute the square root of -1 (<math>i</math>) as follows:<br />
:<math>v\equiv (2a)^{(p-5)/8}\,\pmod m</math><br />
:<math>i\equiv 2av^2\,\pmod m</math><br />
<br />
Then compute the square root as follows:<br />
:<math>r\equiv \pm av(i-1)\,\pmod m</math><br />
<br />
===Modulus congruent to 1 modulo 8===<br />
In this case we can use the Shanks method.<br />
#Set <math>e</math> and an odd <math>q</math> such that <math>m = 2^e q+1</math>.<br />
#Choose <math>x</math> at random in the range <math>1 < x < m</math> and set <math>z \leftarrow x^q\,\bmod m</math>. If <math>z^{2^{e-1}}\equiv 1\,\pmod m</math>, repeat this step. (This generates a quadratic non-residue of <math>m</math>.)<br />
#Set <math>y \leftarrow z</math>, <math>r \leftarrow e</math>, <math>x \leftarrow a^{(q-1)/2} \bmod m</math>, <math>v \leftarrow ax\bmod m</math>, <math>w \leftarrow vx \bmod m</math>.<br />
#If <math>w=1</math>, the computation ends with <math>\pm v</math> as the square root.<br />
#Find the smallest value of <math>k</math> such that <math>w^{2^k}\equiv 1\,\pmod m</math>.<br />
#Set <math>d \leftarrow y^{2^{r-k-1}} \bmod m</math>, <math>y \leftarrow d^2\,\bmod m</math>, <math>r \leftarrow k</math>, <math>v \leftarrow dv\,\bmod m</math>, <math>w \leftarrow wy\,\bmod m</math>.<br />
#Go to step 4.<br />
<br />
===Example 1===<br />
Find the square root of 58 modulo 101.<br />
<br />
First of all we check that the modulus 101 is prime. Then we find that it is congruent to 5 mod 8.<br />
<br />
Now we compute <math>58^{(101-1)/2} \bmod 101 = 1</math> so there are two square roots to be computed.<br />
<br />
<math>v = (2*58)^{(101-5)/8} \bmod 101 = 15^{12} \bmod 101 = 88</math><br />
<br />
<math>i = 2*58*88^2 \bmod 101 = 10</math><br />
<br />
Notice that <math>i*i \equiv -1 \,\pmod {101}</math><br />
<br />
<math>r = 58*88*(10-1) \bmod 101 = 82</math><br />
<br />
So the modular square roots are 82 and its negative 19, which can be easily verified: <math>82*82 \equiv 58 \,\pmod {101}</math>, <math>19*19 \equiv 58 \,\pmod {101}</math>.<br />
<br />
===Example 2===<br />
Find the square root of 111 modulo 113.<br />
<br />
First of all we check that the modulus 113 is prime. Then we find that it is congruent to 1 mod 8.<br />
<br />
Now we compute <math>111^{(113-1)/2} \bmod 113 = 1</math> so there are two square roots to be computed.<br />
<br />
*Step 1: <math>e = 4</math>, <math>q = 7</math>.<br />
*Step 2: <math>x = 2</math>, <math>z = 2^7 \bmod 113 = 15</math>, <math>z^{2^3} \bmod 113 = 1</math>, so we have to repeat step 2.<br />
*Step 2: <math>x = 3</math>, <math>z = 3^7 \bmod 113 = 40</math>, <math>z^{2^3} \bmod 113 = 112</math>.<br />
*Step 3: <math>y = 40</math>, <math>r = 4</math>, <math>x = 111^{(7-1)/2} \bmod 113 = 105</math>, <math>v = 111*105 \bmod 113 = 16</math>, <math>w = 16*105 \bmod 113 = 98</math>.<br />
*Step 4: <math>w</math> is not equal to 1 so the computation continues.<br />
*Step 5: <math>k = 2</math><br />
*Step 6: <math>d = 40^{2^{4-2-1}} \bmod 113 = 18</math>, <math>y = 18^2 \bmod 113 = 98</math>, <math>r = 2</math>, <math>v = 18*16 \bmod 113 = 62</math>, <math>w = 98*98 \bmod 113 = 112</math>.<br />
*Step 4: <math>w</math> is not equal to 1 so the computation continues.<br />
*Step 5: <math>k = 1</math><br />
*Step 6: <math>d = 98^{2^{2-1-1}} \bmod 113 = 98</math>, <math>y = 98^2 \bmod 113 = 112</math>, <math>r = 1</math>, <math>v = 98*62 \bmod 113 = 87</math>, <math>w = 112*112 \bmod 113 = 1</math>.<br />
*Step 4: <math>w = 1</math>, so the square root is <math>\pm v = \pm 87</math>.<br />
<br />
So the modular square roots are 87 and its negative 26, which can be easily verified: <math>87*87 \equiv 111 \,\pmod {113}</math>, <math>26*26 \equiv 111 \,\pmod {113}</math>.<br />
[[Category:Math]]</div>
Karbon