Доброго времени суток!
Для простого p ( такого что символ Лежандра (n/p)=1 )
нужно решить уравнение
$%x^2 ≡ n (mod p^b)$%

n - любое натуральное
В интернете достаточно большое количество материала по квадратичным сравнениям по простому модулю.
если $%b=1$%, то мы можем воспользоваться алгоритмом Шенкса-Тонелли. Подробно и с примером о нем здесь (начиная со страницы 34).
Но, к сожалению, если модуль - степень простого, то данный алгоритм не срабатывает.
(К примеру, при $%n=112093$% и $%p=11^2$% мы не сможем вычислить порядок элемента lambda0.)
Более того, подобные сравнения практически нигде не упоминаются, а если и упоминаются, то не объясняется их решение.
Здесь(страница 59) описан алгоритм подъема решения, но вся фишка в том, что он работает для некоторой функции, не зависящей от b. можно перекинуть остаток от деления n по модулю p^b в левую часть и решить. НО. При увеличении степени b остаток от деления n по модулю $%p^b$% будет изменяться. И, выходит, что одно решение нельзя "поднять", так как полиномы всегда разные". Так что, я не представляю, как это алгоритм использовать.
Собственно вопрос: каким образом можно решать подобные сравнения или как их свести к сравнению по простому модулю?
Или как можно изменить алгоритм поднятия решения, дабы он подошел к моему случаю ?
Заранее спасибо всем откликнувшимся!

задан 7 Авг '13 19:55

изменен 9 Авг '13 14:23

10|600 символов нужно символов осталось
1

По условию, $%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

Спасибо большое за подробный ответ!
К сожалению сам я, в учебниках, да и, вообще, в интернете я данный материал не нашел...

(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) void_pointer

@void_pointer: для простых чисел всё делается при помощи символов Лежандра, а потом можно просто подставлять. Возможно, при переходе от простых чисел к степеням можно применять какие-то общие конструкции или факты, но я, к сожалению, не могу по этому поводу ничего сказать.

(9 Ноя '14 22:14) falcao
10|600 символов нужно символов осталось
0

Если известен корень х для степени к, то корень х1 для степени к+1 вычисляется очень легко по простой формуле x1=x− F'(x)*F(x)/p^k (mod p). Работает с многочленами любой степени и для любого натурального р>1 (правда, при р=2 иногда надо сделать подстановку для изменения четности коэффициентов полинома). А в приведенной выше методике кроме ограничений значений р и степени многочлена надо еще вычислять обратный элемент (например, расширенным алгоритмом Евклида), а также несколько раз степень по модулю.

ссылка

отвечен 5 Сен '17 5:15

изменен 5 Апр 10:10

@Андрей13neo: это опечатка. Там должно быть p^{2b-2}t^2. Но это слагаемое в любом случае равно нулю по модулю p^b, то есть оно исчезает.

(5 Сен '17 12:33) falcao
10|600 символов нужно символов осталось
0

При р=2 алгоритм глючит.

ссылка

отвечен 26 Мар 2:58

Здесь p > 2 по условию. Рассматриваются символы Лежандра по модулю p.

(26 Мар 3:40) falcao

Так, а как же тогда решать при p=2?

(2 Апр 4:49) Андрей13neo

@Андрей13neo: это совсем отдельная техника.

(2 Апр 14:13) falcao

@Андрей13neo: я предлагаю перенести это обсуждение в тот отдельный вопрос, который Вы недавно задали.

(2 Апр 18:02) falcao

Здесь нельзя писать два ответа, поэтому я отредактировал свой первый ответ.

(5 Апр 3:21) Андрей13neo
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×680

задан
7 Авг '13 19:55

показан
2891 раз

обновлен
5 Апр 10:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru