Кpиптогpафия от папиpуса до компьютеpа



Рекуррентные двоичные последовательности - часть 6


или пятое, а через сто лет в 1883 году русский самоучка Первушин нашел уже шестое число Мерсенна, равное:

     2**61-1 =2305843009213693951.

Самое большое известное сейчас простое число - так называемое 32-е число Мерсенна, найденное лишь в 1992 году. Его запись содержит 227832 десятичные цифры или примерно сто страниц текста.
     Нахождение неприводимых многочленов для генерации гаммы представляет сложную вычислительную задачу. Неприводимые многочлены, с помощью которых фактически строятся поля Галуа для криптографии, по своей роли напоминают простые числа в натуральном ряду. Нахождение их, как и простых чисел, производится подбором и требует больших затрат вычислительных мощностей сверхбыстродействующих ЭВМ. Поэтому в открытых публикациях данные о неприводимых многочленах очень больших степеней просто отсутствуют. Отметим, что всегда с(n)=с(0)=1, так как используется неприводимый многочлен степени п. Сложность програ1ммной реализации генератора существенно зависит от числа ненулевых коэффициентов неприводимого многочлена f(x): чем их меньше, тем проще и быстрее программа. Заметим, что в этом случае и криптоаналитикам проще жить: известно, что у них есть секретные теоремы, касающиеся трехчленов. Поэтому практически применяются многочлены с довольно большим числом ненулевых членов. Четного числа ненулевых членов быть не может, так как в этом случае корнем будет х=1 и многочлен можно разделить на х+1, а это доказывает приводимость.




Содержание  Назад  Вперед