# Square roots of unity modulo (N/f)^2

My question relates to square roots of unity modulo N, ie $r^2 = 1 \mod N$.

I have an efficient algorithm for obtaining these for arbitrary $N$. But for a given $N$ what I really want is to obtain the roots for all $N_f = \frac {N^2}{f^2}$ for all $f|N$.

My question is simply this - can these all be deduced from the square roots of unity mod $N$? Or do I need multiple invocations of my root finder?

-
I don't understand your description of "what I really want". –  Hurkyl Jan 18 '13 at 14:06
Given arbitrary N, I want a set of roots modulo every (N/f)^2. The motivating problem is an algorithm that solves Pell eqn x^2 - Dy^2 = N^2. I'm trying to determine if I can avoid having to invoke the root-finder for every f that divides N. –  Jim White Jan 18 '13 at 14:40

If $N$ is odd, then every root of unity modulo $N^2 / f^2$ is equivalent (modulo $N^2 / f^2$) to a root of unity modulo $N^2$.

This can be seen by observing there are two roots of unity modulo any $p^k$, and each contributes a factor of 2 to the number of roots. (So no roots of unity are "lost" when passing from $N^2 / f^2$ to $N^2$)

The even case is, well odd. IIRC, there are four roots of unity modulo $2^k$ for $k > 2$. Two of them: $1$ and $-1$ are persistent as $k$ grows. The other two are always $\pm 1 + 2^{k-1}$, which cannot extend to roots of unity modulo $2^{k+1}$.

However, it's probably easier to organize your program to work one prime at a time then CRT, in which case you don't have to worry about the fact $2$ is weird.

-
Thank you. The reason my question is stated the way it is, by the way, is that my root finder doesn't use CRT at all, it's a rather clever method by Omami/Ouni that produces a generating set for the group of roots. So in order to take your advice I'll have to abandon it and work with the classic algorithm after all. –  Jim White Jan 18 '13 at 15:00
If you want to stick to your approach, you can still split the problem into "power of 2" and "odd", and handle the odd case the way you like, but combine the even and odd parts with the CRT. –  Hurkyl Jan 18 '13 at 15:01
We'll see. I've got both methods implemented, so perhaps it's easier to rework the CRT method. Ironically, the gen-set method is lightning fast wrt identifying a gen-set, but all its advantage is then lost, generating the actual root set is non-trivial. The net effect is that both methods take on average about the same time. The gen-set is not guaranteed to contain the smallest non-trivial root, so no shortcuts there, either! –  Jim White Jan 18 '13 at 15:14
Yes, it seems that for odd M, then N = M, 2M and 4M are ok, simply a matter of looking at roots of N^2 mod (N^2/f^2). It's only multiples of 8 that fail, as we'd expect, I think. –  Jim White Jan 18 '13 at 17:31
Yes, it seems that for odd M, then N = M, 2M and 4M are ok, simply a matter of looking at roots of $N^2 \mod{N^2/f^2}$. It's only multiples of 8 that fail, and it's only for even $f$ values that it fails. –  Jim White Jan 18 '13 at 17:38

You'll get a set of square roots of 1 modulo $p^n$ for each prime $p$ such that $p^n$ is the highest power of $p$ dividing $N$, combine them by the chinese remainder theorem to get the full set.

-
Ok, let's assume my root finder uses the "classical algorithm", finding roots mod p^n, then you are saying I should just extend the second phase, the CRT phase, to include all the additional desired moduli N^2/f^2? –  Jim White Jan 18 '13 at 14:46