После выбора p встает задача выбора n и вычисление первообразного корня степени n. Пусть g – первообразный корень степени 
. В качестве n можно выбрать любой делитель p-1, больший чем m+k. Первообразный корень степени n можно получить путем возведения в степень 
по модулю p. Используя равенства 
и 
, легко предложить алгоритм вычисляющий требуемую величину с трудоемкостью не более 
.
Приведем алгоритм возведения g в степень t.
1. Положим s=g, a=1.
2. Если t четно, то положим 
и t:=t/2. Иначе положим 
, t:=(t-1)/2, .
3. Если t не 0, то повторим шаг 2. В противном случае ответ находится в ячейке a.
