Хорошо, а чем плох (или, наоборот, хорош), такой подход: вот, мы же знаем, что
![$x,y$ $x,y$](https://dxdy-01.korotkov.co.uk/f/0/a/c/0acac2a2d5d05a8394e21a70a71041b482.png)
, - это лишь фасад, мираж, а
на самом деле рулят
![$v,R$ $v,R$](https://dxdy-03.korotkov.co.uk/f/2/e/7/2e7c0823236df564a16b46112b163afc82.png)
. Мы так же знаем, что
![$v^2\equiv R\pmod m$ $v^2\equiv R\pmod m$](https://dxdy-04.korotkov.co.uk/f/3/b/4/3b45e807576b3b7c42165346ef577b3a82.png)
, где
![$R$ $R$](https://dxdy-02.korotkov.co.uk/f/1/e/4/1e438235ef9ec72fc51ac5025516017c82.png)
принадлежит определенной последовательности и слишком большим быть не должно (тут конечно вопрос, что такое "слишком", и традиционное "когда остановиться?"). При этом, точность приближения тем лучше, чем больше величина
![$\sqrt{(m+v)^2-R}+\sqrt{(m-v)^2-R}$ $\sqrt{(m+v)^2-R}+\sqrt{(m-v)^2-R}$](https://dxdy-04.korotkov.co.uk/f/b/0/8/b084e75db79aabb74506c6a56cb5062c82.png)
, или, приближенно, чем меньше
![$\frac R{m^2-v^2}$ $\frac R{m^2-v^2}$](https://dxdy-01.korotkov.co.uk/f/8/9/e/89eef90855ca1004d49010e5d09113ac82.png)
. Тогда, для простого
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
, можно попробовать перебирать значения
![$R$ $R$](https://dxdy-02.korotkov.co.uk/f/1/e/4/1e438235ef9ec72fc51ac5025516017c82.png)
по возрастанию (причем, не все
![$R$ $R$](https://dxdy-02.korotkov.co.uk/f/1/e/4/1e438235ef9ec72fc51ac5025516017c82.png)
будут разрешены по соображениям взаимности) и в лоб извлекать из них корни по модулю
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
, - здесь же есть быстрые алгоритмы (не имел реального опыта реализации, но вот пишут:
Алгоритм Тонелли—Шенкса; есть некоторые оговорки, но, на первый взгляд, алгоритм не выглядит устрашающим/безнадежным). Если же нам еще больше повезло и
![$m=4d+3$ $m=4d+3$](https://dxdy-01.korotkov.co.uk/f/4/8/3/483418c16cbee6842a6479df1011ef3282.png)
, то это вообще сводится к задаче возведения в степень по модулю:
![$v\equiv\pm R^{d+1}\pmod{4d+3}$ $v\equiv\pm R^{d+1}\pmod{4d+3}$](https://dxdy-04.korotkov.co.uk/f/3/5/d/35d566beedd65427b5c367dca239bb7782.png)
, где точно быстрые алгоритмы есть. Хочу попробовать, когда будет чуть больше досуга, в ближайшую среду, видимо