Ask Your Question
1

find all squares modulo a prime number

asked 2016-09-05 11:07:55 +0100

this post is marked as community wiki

This post is a wiki. Anyone with karma >750 is welcome to improve it.

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.

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
2

answered 2016-09-13 14:54:56 +0100

kcrisman gravatar image

This 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.

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|.
edit flag offensive delete link more

Comments

Thanks 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 faster
tmonteil gravatar imagetmonteil ( 2016-09-13 15:37:09 +0100 )edit

Yeah, and there is an easy theoretical reason for the second bullet point.

kcrisman gravatar imagekcrisman ( 2016-09-14 16:39:35 +0100 )edit
1

answered 2016-09-05 11:30:13 +0100

tmonteil gravatar image

updated 2016-09-05 11:32:11 +0100

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:

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
edit flag offensive delete link more

Comments

@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?

Sha gravatar imageSha ( 2016-09-06 11:44:23 +0100 )edit

Well, everything else would be a non-square, right? So perhaps not (n^2 % p)?

kcrisman gravatar imagekcrisman ( 2016-09-06 15:01:05 +0100 )edit

@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)}
Sha gravatar imageSha ( 2016-09-13 03:46:24 +0100 )edit

Sorry, 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.

kcrisman gravatar imagekcrisman ( 2016-09-13 14:22:25 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2016-09-05 11:07:55 +0100

Seen: 605 times

Last updated: Sep 13 '16