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