Схема Шнорра

[simpleAlin]

Добрый день.
Для реализации эцп по схеме Шнорра необходимо выбрать числа:
$p$ – простое число, $q$ – простое число, такое что $q|(p-1) $
$a$ - элемент, такой что $a^q = 1 \mod p$
Подскажите, пожалуйста, алгоритм решения этого сравнения или литературу, в которой можно его найти.
В той литературе, которая у меня на руках, рассматриваются лишь существование решения для общего случая, либо только количество корней такого частного, а как решать - не понятно.

[Sonic86]

Так, т.е. $p,q$ Вы уже выбрали и Вам надо найти все $a$?
В таком случае, находите образующую по модулю $p$ (для этого на практике достаточно проверить порядка $O(\ln ^2p)$ первых простых чисел на то, являются ли они первообразными по модулю $p$ (по критерию Лемера - просто по определению)). Пусть $g$ - первообразная. Тогда $a:a\equiv g^{k\frac{p-1}{q}}\pmod p, k=1,...,p$ - все искомые решения.