алгоритм Ленстры-Ленстры-Ловаса

Автор темы rakshas (Валентин) 
ОбъявленияПоследний пост
ОбъявлениеHuawei - Research scientist (math)22.06.2021 11:25
ОбъявлениеРазделу «Задачки и головоломки» исполнилось два года21.08.2021 01:51
ОбъявлениеГранты для студентов и аспирантов мехмата и физфака МГУ на обучение в магистратуре Кембриджа 2022/202314.10.2021 12:28
08.06.2003 15:23
алгоритм Ленстры-Ленстры-Ловаса
Может быть есть люди знакомые с алгоритмом Ленстры-Ленстры-Ловаса, у которых есть идеи, знания, или готовые материалы о том, как совместить его с р-адическими числами. Буду признателен за ссылки по теме или советы. Очень надо.
08.06.2003 20:31
А что конкретно имеется в виду?
subj

Насколько я понимаю, L^3 называют два алгоритма: обычно так говорят про алгоритм разложения полиномов над Z, иногда про lattice basis reduction. Имеется в виду разложение полиномов над кольцом p-адических чисел?

09.06.2003 09:53
имеется в виду lattice basis reduction
Это усложняет ситуацию? Насколько я понимаю, у на с в стране этим p-дическим анализом занимается максимум человек сто :(
13.06.2003 16:19
Панкратьев Е.В.
L^3 и факторизация
В общих чертах применение L^3 алгоритма для разложения многочленов на множители над Z, используя p-адические числа, выглядит следующим образом.
Общая схема (без L^3 алгоритма):
(1) выбираем полное нормированное поле (комплексных, вещественных или p-адических чисел)
(2) раскладываем наш многочлен на неприводимые множители над выбранным полем с достаточно высокой точностью (оценки конструктивные)
(3) перебираем сочетания неприводимых многочленов до тех пор, пока не получим произведение с целыми коэффициентами.

p-адические числа предпочтительнее, поскольку, как правило, количество неприводимых множителей (следовательно, и перебор) меньше.

Алгоритм факторизиции для случая p-адических коэффициентов основан на алгоритме Берлекэмпа (начальное приближение) и гензелевом подъеме (аналог метода Ньютона)
Сложность остается полиномиальной от степени исходного многочлена из-за перебора.

Использование L^3 алгоритма позволяет поднимать только один неприводимый множитель. Достигнув нужной точности (есть конструктивные оценки), применением L^3 алгоритма можно получить неприводимый над Z множитель, делящийся на поднимаемый множитель над O_p[x] (или C[x], R[x]).
Сложность получается полиномиальная, но на реальных задачах уступает варианту с перебором.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти