|
|
Долго объяснение наверное будет, но попробую.
Вообще лобовой метод следующий.
Полином должен быть с одной стороны неприводимым, т.е. не иметь делителей, с другой стороны должен быть делителем полинома X^M+1.
M, в свою очередь, это 2^N-1. N - длина регистра (степень искомого полинома). Т.е. M - длина последовательности.
В общем найти все делители полинома X^M+1 и проверить их на простоту.
Одним из делителей этого полинома всегда будет X+1, кстати.
Но это мне кажется утомительно и долго.
Я делал по другому.
Известно, что число отводов обратной связи всегда четно,
Полиномы имеют вид X^N+...+1. Отводы обратной связи - степени X, к-т при которых=1, X^0=1 в полиноме- не отвод.
Полиному можно поставить в соответствие дв. число разрядностью N+1, пронумеровав, номера разрядов этого числа соответствуют степеням X в полиноме. В остальных разрядах 0.
В итоге искать следует среди дв. чисел нечетных и больших 2^N.
Из этого множества оставлять только те, в которых четное число 1 в разрядах 1-N.
Дальше учесть то, что если X^N+...+1 полином M-последов, то
X^N*(X^-N+...+1) тоже будет полиномом M-последовательности, такой же длины, но другой. В выражении в скобках полином по отриц. степеням.
В обшем отобранное множество дв. чисел с учетом этого можно еще ополовинить.
В результате получается некое множество дв. чисел.
Каждому числу ставится в соответствие полином и проверяется на простоту. Возможные делители полинома имеют макс. степень N-1.
А минимальную - 1, причем полином единичной степени только один и он X+1. Если кандидат на полином M- последов. не делится на X+1, значит он не делится и на любой полином степени N-1.
Далее. Полиномов второй степени всего 2. X^2+1 и X^2+X+1.
Причем X^2+1=(X+1)*(X+1) - Галуа, однако.
Т.е. далее проверка на делимость на полином X^2+X+1.
Если не делится, то автоматом вылетают все возможные делители степени N-2. Ну и т.д.
Примерно так.
Я давно писал генерацию, еще на DEC, в 80-х годах, на ассемблере.
И вроде для ускорения в качестве кандидатов на искомый полином брал в первую очередь простые числа из отобранного (выше) множества дв. чисел, но точно не скажу.
Кстати, вчера в ответе Сергею Борщу я немного лопухнулся, сегодня там же покаялся.
Ну и если Вам нужно - могу выслать полиномы.
Онм у меня все начиная с 4-ой степенью, кончая 24. с 25 по 32 не все.
Я видимо утомился их генерировать и ограничился относительно небольшим числом. Вчера С. Борщу выслал.
А полиномы 3 и 4 степени наверное и так всем известны.
E-mail: 
info@telesys.ru
