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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Алгоритм вычисления корней по модулю простого числа
СообщениеДобавлено: 03 мар 2012, 22:12 
Не в сети
Начинающий
Зарегистрирован:
03 мар 2012, 14:51
Сообщений: 28
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте!
У меня возникли неясности с алгоритмом вычисления корней по модулю простого числа, алгоритм описан на странице 153 в http://www.ksu.ru/f9/bibl/Monograph_ishm.pdf.
Пункт два вообще не понятен, как произошло такое разложение и что там вообще происходит на примере. Комментариев минимум и вопрос остался открытым. Поясните пожалуйста более подробно этот алгоритм.
Заранее спасибо.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Алгоритм вычисления корней по модулю простого числа
СообщениеДобавлено: 04 мар 2012, 06:20 
Не в сети
Последняя инстанция
Аватара пользователя
Зарегистрирован:
29 окт 2010, 11:15
Сообщений: 2715
Cпасибо сказано: 112
Спасибо получено:
833 раз в 666 сообщениях
Очков репутации: 198

Добавить очки репутацииУменьшить очки репутации
Там общеизвестное понижение степени многочлена.
Простое замечание. Если [math]f(x)[/math] и [math]g(x)[/math] имеют общий корень, то этот же корень имеет и многочлен [math]u(x)f(x)+v(x)g(x)[/math]
Основываясь на этом замечании получаем, что для двух многочленов [math]f(x)[/math] и [math]g(x)[/math], имеющих общий корень, тот же корень имеет их НОД.
Теперь если взять произвольный многочлен [math]f(x)[/math] и в пару с ним [math]g(x)=x^p-x[/math], корнями которого являются все элементы [math]\mathbb Z_p[/math], то осюда получим, что НОД этой пары имеет в точности те же самые корни, что и [math]f(x)[/math]. Если [math]f(x)[/math] не является делителем [math]g(x)=x^p-x[/math], то их НОД имеет меньшую степень, чем [math]f(x)[/math] и задача нахождения корней несколько упрощается.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю dr Watson "Спасибо" сказали:
Alexdemath, mad_math
 Заголовок сообщения: Re: Алгоритм вычисления корней по модулю простого числа
СообщениеДобавлено: 04 мар 2012, 20:53 
Не в сети
Начинающий
Зарегистрирован:
03 мар 2012, 14:51
Сообщений: 28
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
спасибо, вроде появляется понимание, но не до конца:
а зачем нам надо менять параметр b.
и правильно ли я задался вопросом по нахождению НОД многочлена со сдвинутым аргументом
http://mathhelpplanet.com/viewtopic.php?f=32&t=15120

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

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

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

registration

0

175

29 сен 2021, 21:49

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

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

mdauletiyarov

3

91

21 окт 2023, 17:44

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

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

Xenia1996

7

818

19 окт 2019, 00:30

Ни одного простого числа (Всеросс 2006, модификация)

в форуме Задачи со школьных и студенческих олимпиад

Xenia1996

5

622

28 авг 2017, 16:04

И снова ни одного простого числа (из далёкого 2001г)

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

Xenia1996

1

369

09 сен 2017, 16:19

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

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

Xenia1996

0

359

25 мар 2018, 00:11

Номер простого числа и его связь с степенью двойки

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

Login V

4

517

25 фев 2017, 20:25

Алгоритм поиска корней по Бренту.

в форуме Численные методы

Monk0712

0

347

13 окт 2014, 17:35

Машина Тьюринга.поиск простого числа (с моим решением)

в форуме Дискретная математика, Теория множеств и Логика

zero2hack

1

674

13 июн 2014, 16:29

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

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

nad27

2

593

10 дек 2019, 23:33


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



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

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


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

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

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

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