|
Доброго времени суток! n - любое натуральное задан 7 Авг '13 19:55 
miramentis |
|
По условию, $%p > 2$% -- простое число, и $%n$% не делится на $%p$%. Найдём решения сравнения $%x^2\equiv n\pmod{p^b}$% индукцией по $%b$%. При $%b=1$% корни (их два, и они отличаются знаком) находятся либо подбором, либо при помощи упомянутого выше алгоритма. Пусть теперь $%b > 1$%, и корни квадратичного сравнения по модулю $%p^{b-1}$% уже найдены. Обозначим через $%x_0$% один из таких корней; он нам известен. По условию, $%x_0^2-n$% кратно $%p^{b-1}$%; положим $%x_0^2=n+p^{b-1}y_0$%, где число $%y_0$% мы также знаем. Обозначим через $%x$% какое-то из решений сравнения $%x^2\equiv n\pmod{p^b}$% -- при условии, что такое решение имеется. Тогда $%x^2-x_0^2=(x-x_0)(x+x_0)$% делится на $%p^{b-1}$%. Легко видеть, что оба сомножителя не могут быть кратны $%p$%. Тогда один из них делится на $%p^{b-1}$%. Можно считать, что это $%x-x_0$%, так как решение $%x$% мы вправе заменить на $%-x$%. Итак, $%x-x_0=p^{b-1}t$%, где $%t$% -- неизвестное целое число. Ясно, что $%x^2=(x_0+p^{b-1}t)^2=x_0^2+2x_0tp^{b-1}+p^{2b-2}$%. Последнее слагаемое делится на $%p^b$%. Далее, $%x^2\equiv n\pmod{p^b}$% после упрощений будет означать, что $%2x_0tp^{b-1}\equiv-y_0p^{b-1}\pmod{p^b}$%, то есть достаточно решить линейное сравнение $%2x_0t\equiv-y_0\pmod p$%. Его решение существует и единственно, так как $%2x_0$% не делится на $%p$%. Решая его, находим $%t$%, откуда $%x$% находится с точностью до знака. отвечен 8 Авг '13 23:35 
falcao Спасибо большое за подробный ответ!
(8 Авг '13 23:44)
miramentis
@falcao Можно ли составить обобщенный алгоритм решения квадратичных сравнений типа $%{x^2} \equiv N\,\,\,({\text{mod }}P)$%, где $%P$% - простое число и $%N \ne 0,\,\,\,P = {p^k},\,\,\,{\text{gcd(}}N,P) = 1$% используя лемму Гензеля?
(9 Ноя '14 22:00)
night-raven
@void_pointer: для простых чисел всё делается при помощи символов Лежандра, а потом можно просто подставлять. Возможно, при переходе от простых чисел к степеням можно применять какие-то общие конструкции или факты, но я, к сожалению, не могу по этому поводу ничего сказать.
(9 Ноя '14 22:14)
falcao
|
|
Если известен корень х для степени к, то корень х1 для степени к+1 вычисляется очень легко по простой формуле x1=x− F'(x)*F(x)/p^k (mod p). Работает с многочленами любой степени и для любого натурального р>1 (правда, при р=2 иногда надо сделать подстановку для изменения четности коэффициентов полинома). А в приведенной выше методике кроме ограничений значений р и степени многочлена надо еще вычислять обратный элемент (например, расширенным алгоритмом Евклида), а также несколько раз степень по модулю. отвечен 5 Сен '17 5:15 
Андрей13neo @Андрей13neo: это опечатка. Там должно быть p^{2b-2}t^2. Но это слагаемое в любом случае равно нулю по модулю p^b, то есть оно исчезает.
(5 Сен '17 12:33)
falcao
|
|
При р=2 алгоритм глючит. отвечен 26 Мар '18 2:58
Андрей13neo Здесь p > 2 по условию. Рассматриваются символы Лежандра по модулю p.
(26 Мар '18 3:40)
falcao
Так, а как же тогда решать при p=2?
(2 Апр '18 4:49)
Андрей13neo
@Андрей13neo: это совсем отдельная техника.
(2 Апр '18 14:13)
falcao
@Андрей13neo: я предлагаю перенести это обсуждение в тот отдельный вопрос, который Вы недавно задали.
(2 Апр '18 18:02)
falcao
Здесь нельзя писать два ответа, поэтому я отредактировал свой первый ответ.
(5 Апр '18 3:21)
Андрей13neo
|