# upper bound on, or fast algorithm to find, an order $2^n$ element in the multiplicative group modulo prime $q(2^n)+1$

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.

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, 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$$.

• 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. – Greg Martin May 26 at 21:07
• @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$. – stanley dodds May 26 at 21:35