Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
I don't understand your description of "what I really want". – Hurkyl Jan 18 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 at 14:40

2 Answers

up vote 0 down vote accepted

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.

share|improve this answer
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 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 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 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 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 at 17:38
up vote 1 down vote

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.

share|improve this answer
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 at 14:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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