Как можно ускорить нахождение i в выражении?

Question

[Александр Лях]

m - задаётся
d - задаётся
задача найти i
i^2 mod m = -d mod m
Как сделать быстрое нахождение того самого i?

Comments

[Александр Лях]

m - простое число. Пишу алгоритм Корначчи, помогите пожалуйста с написанием кода.

[xmoonlight]

Александр Лях, а формулу - можно скрином...

[AVKor]

Александр Лях,

Пишу алгоритм Корначчи

Чего?

[Алан Гибизов]

Александр Лях, а вы свой код покажите, и что не получается.

[Rsa97]

Формула выглядит как x₀² ≡ -d (mod m)
m - не обязательно простое число, требуется, чтобы d и m были взаимно простыми, то есть не имели общих делителей. Например, 4 и 9 - взаимно простые числа.
Для компьютерного алгоритма эту формулу (с учётом условия 1 ≤ d < m) можно представить как x₀² % m = (m - d) % m

[Александр Лях]

Rsa97, знаю, но проблема в том, что в простыми числам алгоритм Корначчи работает гораздо быстрее

[Александр Лях]

Rsa97, не проблема, а просто такой факт

[AVKor]

Александр Лях,

алгоритм Корначчи

вообще для другой задачи.

Answer 1

[shurshur]

Алгоритм Тонелли-Шенкса
Можно даже нагуглить пример на python

Comments

[Александр Лях]

он за log(n) работает?

[shurshur]

Александр Лях, в вики написано, что в среднем O(\ln^2p)