Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 3 ] |
|
Автор | Сообщение | |
---|---|---|
miramentis |
|
|
Для простого p ( такого что символ Лежандра (n/p)=1 ) нужно решить уравнение x^2 ≡ n (mod p^b) где n - любое натуральное В интернете достаточно большое количество материала по квадратичным сравнениям по простому модулю. если b==1, то мы можем воспользоваться алгоритмом Шенкса-Тонеллиhttp://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm. Подробно и с примером о нем здесь (начиная со страницы 34)http://window.edu.ru/resource/980/73980/files/Monograph_ishm.pdf. Но, к сожалению, если модуль - степень простого, то данный алгоритм не срабатывает. (К примеру, при n=112093 и p=11^2 мы не сможем вычислить порядок элемента lambda_0.) Более того, подобные сравнения практически нигде не упоминаются, а если и упоминаются, то не объясняется их решение. Собственно вопрос: каким образом можно решать подобные сравнения или как их свести к сравнению по простому модулю? Заранее спасибо всем откликнувшимся! Проверял здесь Онлайн решение сравнений по модулю |
||
Вернуться к началу | ||
Sonic |
|
|
Пусть [math]x_b\colon x_b^2\equiv n\pmod{p^b}[/math], тогда [math]x_{b+1}\equiv x_b+p^bq_b\pmod{p^{b+1}}[/math]. Подставляя [math]x_{b+1}[/math] в сравнение с показателем [math]p^{b+1}[/math], получаем:
[math]n\equiv x_{b+1}^2\equiv x_b^2+2x_bp^bq_b\pmod{p^{b+1}}[/math] при [math]b>1[/math]. Последнее сравнение линейно относительно [math]q_b[/math], потому Вы можете найти [math]q_b[/math] по [math]x_b[/math], т.е. в итоге можете рекуррентно вычислять [math]x_{b+1}[/math] через [math]x_b[/math]. [math]x_1[/math] Вы можете найти по приведенным алгоритмам. Для разрешимости сравнения [math]F(x)\equiv A\pmod{p^b}[/math] по модулю [math]p^{b+1}[/math] нужно только чтобы [math]F'(x)\not\equiv 0\pmod p[/math], а вообще [math]F[/math] произвольно. Именно поэтому решение таких сравнений обычно затруднения не вызывает. Но где-то я про них видел что-то. Ну в крайнем случае сами поковыряетесь - это интересно и просто |
||
Вернуться к началу | ||
За это сообщение пользователю Sonic "Спасибо" сказали: Alexdemath, miramentis |
||
miramentis |
|
|
Да, действительно, все очень просто. Жаль, что я это сам нигде не нашел...
Спасибо Вам огромное за помощь и за спасенные часы моего времени! |
||
Вернуться к началу | ||
[ Сообщений: 3 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Сравнения любой степени по простому модулю
в форуме Теория чисел |
5 |
734 |
09 ноя 2014, 10:31 |
|
Количество делителей, равное степени простого числа
в форуме Размышления по поводу и без |
0 |
361 |
25 мар 2018, 00:11 |
|
Остаток числа в степени по модулю
в форуме Теория чисел |
2 |
593 |
10 дек 2019, 23:33 |
|
Решение сравнения по модулю
в форуме Теория чисел |
1 |
321 |
20 авг 2019, 13:27 |
|
Решение сравнения по простому модулю
в форуме Теория чисел |
19 |
997 |
29 янв 2017, 19:27 |
|
Решение степенного сравнения по простому модулю
в форуме Теория чисел |
2 |
277 |
22 ноя 2018, 13:09 |
|
Простое как сумма простого и степени 2
в форуме Теория чисел |
4 |
545 |
21 янв 2016, 16:57 |
|
Представление простого числа
в форуме Алгебра |
3 |
95 |
21 окт 2023, 17:44 |
|
Сравнения первой степени
в форуме Алгебра |
3 |
421 |
07 фев 2019, 13:27 |
|
Остаток от деления простого числа | 7 |
820 |
19 окт 2019, 00:30 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |