1
$\begingroup$

I have a program which (in its current implementation) requires, for a given $N=2^n$, some $\omega$ in some field such that $\omega^N=1$ and $\omega^i\ne1$ for each $0<i<N$.

Complex roots of unity are not viable, due to imperfect precision when represented in Cartesian form on a computer. Even if represented accurately in polar form, now it is addition of complex numbers which is slow and imprecise, requiring trigonometric functions.

The method that I have implemented is to first find a prime in the form $P=qN+1$ (which heuristically should be fast; we can "expect" to find such $q$ within $\mathcal{O}(\log (q_0N))$ of some $q_0$, and we can test candidate $P$ for primality quickly) and then work in the field of integers modulo $P$. Since $P$ is prime, is has a primitive root $g$, and hence $g^q$ has the desired properties. We therefore know that such $\omega$ does indeed exist in this field.

However, my best method for finding $\omega$ so far is to simply check $\omega=2,3,4,\dots$ (see edit for much better method for choosing trial $\omega$) for the property $\omega^{N/2}\equiv-1\mod P$ (which holds iff $\omega^N\equiv1$ and $\omega^i\not\equiv1$ for each $0<i<N$, since the only prime dividing $N$ is $2$). This works fine, but the problem is that I don't know if this is definitely fast, and there may be a better method.

For reasons that shouldn't be important, my program requires that $P\approx{N^2\over2}$, so a possible worst case may require checking $\mathcal{O}(N^2)$ candidates - this would be too slow. I therefore either need a good upper bound on the least such $\omega$, or a faster method of finding one.

The odd powers of $g^q$ cover exactly all such $\omega$. This is simple to prove by considering all cases for powers of $g$, which covers everything, as $g$ is a primitive root modulo $P$. Therefore we know there are exactly $N/2$ valid roots of unity, distributed among roughly $N^2\over2$ integers. Randomly searching will therefore take roughly $N$ checks on average. This is good, but the worst case is still $\mathcal{O}(N^2)$. Any method better than this, but preferably one taking at most $\mathcal{O}(N)$ time, would be great.

EDIT: I've realised there is quite a trivial algorithm that finds $\omega$ very quickly on average. Pick some $a$, then compute $a^q\mod P$. There is a 50% chance that this has order $N$. The reason is that $a\equiv g^k\mod P$ for some $k$. By the above, if $k$ is odd, then $a^q\equiv (g^q)^k\mod P$ has exactly order $N$ as required. $k$ is odd for half of the powers of $g$ (which are half the integers from $1$ to $P-1$), so each $a$ gives a 50% chance. Hence we now only expect to have to check 2 values on average. I would bet there is a proof somewhere that checking $2^q,3^q,\dots$ finds $\omega$ in a very small number of trials as a function of $N$ or $P$.

$\endgroup$
  • 2
    $\begingroup$ It's not clear whether you already see this, but the algorithm starting from $2$ should take $(N/2)$th powers of $2^q,3^q,\dots$, etc. Indeed, assuming an appropriate Riemann hypothesis, one only needs to check a polylog number of $\omega$ starting from $2$. You are basically finding a quadratic nonresidue $\omega$ modulo $P$, if you want to search the literature for more details. $\endgroup$ – Greg Martin May 26 at 21:07
  • $\begingroup$ @GregMartin $\omega$ is not necessarily a quadratic nonresidue, because $q$ is not necessarily odd, but yes, finding a quadratic nonresidue would immediately give $\omega$ by repeated squaring. And yes I see how to check each candidate, since that was my initial algorithm anyway. But thanks for the comment; I suppose it's fair to say that this will be fast for any $P$ small enough to be computed with, and most likely for all $P$. $\endgroup$ – stanley dodds May 26 at 21:35

Your Answer

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

Browse other questions tagged or ask your own question.