ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 14 Sep 2016 16:39:35 +0200find all squares modulo a prime numberhttps://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/I have been using PARI-GP to find the squares of a prime number. For example
for(JJ=0,7,print1(JJ^2%8"\t"))
in PARI gives
0 1 4 1 0 1 4 1
from which I know that the squares modulo 8 are 1 and 4. Now that I need to find the squares modulo large prime, I was wondering is there a way SAGE can give me a complete list without repeating the values. Mon, 05 Sep 2016 11:07:55 +0200https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/Answer by tmonteil for <p>I have been using PARI-GP to find the squares of a prime number. For example</p>
<pre><code>for(JJ=0,7,print1(JJ^2%8"\t"))
</code></pre>
<p>in PARI gives</p>
<pre><code>0 1 4 1 0 1 4 1
</code></pre>
<p>from which I know that the squares modulo 8 are 1 and 4. Now that I need to find the squares modulo large prime, I was wondering is there a way SAGE can give me a complete list without repeating the values. </p>
https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?answer=34725#post-id-34725Given that $(n + p)^2 = n^2 + 2np + p^2 = n^2 \mbox{ mod } p$, you just have to compute the numbers $n^2 \mbox{ mod } p$ for all integers between $0$ and $p-1$. If you want to avoid repetitions, you just have to put them in a set. Here is how:
sage: p = 17
sage: S = {n^2 % p for n in range(p)}
sage: S
{0, 1, 2, 4, 8, 9, 13, 15, 16}
sage: p = 123457
sage: S = {n^2 % p for n in range(p)}
sage: len(S)
61729Mon, 05 Sep 2016 11:30:13 +0200https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?answer=34725#post-id-34725Comment by Sha for <p>Given that $(n + p)^2 = n^2 + 2np + p^2 = n^2 \mbox{ mod } p$, you just have to compute the numbers $n^2 \mbox{ mod } p$ for all integers between $0$ and $p-1$. If you want to avoid repetitions, you just have to put them in a set. Here is how:</p>
<pre><code>sage: p = 17
sage: S = {n^2 % p for n in range(p)}
sage: S
{0, 1, 2, 4, 8, 9, 13, 15, 16}
sage: p = 123457
sage: S = {n^2 % p for n in range(p)}
sage: len(S)
61729
</code></pre>
https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34808#post-id-34808@kcrisman I tried both of this command but it did not work. Instead it gave me a "False" answer.
S={not(n^2%p) for n in range(p)}
S=not {n^2%p for n in range(p)}Tue, 13 Sep 2016 03:46:24 +0200https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34808#post-id-34808Comment by kcrisman for <p>Given that $(n + p)^2 = n^2 + 2np + p^2 = n^2 \mbox{ mod } p$, you just have to compute the numbers $n^2 \mbox{ mod } p$ for all integers between $0$ and $p-1$. If you want to avoid repetitions, you just have to put them in a set. Here is how:</p>
<pre><code>sage: p = 17
sage: S = {n^2 % p for n in range(p)}
sage: S
{0, 1, 2, 4, 8, 9, 13, 15, 16}
sage: p = 123457
sage: S = {n^2 % p for n in range(p)}
sage: len(S)
61729
</code></pre>
https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34812#post-id-34812Sorry, I thought you were somehow getting `True` or `False`. You would want to look for `n` such that it was not in this list. Anyway, an easier way to do this with Thierry's syntax is just `set(range(p)).difference(S)`. You need the `set` because then you get set difference.Tue, 13 Sep 2016 14:22:25 +0200https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34812#post-id-34812Comment by Sha for <p>Given that $(n + p)^2 = n^2 + 2np + p^2 = n^2 \mbox{ mod } p$, you just have to compute the numbers $n^2 \mbox{ mod } p$ for all integers between $0$ and $p-1$. If you want to avoid repetitions, you just have to put them in a set. Here is how:</p>
<pre><code>sage: p = 17
sage: S = {n^2 % p for n in range(p)}
sage: S
{0, 1, 2, 4, 8, 9, 13, 15, 16}
sage: p = 123457
sage: S = {n^2 % p for n in range(p)}
sage: len(S)
61729
</code></pre>
https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34747#post-id-34747@tmonteil thank you. your answer is very helpful to me. Can I do the same for non-squares? How to obtain the set of non-squares from the code?Tue, 06 Sep 2016 11:44:23 +0200https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34747#post-id-34747Comment by kcrisman for <p>Given that $(n + p)^2 = n^2 + 2np + p^2 = n^2 \mbox{ mod } p$, you just have to compute the numbers $n^2 \mbox{ mod } p$ for all integers between $0$ and $p-1$. If you want to avoid repetitions, you just have to put them in a set. Here is how:</p>
<pre><code>sage: p = 17
sage: S = {n^2 % p for n in range(p)}
sage: S
{0, 1, 2, 4, 8, 9, 13, 15, 16}
sage: p = 123457
sage: S = {n^2 % p for n in range(p)}
sage: len(S)
61729
</code></pre>
https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34749#post-id-34749Well, everything *else* would be a non-square, right? So perhaps `not (n^2 % p)`?Tue, 06 Sep 2016 15:01:05 +0200https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34749#post-id-34749Answer by kcrisman for <p>I have been using PARI-GP to find the squares of a prime number. For example</p>
<pre><code>for(JJ=0,7,print1(JJ^2%8"\t"))
</code></pre>
<p>in PARI gives</p>
<pre><code>0 1 4 1 0 1 4 1
</code></pre>
<p>from which I know that the squares modulo 8 are 1 and 4. Now that I need to find the squares modulo large prime, I was wondering is there a way SAGE can give me a complete list without repeating the values. </p>
https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?answer=34813#post-id-34813This answer sort of cheats, but:
sage: p = 17
sage: quadratic_residues(p)
[0, 1, 2, 4, 8, 9, 13, 15, 16]
This is, after all, a [well-known concept](https://en.wikipedia.org/wiki/Quadratic_residue).
This works for your example too, even though 8 isn't prime
sage: quadratic_residues?
Signature: quadratic_residues(n)
Docstring:
Return a sorted list of all squares modulo the integer n in the
range 0<= x < |n|.
Tue, 13 Sep 2016 14:54:56 +0200https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?answer=34813#post-id-34813Comment by tmonteil for <p>This answer sort of cheats, but:</p>
<pre><code>sage: p = 17
sage: quadratic_residues(p)
[0, 1, 2, 4, 8, 9, 13, 15, 16]
</code></pre>
<p>This is, after all, a <a href="https://en.wikipedia.org/wiki/Quadratic_residue">well-known concept</a>.</p>
<p>This works for your example too, even though 8 isn't prime</p>
<pre><code>sage: quadratic_residues?
Signature: quadratic_residues(n)
Docstring:
Return a sorted list of all squares modulo the integer n in the
range 0<= x < |n|.
</code></pre>
https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34814#post-id-34814Thanks for pointing this out ! Actually the source code is almost the same except that
- the set is turned into a sorted list
- the loop ends at `p//2+1`
- instead of `p^2` it uses `p*p` which is a bit fasterTue, 13 Sep 2016 15:37:09 +0200https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34814#post-id-34814Comment by kcrisman for <p>This answer sort of cheats, but:</p>
<pre><code>sage: p = 17
sage: quadratic_residues(p)
[0, 1, 2, 4, 8, 9, 13, 15, 16]
</code></pre>
<p>This is, after all, a <a href="https://en.wikipedia.org/wiki/Quadratic_residue">well-known concept</a>.</p>
<p>This works for your example too, even though 8 isn't prime</p>
<pre><code>sage: quadratic_residues?
Signature: quadratic_residues(n)
Docstring:
Return a sorted list of all squares modulo the integer n in the
range 0<= x < |n|.
</code></pre>
https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34819#post-id-34819Yeah, and there is an easy theoretical reason for the second bullet point.Wed, 14 Sep 2016 16:39:35 +0200https://ask.sagemath.org/question/34724/find-all-squares-modulo-a-prime-number/?comment=34819#post-id-34819