Find a primitive $k$-th root of unity $w$ modulo some prime $p$, where $k\geq a$ and $p\geq b$ where $a,b$ are chosen constants.

After looking online, I know I can find such values from tables, e.g. see here. But to hand does anyone know of an algorithm or theorem or something which can produce the required $w, p, k$? (Perhaps this is a tall order and I'm not that familiar with abstract algebra so apologies if that's the case)

Example: Suppose $p>3$ and we require $k\geq 5$, then from the table I can see that $p=7$ so that $w\in\{3,5\}$ and $k=6$ will satisfy the conditions.

Update: After a bit more searching I found this which seems to make use of the Charmichael function. Also found this. Looks like it's difficult without any conditions! Oh well.


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.