Доброго времени суток!
Для простого 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 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×552

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

показан
2009 раз

обновлен
9 Ноя '14 22:14

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

по почте:

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

по RSS:

Ответы

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

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