2

When reading about Cipolla's algorithm on Wikipedia, I found that the number of quadratic non-residues in the image of $f:\Bbb F \longrightarrow \Bbb F, f(a) = a^2 - x^2$ where $\Bbb F$ is a finite field of prime cardinality $p$ and $x \in \Bbb F$, is $\frac{p-1} 2$. Why?

I was thinking that there might be some sort of symmetry between the nonzero quadratic residues and the quadratic nonresidues, but I don't see it.

[edit]

Wherever I previously said quadratic residue, it nows says quadratic nonresidue.

wlad
  • 8,185
  • 1
    Let $p=7$ and $x=1$. Then $a^2-1^2$ takes on values $-1,0,3,1$ modulo $7$. – André Nicolas Jun 04 '15 at 13:39
  • For $p=2$, the statement doesn't make any sense. For $x=0$, it's clearly false. And $\frac{p-1}{2}$ is the total number of quadratic non-residues in $\mathbb F$, so $a^2-x^2$ may never be a square for the claim to hold. – Thomas Poguntke Jun 04 '15 at 13:41

2 Answers2

1

This is not true in general. Let $p=7$ and $x=1$. Then $a^2-1^2$ takes on values $-1,0,3,1$ modulo $7$. There is only one QR in the bunch, and two NR.

What is true for odd primes $p$ is that $f(a)$ takes on exactly $\frac{p-1}{2}$ diferent non-zero values modulo $p$. But this is obvious, since $a^2$ takes on $\frac{p-1}{2}+1$ values.

Remark: The Wikipedia article does not count the number of non-residues in the image of $f$. For each $a$ it makes a tick if $a^2-x^2$ is a NR, and it counts the number of ticks.

André Nicolas
  • 507,029
  • Let $p\neq 2$ and $x \neq 0$. In particular, the statement never holds for $p \equiv 1 \bmod 4$, since then $$\left(\frac{-x^2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{x^2}{p}\right) = \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = 1.$$ Thus $f(\mathbb F)$ contains both $0$ and $-x^2$ as quadratic residues, hence less than $\frac{p-1}{2}$ quadratic non-residues. – Thomas Poguntke Jun 04 '15 at 14:18
  • @Engloutie Does that mean Wikipedia is wrong? – wlad Jun 04 '15 at 15:28
  • 1
    It may be your interpretation of what they say. My reading of the "there is a chance" part is that it is not the range of $f(a)$ that they are talking about, but the number of (not necessarily distinct) values. In the case of my $7$ and $1$ we would get values $-1,0,3, 1, 1, 3, 0$, so three non-residues, if we counteach occurrence of the $3$. – André Nicolas Jun 04 '15 at 15:46
  • Your remark is right. – wlad Jun 04 '15 at 15:57
0

$$f(a) = a^2 - x^2 = a^2\left(1 - \left( \frac x a \right)^2 \right)$$

Now $x/a$ can be anything, so we've got the $1 - $ an arbitrary quadratic residue. The problem becomes counting how many quadratic residues there are in the image of $f(x) = 1 - x^2$ (I found it distracting to make the constant in the function $x$).

So let's say we've got $$1 - x^2 = y^2 \iff 1 = x^2 + y^2$$ This looks like a circle. So we have to count the number of points on the unit circle, and then get rid of repeated values of $x$.

Maybe we can do that considering lines from $(-1,0)$ to the circle. Every point on the circle has such a line, and so we just have to show that for any slope we get two points only one of which is $(-1,0)$ (therefore making it one-to-one). The non-$(-1,0)$ solution to this is well known: $$(\frac{2t}{1 + t^2}, \frac{1-t^2} {1+t^2})$$ where $t$ is the slope of the line. So we have that every point yields a unique line and every line yields a point, so one-to-one as claimed.

Now divide the number of points on the circle (which is $p+1$, when counting every slope value and the vertical line) by $2$ and then add $1$ to get $\frac{p+1}{2} + 1 = \frac{p + 3} 2$

wlad
  • 8,185