4
$\begingroup$

Take the set of integers $\{0, 1, .., p-1\}$, square each element, you get the (smaller) set of quadratic residues. Repeat until you get a fix point set. The size of this set is a function of $p$. Does this function have a name? How can I efficiently calculate it?

Some values: $$f(3) = 2, \\ f(5) = 2,\\ f(7) = 4,\\ f(11) = 6,\\ f(13) = 4, \\ f(17) = 2,\\ f(19) = 10,\\ f(23) = 12,\\ f(29) = 8$$

$\endgroup$
6
$\begingroup$

Let us factor $p-1=2^am$, where $m$ is odd. The size of your terminal set is $m$. You are working with a cyclic group of order $p-1$. As $m$ is odd, the Chinese Remainder Theorem tells you that there is an isomorphism $$ \mathbb{Z}_p^*\cong C_m\times C_{2^a}. $$ Repeated squaring kills the $C_{2^a}$ after $a$ iterations, and squaring is bijective on $C_m$.

If you include $0$ (I didn't), then add one.

$\endgroup$
  • 2
    $\begingroup$ There seems to be a difference of $1$, cf. OP's examples. Maybe from $x=0$? $\endgroup$ – Hagen von Eitzen Jul 15 '13 at 15:32
  • $\begingroup$ Great! Thanks! I will accept this in 9 minutes ;) $\endgroup$ – aelguindy Jul 15 '13 at 15:33
  • $\begingroup$ @aelguindy: Sorry about not reading carefully enough, so I missed zero initially. Basically you just take $p-1$ and keep dividing it with two as many times as it takes to make the quotient odd. No need to fully factorize. $\endgroup$ – Jyrki Lahtonen Jul 15 '13 at 15:35
  • $\begingroup$ No worries! All that I figured out myself. I just needed to see $\mathbb{Z}_p^* \cong C_m \times C_{2^a}$ ;). Thanks again! $\endgroup$ – aelguindy Jul 15 '13 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.