1
$\begingroup$

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.

$\endgroup$

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.