Есть ли способ найти дискретный корень?

Question

[Иван]

В статье на хабре есть странная формула
Разве есть быстрый способ найти корень по модулю? Вроде есть только сведение к дискретному логарифму (и притом только при простом p) или тупой перебор. Или это какая-то хитрая операция, отличная от принятого определения корня по модулю?

Answer 1

[AVKor]

Это квадратный корень в кольце (в данном случае - поле, поскольку p - простое число) классов вычетов по модулю p. Про нахождение корня google://quadratic residue

Answer 2

[Labunsky]

А можно и на русском
Зовется это алгоритмом Шенкса