умножение многочленов по модулю неприводимого многочлена

[GIM]

Здравствуйте, я хотела спросить:
существует ли алгоритм, который находит неприводимый многочлен n степени?

Мне нужно реализовать операцию умножения многочленов, представимых наборами из 0 и 1,
при этом реультат умножения надо брать по модулю многочлена степени n ,
то есть при умножении двух многочленов степени n , в результате будет многочлен степени не более чем (2n-2).а мне нужен многочлен степени не выше n.

САМ вопрос:
как мне строить неприводимые многочлены нужной степени?
при очень больших n ?

являются ли многочлены (x^n+1) или (x^n+x+1) неприводимыми

P.S. умножение является блоком схемы, которую мне надо построить.
Заранее СПАСИБО!
с Уважением, GIM

Красный цвет --- модераторский: Правила форума

[Sonic86]

GIM писал(а):

Мне нужно реализовать операцию умножения многочленов, представимых наборами из 0 и 1

Это как? У Вас должны быть многочлены над $\mathbb{Z}_2$ или просто начальные коэффициенты из $\{ 0; 1\}$, а коэффициенты произведения могут быть любые целые? Если второй вариант, то Вам нужна книжка Лидл Нидеррайтер Конечные поля. Книжка большая, но простая.
Если же второй вариант (многочлены над $\mathbb{Z}$), то надо использовать другие критерии, например, критерий Эйзенштейна (другие не знаю).

GIM писал(а):

являются ли многочлены (x^n+1) или (x^n+x+1) неприводимыми

Многочлен $x^n+1$ приводим, догадайтесь как

Формулы обрамлять долларами! Посмотрите ссылку на тег math сверху! Иначе пойдете в карантин.

[GIM]

здравствуйте,
замечание поняла
само задание звучит так: построить схему для сложения 2 точек эллиптической кривой над полем Галуа $GF(2^n)$в булевом базисе.
при этом точки представлены как наборы 0 или 1, а операции сложения или умножения,нахождения обратного элемента этих точек надо выполнять как над многочленами.
операцию умножения мне надо сделать как блок, а с остальной частью я вроде разобралась.
чтобы после умножения многочлен бы степени не выше $n$ мне надо брать произведение по модулю неприводимого многочлена.т е $n$ .как мне построить сам этот многочлен...
прошу прощения, если некорректно поставила вопрос

[Sonic86]

Значит в $\mathbb{Z}_2$.
Тогда Вам нужен Лидл Нидеррайтер, у меня есть в djvu.
Там есть теоремы для числа неприводимых многочленов над полем и для их построения. Есть теорема-критерий неприводимости многочлена $x^p-x-a$ для поля $GF(p^n)$.
Хотя вроде это не то...

[GIM]

GIM писал(а):

являются ли многочлены (x^n+1) или (x^n+x+1) неприводимыми

Многочлен $x^n+1$ приводим, догадайтесь как


догадалась, т к ненулевых элементов четное число,следовательно корнем будет х=1 и многочлен можно разделить на х+1, а это доказывает приводимость.

-- Пн май 31, 2010 16:30:32 --

Sonic86 в сообщении #325876 писал(а):

Значит в $\mathbb{Z}_2$.
Тогда Вам нужен Лидл Нидеррайтер, у меня есть в djvu.
Там есть теоремы для числа неприводимых многочленов над полем и для их построения. Есть теорема-критерий неприводимости многочлена $x^p-x-a$ для поля $GF(p^n)$.
Хотя вроде это не то...

книжку я скачала,
я знаю про эту теорему,
не могли бы вы подсказать сам алгоритм нахождения неприводимого многочлена нужной степени.
а для конечного поля всегда существует многочлен n cтепени .
т к мне надо перемножать большие многочлены (степени более чем 123, ) то и неприводимые многочлены должны быть большой степени.
а перебором считать , очень сложно

[Sonic86]

GIM писал(а):

не могли бы вы подсказать сам алгоритм нахождения неприводимого многочлена нужной степени.
а для конечного поля всегда существует многочлен n cтепени .

Увы, я на самом деле в этом не рублю - но в книге есть, при наличии большого количества времени можно поразбираться.
М.б. Вам кто-то еще что-нибудь посоветует.

[maxal]

Ну вот для примера пара статей по теме:
http://www.shoup.net/papers/detirred.pdf
http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf

[Leox]

Посмотрите в Лидл Нидеррайтер должны быть критерии неприводимости трехчленов $x^n+x^m+1, n>m.$ Попробуйте при фиксированном n подобрать подходящее $m$ и получить неприводимый многочлен.