Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Квадратичные сравнения по модулю степени простого числа
СообщениеДобавлено: 07 авг 2013, 17:51 
Не в сети
Начинающий
Зарегистрирован:
07 авг 2013, 17:46
Сообщений: 5
Cпасибо сказано: 1
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Доброго времени суток!

Для простого 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.)
Более того, подобные сравнения практически нигде не упоминаются, а если и упоминаются, то не объясняется их решение.
Собственно вопрос: каким образом можно решать подобные сравнения или как их свести к сравнению по простому модулю?
Заранее спасибо всем откликнувшимся!

Проверял здесь Онлайн решение сравнений по модулю

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Квадратичные сравнения по модулю степени простого числа
СообщениеДобавлено: 07 авг 2013, 18:12 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Пусть [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] произвольно. Именно поэтому решение таких сравнений обычно затруднения не вызывает. Но где-то я про них видел что-то. Ну в крайнем случае сами поковыряетесь - это интересно и просто :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Sonic "Спасибо" сказали:
Alexdemath, miramentis
 Заголовок сообщения: Re: Квадратичные сравнения по модулю степени простого числа
СообщениеДобавлено: 07 авг 2013, 22:44 
Не в сети
Начинающий
Зарегистрирован:
07 авг 2013, 17:46
Сообщений: 5
Cпасибо сказано: 1
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Да, действительно, все очень просто. Жаль, что я это сам нигде не нашел...
Спасибо Вам огромное за помощь и за спасенные часы моего времени!

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 3 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Сравнения любой степени по простому модулю

в форуме Теория чисел

Potato

5

731

09 ноя 2014, 10:31

Количество делителей, равное степени простого числа

в форуме Размышления по поводу и без

Xenia1996

0

359

25 мар 2018, 00:11

Остаток числа в степени по модулю

в форуме Теория чисел

nad27

2

593

10 дек 2019, 23:33

Решение сравнения по модулю

в форуме Теория чисел

MisterOrange

1

321

20 авг 2019, 13:27

Решение сравнения по простому модулю

в форуме Теория чисел

Alexey000

19

997

29 янв 2017, 19:27

Решение степенного сравнения по простому модулю

в форуме Теория чисел

maxkor

2

276

22 ноя 2018, 13:09

Простое как сумма простого и степени 2

в форуме Теория чисел

uporov1952

4

541

21 янв 2016, 16:57

Представление простого числа

в форуме Алгебра

mdauletiyarov

3

91

21 окт 2023, 17:44

Сравнения первой степени

в форуме Алгебра

PETPO

3

419

07 фев 2019, 13:27

Остаток от деления простого числа

в форуме Интересные задачи участников форума MHP

Xenia1996

7

818

19 окт 2019, 00:30


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved