многочлена первой степени:
Yn = Ent (a*n+b)
Если n пробегает значения натурального ряда чисел, то
поведение Yn выглядит весьма хаотичным. Еще Карл Якоби доказал,
что при рациональном коэффициенте а множество {Yn} конечно, а при
иррациональном бесконечно и всюду плотно в интервале от 0 до 1.
Для многочленов больших степеней такая задача была решена лишь в
1916 году выдающимся математиком нашего века Германом Вейлем.
Кроме того, он установил критерий равномерности распределения
любой функции от натурального ряда чисел. Небезынтересно привести
его в краткой формулировке.
КРИТЕРИЙ ВЕЙЛЯ. Чтобы ряд х1, х2, x3,... был распределен
равномерно в интервале от 0 до 1, необходимо и достаточно, чтобы
для любой интегрируемой по Риману функции f(x) было справедливо
соотношение P{<f(x)>=Mf(x)}=1.
Это соотношение выражает свойство, называемое эргодичностью и
заключающееся в том, что среднее по реализациям псевдослучайных
чисел равно среднему по всему их множеству с вероятностью 1.
Таким образом, Вейль доказал, что эргодичность гарантирует
отсутствие экзотичности в поведении последовательности Xn.
Однако эти результаты далеки от практики получения
псевдослучайных рядов чисел. Дело в том, что теорема Якоби
относится к действительным числам х и у, которые не могут быть
использованы при вычислениях, потому что иррациональные
действительные числа требуют для своей записи бесконечного числа
знаков. Попытки замены настоящего иррационального числа его
приближением на ЭВМ для генерации псевдослучайной
последовательности опасны, так как получаемые последовательности
оканчиваются циклами с коротким периодом. Завершают
доказательство непригодности полиномиальных и других
функциональных преобразований натурального ряда чисел для
получения псевдослучайных последовательностей результаты
Пуанкаре. В частности он установил, что непрерывное отображение Т
области U числового пространства в себя обязательно приводит к
короткой цикличности траекторий Tn(х) для всюду плотного в U
множества точек, если учитывать попадание траекторий точек в их
сколь угодно малые окрестности или ряды чисел, созданные таким
методом, отягчены периодичностями.
Несмотря на непригодность для криптографии простых
последовательностей чисел, рассмотрим все же самые
распространенные из них. Наиболее древний вычислительный способ
генерации псевдослучайных чисел на ЭВМ принадлежит Джону фон
Нейману и относится к 1946 году. Этот способ базировался на том,
что каждое последующее случайное число образуется возведением
предыдущего в квадрат и отбрасыванием цифр с обоих концов. Способ
Неймана оказался ненадежным и очень быстро от него отказались. Из
простейших процедур, имитирующих случайные числа, наиболее
употребляем так называемый конгруэнтный способ, приписываемый
Д.Х. Лемеру:
G(n+1)=KGn+C MOD M
В нем каждое последующее псевдослучайное число G(n+1)
получается из предыдущего Gn умножением его на К, сложением с С и
взятием остатка от деления на М. Весь фокус здесь в том, чтобы
подобрать хорошие значения К, С и М, на что были потрачены
десятилетия работы математиков. Подбор почти иррациональных К
ничего не дает. Например, выбрав закон генерации
последовательности G(N+1) = Ent (sqr(2)*Gn) на IBM PC при формате
представления чисел с плавающей запятой IEEE в 4 байта, получим
псевдослучайные ряды, обязательно заканчивающиеся циклами с
периодами длиной всего лишь 1225 и 147 в зависимости от
начального заполнения. Разумнее вычисления вести в целых числах.
Для них было установлено, что при С=0 и М=2**N наибольший период
М/4 достигается при K=3+8*i или K=5+8*i и нечетном начальном
числе. При достаточно больших К ряд производит впечатление
случайного. Насколько это верно читатель может выяснить
самостоятельно следующей программой:
'----------проверка случайности ряда чисел
DEFINT A-Z: SCREEN 2: CLS
n = 1
DO
nold = n: n = FnRnd% (n)
PSET (nold/64,CVL(MKI$(n)+MKI$(0))\512)
LOOP UNTIL n = 1
END
'----генерация ряда чисел с периодом 16384
DEF FnRnd% (n) =CVI(LEFT$(MKL$(1381&*n),2))
В ней случайность ряда проверяется отображением на экране
дисплея пар его чисел (Gn+1, Gn) в прямоугольнике размером 128 х
512. Это простой и удобный способ проверки случайности рядов
чисел, так как на глаз заметны малейшие закономерности в
получаемом орнаменте. Из опытов с этой программой можно
убедиться, что как ни экспериментируй с подбором К, все равно
закономерности видны и чисто случайного рада чисел не получишь.
Вспомните ехидное предложение Додо "становиться строго в
беспорядке" из "Алисы в стране чудес". Результат можно несколько
улучшить. Если С нечетно и K=1+4*i, то период ряда равен М. После
долгих поисков К исследователи остановились на значениях 69069 и
71365. Кроме значений М=2**N широко используются выборы простых
М, например, простого числа М=2**31-1, известного со времен
Эйлера (Это число "плохо" тем, что в двоичной записи содержит
лишь единицы. Однако оно может использоваться, если вычисления
выполняются в десятичной арифметике.)
Однако обратимся к фактам. В 1948 году фон Нейман предложил
генератор псевдослучайных чисел, который через год подвергся
резкой критике. В 1972 году в пакете прикладных программ IBM 360
на языке Фортран появилась программа RANDU, а в 1977-м Форсайт
показал, что тройки ее последовательных значений лежат на 15
параллельных плоскостях. В 1979 году Скраг опубликовал компактный
алгоритм генерации псевдослучайных чисел, а через год Плаке
доказал его статистическую неудовлетворительность. Этому списку
нет конца: более месяца работы автор потерял из-за некомпетентно
сделанного генератора случайных чисел в системе М86 ЕС 1840,
который использовался для моделирования сложных процессов. В
журнале "Наука и жизнь" за октябрь 1986 года М. Максимов поместил
статью-предупреждение под названием "Случайны ли случайные
числа?", где совершенно справедливо отметил негодность
используемых генераторов. По его данным, генератор FRAN у БК-0010
имеет длину периода всего лишь 2**15, а бьет рекорды бессмыслицы
генератор Бейсика ДВК, который имеет период лишь 8192 и
последовательные тройки его "случайных" чисел, функционально
связанные уравнением Gn-6*G(n+1)+9*G(n+2), равны целым числам. Не
иначе, как от отчаяния, рад исследователей одновременно
использует два и даже три разных генератора, смешивая их
значения. Если разные генераторы независимы, то сумма их
последовательностей обладает дисперсией, равной сумме дисперсий
отдельных последовательностей. Иначе говоря, случайность рядов
возрастает при их суммировании. Это дает слабую надежду на
возможность конструирования генератора с приемлемыми для
криптографии свойствами: случайностью и большой длиной периода.
Заметим, что некоторые "запутывания" последовательностей
псевдослучайных чисел лишь ухудшают их статистические свойства.
Далеко не всегда сложность формирования рада порождает
случайность распределения. Например, генератор случайных чисел из
игровой программы неизвестного происхождения для программируемого
калькулятора использовал в качестве случайных чисел первые цифры
последовательности {83**K}. Легко доказывается, что такой
генератор будет на 14% чаще давать цифру 7, чем 8. В литературе
приводится громадное количество формул для генерации случайных
рядов, и автору довелось испытать их не один десяток, но, не то
чтобы хорошей, а даже удовлетворительной по статистическим
свойствам найти не удалось. Сдается, что часть подобных способов
генерации случайных рядов предложена в качестве шутки
криптографами, желающими упростить себе работу. Однако в системах
программирования обычно используют все же конгруэнтные генераторы
по алгоритму, предложенному Национальным бюро стандартов США,
который, имея длину периода 2**24, обеспечивает очень неплохие
статистические свойства. К сожалению, длина его периода для
криптографии слишком мала и, кроме того, было доказано, что
последовательности, генерируемые конгруэнтными генераторами, не
являются криптографически стойкими. Если дана часть такой
последовательности достаточной длины, то ее параметры могут быть
восстановлены.
Интересный класс генераторов случайных чисел неоднократно
предлагался многими специалистами целочисленной арифметике, в
частности Джорджем Марсалиа и Арифом Зейманом. Генераторы этого
типа основаны на использовании последовательностей Фибоначчи.
Классический пример такой последовательности {0, 1, 1, 2, 3, 5,
8, 13, 21, 34...}. За исключением первых двух ее членов, каждый
последующий член равен сумме двух предшествующих. Если брать
только последнюю цифру каждого числа в последовательности, то
получится последовательность чисел {0, 1, 1, 2, 5, 8, 3, 1, 4, 5,
9, 4...} Если эта последовательность применяется для начального
заполнения массива большой длины, то, используя этот массив,
можно создать генератор случайных чисел Фибоначчи с
запаздыванием, где складываются не соседние, а удаленные числа.
Марсалиа и Зейман предложили ввести в схему Фибоначчи "бит
переноса", который может иметь начальное значение 0 или 1.
Построенный на этой основе генератор "сложения с переносом"
приобретает интересные свойства, на их основании можно создавать
последовательности, период которых значительно больше, чем у
применяемых в настоящее время конгруэнтных генераторов. По
образному выражению Марсалиа, генераторы этого класса можно
рассматривать как усилители случайности. "Вы берете случайное за-
полнение длиной в несколько тысяч бит и генерируете длинные
последовательности случайных чисел". Однако большой период сам по
себе еще не является достаточным условием. Слабые места гамм
бывает трудно обнаружить и аналитику требуется применять
утонченные методы анализа последовательностей, чтобы выделить
определенные закономерности, которые скрыты в большом массиве
цифр.
Последнее, на чем следует остановить внимание, это
особенности использования стандартных генераторов случайных чисел
в различных языках программирования, если уж ими пришлось
воспользоваться. Так отметим, что известный в Бейсике оператор
RANDOMIZE (Он такой же, как и во всех других языках
программирования. например. Pascal или C++.), применяемый для
начальной установки генератора случайных чисел, может ошарашить
пользователя. Ибо после выполнения:
RANDOMIZE 231
х = RND
RANDOMIZE 231
у = RND
необязательно получится х=у, потому что оператор RANDOMIZE
переустанавливает не всё случайное число из 3 байт, а лишь его
часть из 2 байт. Точная установка может быть произведена функцией
RND, как x=RND(-231). Не нужно думать, что эта проблема
встречается лишь при программировании на Бейсике. Паскаль и Си
всех фирм дают те же результаты. А вот увеличение периода
последовательности сделать несколько сложнее. Для этого можно
использовать функцию:
FUNCTION Rand (х, у)
х = RND (-х)
у = RND (-у): IF у = О THEN у = RND (-у)
Rand = (х+у) MOD 1
END FUNCTION
Период такой функции равен 2**24-(2**24-1), но вот свойства
его ряда не обязаны при любых исходных х и у быть такими же
хорошими, как у RND.
При создании с помощью встроенного генератора случайных чисел
объектов, имеющих число состояний большее, чем у генератора, его
приходится использовать несколько раз, переустанавливая по
заранее заданному ключу. Например, следующий фрагмент программы:
FOR i = 1 ТО 5
х = RND (-gamma (i))
FOR j = 0 TO 32
SWAP map (j), map (32 * RND)
NEXT: NEXT
производит случайную перестановку 33 элементов массива map,
которая может быть сделана примерно 2**118 способами, и при длине
периода генератора в 2**24, его нужно запустить не менее 5 раз,
чтобы реализовать все варианты перестановки.
Рекуррентные двоичные последовательности
Изложим теперь способ построения последовательностей
случайных чисел с гарантировано хорошими для криптографии
свойствами. Читатели, не интересующиеся практикой криптографии
или стохастического моделирования, могут спокойно опустить эту
подглавку и перейти к следующей. Для тех, кто решит все-таки
изучить ее, сделаем несколько замечаний. Автор не рассчитывал на
серьезную математическую подготовку читателей - в подавляющем
большинстве институтов и университетов страны курс теории
конечных полей если и читается, то лишь факультативно. Поэтому
систематичности и строгости изложения ожидать не приходится. Цель
- освоение принципов программной реализации хороших рядов
псевдослучайных чисел, что достигается приведением аналогов и
разбором конкретных примеров. Тем не менее, программисты
по-видимому будут удовлетворены приведенной детальностью
изложения, а ценители математической строгости могут уточнить
неясные для себя вопросы, обратившись к книге "Современная
прикладная алгебра" Г. Биркгоф и Т. Барти (Москва, "Мир", 1976)
или же анналам математики Бурбаки.
По определению сложности закона генерации ряда чисел, если
сложность последовательности {Gi} равна m, то любые m+1
последовательные ее значения зависимы. Если же эта зависимость
представима линейной, то получается рекуррентное соотношение
следующего вида:
C0*Gi+C1*G(i-1)+...+Cm*G(i-m)=0
При этом C0 и Cm обязаны быть неравными нулю. По начальным
данным Go, Gi,... Gm-1 длины m строится бесконечная
последовательность. Каждый ее последующий член определяется из m
предыдущих. Последовательности такого вида легко реализуются на
ЭВМ. Особенно простой вид их реализации получается когда все с, и
д, принимают лишь значения 0 и 1, что соответствует значениям
отдельных бит. На множестве таких чисел определены алгебраические
операции сложения и умножения, то есть имеется поле из двух
элементов. Поля указанного типа с конечным числом элементов
называются по фамилии их первооткрывателя Эвариста Галуа и для
поля с n элементами обозначаются как GF(n), где GF - аббревиатура
от слов Galois Field (поле Галуа). Они существуют, лишь когда n
равно простому числу, и тогда называются простыми, или степени
простого числа, и тогда называются расширениями соответствующего
простого поля. Так, поле из 2 элементов GF(2) - простое поле
порядка 2, a GF(4) - его расширение. При вычислениях на ЭВМ
используются поля Галуа из элементов {0, 1}, обозначаемые
GF(2**N) и соответствующие строкам данных длиной в N бит. Таблицы
арифметических операций в GF(2) будут следующими:
+ 0 1 * 0 1
0 0 1 0 0 0
1 1 0 1 0 1
На ЭВМ такому сложению соответствует операция XOR, уже
известная нам по машинному шифру ручной замены, а умножению -
операция AND. Это поле обладает замечательным свойством -
операция вычитания в нем тождественна операции сложения и в
записях не употребляется. Поля бит, как байт или слово, можно
представить векторами, каждая компонента которых принимает
значения из GF(2). Такие вектора удобно рассматривать как
многочлены. Байт, например, можно представить многочленом седьмой
степени, каждый член которого соответствует одному ненулевому
биту в байте:
(10010101)=x**7+x**4+x**2+1
Представление битовых полей данных в ЭВМ многочленами
упрощает рассмотрение операции их сдвига. Сдвигу данных влево на
один бит соответствует умножение многочлена на х, а вправо -
деление на х.
Совокупность всех многочленов степени меньше n представляет
собой векторное пространство размерности n над GF(2), так как
многочлены можно складывать, вычитать или умножать на константу.
Теперь, фиксировав неразрешимый над GF(2) многочлен f(x)
степени n+1, рассмотрим остатки от деления на него других
многочленов. Их множество совпадает с множеством многочленов
степени не больше n. Например, f(x)=x**2+x+1 над GF(2)
неприводим, потому что f(0)=1 и f(1)=1. Для него остатками будут
элементы {0, 1, х, х+1}. На множестве этих остатков можно задать
арифметические операции сложения и умножения, рассматривая
остатки от деления на многочлен f(x). Легко проверить, что
определенные таким образом сложение и умножение обладают всеми
необходимыми свойствами обычных арифметических операций:
коммутативностью, ассоциативностью и дистрибутивностью. Результат
сложения или умножения над двумя элементами из приведенного
множества тоже ему принадлежит. И, наконец, в множестве
определены О и 1 так, что для произвольного элемента х имеем
0+х=х и 1*х=х. Таким образом, получено GF(4) - расширение поля
GF(2) присоединением к нему остатков от деления произвольных
многочленов на неприводимый над ним многочлен х**2+х+1. Выбирая
разные неприводимые многочлены, можно получать разные расширения
GF(2).
Из школьного курса математики известно, что над полем
комплексных чисел любой многочлен разложим на линейные множители
или, что то же самое, имеет столько корней, какова его степень.
Однако это не так для других полей - в полях действительных или
рациональных чисел многочлен х**2+х+1 корней не имеет и не может
быть разложен на линейные множители. Аналогично, в поле GF(2)
многочлен х**2+х+1 тоже не имеет корней, что просто проверить
непосредственно: 1*1+1+1=1 и 0*0+0+1 =1. Тем не менее у
f(x)=x**2+x+1 в поле Галуа GF(4) существует корень х,
соответствующий многочлену х из таблиц выше, так как f(x)= х**2
+х+1 по модулю f(x).
Элементы поля Галуа GF(2**N) относительно умножения образуют
абелеву группу, то есть на этом множестве для любых его элементов
х, у и z выполняются аксиомы:
x*y=y*x*x*(y*z)=(x*y)*zx*1=1*xx*1/x=1/x*x=1
Если рассмотреть степени произвольного элемента х из
GF(2**N), то обнаружим, что они образуют абелеву подгруппу. Такие
подгруппы принято именовать циклическими. Число элементов этой
подгруппы называют порядком элемента х. Из такого определения
порядка следует, что если многочлен р(х) принадлежит GF(2**N) и
имеет порядок k, то р(х)**K=1. Разберем теперь несколько важных
свойств, касающихся порядка элементов в GF(2), изложенных в виде
теорем.
ТЕОРЕМА 1. Если f(x) - неприводимый многочлен над GF(2), то
выполняется равенство f(x**2)=f(x)**2.
Это равенство доказывается тем, что все попарные произведения
в f(x)**2 равны нулю над GF(2). Например,
(х**2+х+1)**2=х**4+x**2+1.
ТЕОРЕМА 2. Если неприводимый многочлен f(x) над GF(2**N) имеет
порядок k, то k делит 2**N-1.
Это следует из теоремы Лагранжа, утверждающей, что число
элементов группы G делится на число элементов любой своей
подгруппы Н. Подгруппа Н расслаивает группу G на смежные классы
элементов, не пересекающиеся меж собой. Так, элементы х и у
считаются принадлежащими одному классу по подгруппе Н, если у/х
принадлежит Н. Поскольку классы не пересекаются и содержат
одинаковое число элементов, то число элементов группы делится на
число элементов в подгруппе. Из теоремы 2 вытекает важное
следствие, что если 2**N-1 простое число, то мультипликативная
группа GF(2**N) циклическая и порядок любого ее неединичного
элемента тоже равен 2**N-1.
ТЕОРЕМА 3. Любой многочлен р(х) из GF(2**N) удовлетворяет
уравнению х**k=х, где К=2**N.
Порядок ненулевого р(х) делит 2**N-1 и имеем х**(K-1)=1, а
так как для р(х)=0 имеем уравнение х=0, то в результате любой
р(х) удовлетворяет уравнению х**K=х.
Отметим особое положение уравнения х**K=х, где К=2**N,
поскольку его корни порождают все элементы поля GF(2). Так как
уравнение х**(K-1)-х=0 имеет корнем х=0, то, разделив его на х,
получаем уравнение х**(K-1)-1=0, все корни которого ненулевые.
Производная уравнения имеет вид (x**k-x)=2*N*x**(n-1)-1=1, и у
нее нет общих корней с исходным уравнением. Следовательно, в этом
уравнении все корни различны, и так как их число равно 2**n, то
они совпадают со всеми элементами поля GF(2).
ТЕОРЕМА 4. Многочлен х**k-1 делит х**M-1 в том и только в том
случае, если k делит M.
Это вытекает из того факта, что если все корни х**k-1
являются также и корнями х**m-1, то m должно делиться на k.
Теперь обратимся к использованию полиномов в практике
вычислений на ЭВМ, широко распространено и легко реализуется
программно. Рассмотрим электронную схему деления данных в поле из
N бит на полином:
f(x) = C0+C1*x+...+ Cn*х**N
N N-1 3 2 1
┌─┐ ┌─┐ ┌─┐┌─┐ ┌─┐
┌─────>┤+├>┤+├─────>────┤+├┤+├>┤+├──────┐
│ └┬┘ └┬┘ └┬┘└┬┘ └┼┘ │
└─┬───┬─┴─┬─┴─┬─────────┬┴─┬┴─┬─┴─<─────┘
└───┴───┴───┴─────────┴──┴──┴───┘
┌─┐
│+│ сумматор XOR
└─┘
┌─┐
│ │ регистр сдвига
└─┘
На схеме биты показаны квадратными клетками. Шаг процедуры
деления состоит в сдвиге данных влево на один бит и дозаписи
освобождающегося крайнего правого бита суммой значений бит по
модулю 2, умноженных на соответствующие коэффициенты многочлена
f(x), то есть не все ячейки сдвига соединены с относящимися к ним
сумматорами. В результате последовательного выполнения отдельных
шагов деления исходных данных а(х), справа в данные
дозаписывается последовательность s(x), которая выражается
формулой:
s(x)=a(x)/f(x)=S0+S1*x+S2*x**2+...
справедливость которой просто проверить, приравнивая коэффициенты
при х в уравнении s(x)*f(x)=a(x). Таким образом, получена связь
между линейными рекуррентными последовательностями, делением
многочленов над GF(2) и алгоритмом реализации деления на ЭВМ.
Например, пусть имеем над GF(2) рекуррентное соотношение
Gi+G(i-1)+G(i-3)=0. Многочлен, который ему отвечает, равен
1+х+х**3. Это неприводимый многочлен над GF(2), который порождает
расширение GF(8). Мультипликативная группа в GF(8) имеет 7
элементов и циклична в силу простоты числа 7. Электронная схема
этого рекуррентного генератора представляется так:
3 2 1
┌─┐
┌─────>──────┼+├───────┐
│ └┬┘ │
│ ┌──┬────┬──┴──┐ │
└──┴──┴────┴─────<─────┘
Он будет генерировать следующие последовательности при разных
начальных данных (периоды в скобках):
000 => (0)
001 => (0011101)
010 => (0100111)
O11 => (0111010)
100 => (1001110)
101 => (1010011)
110 => (1101001)
111 => (1110100)
Рассмотрим теперь программную процедуру, реализующую деление
на примитивный неприводимый многочлен х**3+х+1 в поле Галуа
GF(8), представленную короткой программой на языке Бейсик.
Переменные в ней рассматриваются как целые числа.
'программа деления на многочлен х**З+х+1
DEFINT A-Z
n = 1
DO
m = О
'-----------расчет бита переноса
IF n AND 2^2 THEN m = m+1
IF n AND 2^0 THEN m = m + 1
n = 2 * (n AND (2^2-1)) OR (m AND 1)
LOOP UNTIL n = 1
END
В этой программе сдвиг влево заменен операцией умножения на
2, а бит переноса рассчитывается тестированием бит,
соответствующих ненулевым коэффициентам многочлена. В
соответствии с теорией период такого генератора составляет 7 и
включает в себя все ненулевые числа из 3 бит. Из этой программы
видно, что реализация процедуры деления многочленов на ЭВМ или,
что то же самое, генерации рекуррентных последовательностей
проста.
Особый интерес для генерации длинных последовательностей
представляют элементы GF(2**N), имеющие порядок равный 2**N-1.
Они называются примитивными, потому что, возводя их в степень,
можно получить весь набор ненулевых элементов поля Галуа. Если
2**N-1 простое число, то все элементы мультипликативной группы
(кроме 1, конечно!) примитивны. Однако такие числа, называемые
простыми числами Мерсенна, расположены редко. Они с давних пор
слыли чемпионами среди простых чисел по своему размеру. Во время
Эйлера наибольшим простым числом было:
2**31-1 =2147483647,
или пятое, а через сто лет в 1883 году русский самоучка Первушин
нашел уже шестое число Мерсенна, равное:
2**61-1 =2305843009213693951.
Самое большое известное сейчас простое число - так называемое
32-е число Мерсенна, найденное лишь в 1992 году. Его запись
содержит 227832 десятичные цифры или примерно сто страниц текста.
Нахождение неприводимых многочленов для генерации гаммы
представляет сложную вычислительную задачу. Неприводимые
многочлены, с помощью которых фактически строятся поля Галуа для
криптографии, по своей роли напоминают простые числа в
натуральном ряду. Нахождение их, как и простых чисел,
производится подбором и требует больших затрат вычислительных
мощностей сверхбыстродействующих ЭВМ. Поэтому в открытых
публикациях данные о неприводимых многочленах очень больших
степеней просто отсутствуют. Отметим, что всегда с(n)=с(0)=1, так
как используется неприводимый многочлен степени п. Сложность
програ1ммной реализации генератора существенно зависит от числа
ненулевых коэффициентов неприводимого многочлена f(x): чем их
меньше, тем проще и быстрее программа. Заметим, что в этом случае
и криптоаналитикам проще жить: известно, что у них есть секретные
теоремы, касающиеся трехчленов. Поэтому практически применяются
многочлены с довольно большим числом ненулевых членов. Четного
числа ненулевых членов быть не может, так как в этом случае
корнем будет х=1 и многочлен можно разделить на х+1, а это
доказывает приводимость.
Последовательности максимальной длины
Дата добавления: 2015-08-28; просмотров: 27 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |