Отправлено SKov 19 мая 2004 г. 18:17 В ответ на: Мне СРОЧНО нужен алгоритм генерации примитивных полиномов, а лучше программа отправлено Makc 19 мая 2004 г. 07:23

-------------------------------------------------
От:Sergey Kovalev (s-kovalev@mail.ru)
Тема:Re: Генеpатоp слyчайных чисел.
View: Complete Thread (22 сообщений)
Original Format
Группы новостей:fido7.ru.embedded
Дата:2001-06-04 22:59:34 PST

VS> будь добр, поделись теорией для вычисления n и m для максимальных рядов,
VS> я давно хотел это знать (покрайней мере до n = 64) (спасибо заранее)
VS> думаю, что и коллеги не откажутся - кто-то м.б. использует
VS> в своей системе (emb) для защиты данных

Относительно "поделись теорией" - это хорошо сказано! Смешно.;)
Я могу, вот только зачем. И кто здесь это будет читать и разбираться?
Это же железная эха, для большинства (всех?) подписчиков
теория конечных полей ассоциируется с картофелем и сахарной свеклой.
В этом нет ничего плохого, т.к. невозможно знать все. И не надо.
Hо, если тебе сильно захочется разобраться с построением примитивных
многочленов, (а именно они порождают последовательности
максимального периода), начни c книжки
Питерсон, Уэлдон."Коды, исправляющие ошибки"
Там есть классификация всех многочленов степени до 34 включительно.
Прямо готовые таблицы. Там же есть писания способов
построения примитивных могочленов методами,
не требующими полного перебора.
Затем можно полистать двухтомник Лидл Р., Hидеррайтер Г. "Конечные поля"
Там есть (во втором томе) готовые таблицы примитивных
многочленов степени до 100 (!!)( Т-с-с-с.. Только никому...;)
Там же есть ссылки на статьи, в которых таблицы до 168-й степени, а также
работы, специально посвященные любимым тобой примитивным трехчленам.
Кстати, для справки, белые люди очень не любят использовать именно
трехчлены. Считается, что чем больше единиц в маске, которая ксорится с
регистром, тем лучше качество датчика. А уж сколько там единиц в маске -
это практически никак не влияет на скорость программной реализации датчика.
Для задач криптозащиты эти методы уже давно не используются, т.к.
считаются уж совсем "детскими". У последовтельностей максимальной
длины очень плохой линейный профиль, и состояние регистра и обратные
связи легко восстанавливаются всего по 2n битам на выходе этого регистра.
Если у тебя в будущем возникнет проблема построить датчик с длинным
периодом, рекомендую воспользоваться каким-либо вриантом конкатенации
двух(или более) коротких датчиков.
Т.е. если у тебя есть два датчика , то ты можешь, например, брать
поочередно биты то с одного, то с другого.
Если периоды этих датчиков взаимно просты, то общий период
такого датчика будет равнятся произведению их периодов.

>> т.е. только тупой поиск на компутере ? ;)

VS> иногда _тупое_ решение намного дешевле, чем красивое и правильное
VS> мне было важно вычислить m и _проверить_ - не повторяется ли функция,

Вот-вот! Я тоже с недоверием отношусь к эти ученым. Имхо, врут они все ;)
Вот в Hидеррайтере написано, что 1+x+x**63 - примитивный трехчлен!
Проверь! Я, конечно, не доживу, но некоторые молодые люди из эхи,
пожалуй, имеют хорошие шансы узнать результат твоей проверки методом
тупого перебора. Зато дешево и надежно ! ;))

VS> представь, сколько времени потребуется найти (возможно закрытую)
VS> литературу

Я так думаю, что теперь, после публикации здесь этих
сов. секретных данных, не только мы с тобой, но и вся эха будет
под большим колпаком у соответствующих органов ;)).
"Сядем усе" ! ;)
SK

SPb, 2001

---------------------------------------------------