Неприводимый многочлен

многочлен, не разлагающийся на множители более низкой степени. Возможность разложить многочлен на множители (и свойство неприводимости) зависит от того, какие числа допускаются в качестве коэффициентов многочлена. Так, многочлен x³ + 2 неприводим, если в качестве коэффициентов допускать только рациональные числа, но разлагается в произведение двух Н. м.

25. НОД (a,b) – самое большое число, которое делит a и b

26. Линейными коэнгурентными генераторами называются генераторы псевдослучайных последовательностей следующего вида:

Где - n-й член последовательности. Параметры a, b, m представляют собой константы: a – это множитель, b – это приращение, m – модуль.

Их преимущество – это быстродействие, так как они не требуют небольшое число операций на бит. В криптологии их не используют, так как их выход не предсказуем.

Квадратичные генераторы:

27. Регистр сдвига представляет собой последовательность битов (длина регистров сдвига выражается числом битов. Если длина регистра n, то n-битовый регистр сдвига). При каждом извлечении бита, все биты регистра сдвигаются на 1 позицию вправо. Новый старший бит рассчитывается как функция от всех остальных битов регистра. Период регистра сдвига – длина получаемой последовательности до начала ее повторения.

Регистр сдвига с линейной обратной связью – простейший регистр сдвига с обратной связью. Обратная связь представляет собой просто операцию XOR над некоторыми битами регистра, перечень этих битов – последовательность отводов.

Выходной последовательностью регистра будет строка младших значащих битов: 111101011001000…

Степень многочлена, образованного из последовательности отводов регистра является длиной регистра сдвига.

Потоковые шифры на основе регистров сдвига легко реализуются с помощью цифровой аппаратуры.

28. Максимальный период линейной псевдослучайной последовательности, полученной с использованием n - разрядного регистра, равен 2ⁿ -1. Такие последовательности называют последовательностями максимальной длины, или m - последовательностями. Необходимым (но не достаточным) условием получения m - последовательности является неприводимость порождающего многочлена – неразложимость на действительные множители.

29. Псевдослуча́йная после́довательность (ПСП) — последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи.

Хотя псевдослучайная последовательность в этом смысле часто, как может показаться, лишена закономерностей, однако, любой псевдослучайный генератор с конечным числом внутренних состояний повторится после очень длинной последовательности чисел. Это может быть доказано с помощью принципа Дирихле.

30. Множество всех чисел, сравнимых с a по модулю n называется классом вычетов a по модулю n, и обычно обозначается [ a ] _n или . Таким образом, сравнение равносильно равенству классов вычетов [ a ] _n = [ b ] _n.

Поскольку сравнение по модулю n является отношением эквивалентности на множестве целых чисел , то классы вычетов по модулю n представляют собой классы эквивалентности; их количество равно n. Множество всех классов вычетов по модулю n обозначается или .

Операции сложения и умножения на индуцируют соответствующие операции на множестве :

• [ a ] _n + [ b ] _n = [ a + b ] _n
• 
• Относительно этих операций множество является конечным кольцом, а если n простое — конечным полем.

32. Просто́е число́ — это натуральное число, которое имеет ровно два натуральных делителя (только 1 и самого себя)без остатка. Все остальные числа, кроме единицы, называются составными. Таким образом, все натуральные числа большие единицы разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы.

33. Составно́е число́ — натуральное число бо́льшее 1, не являющееся простым. Каждое составное число является произведением двух натуральных чисел, бо́льших 1.

Последовательность составных чисел начинается так:

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, … (последовательность A002808 в OEIS)

Любое составное число может быть единственным способом разложено в произведение простых множителей.

34. Шифр (от араб. صِفْر ‎‎, ṣifr «ноль», откуда фр. chiffre «цифра»; родственно слову цифра), код — совокупность алгоритмов криптографических преобразований (шифрования), отображающих множество возможных открытых данных на множество возможных зашифрованных данных, и обратных им преобразований. Важным параметром любого шифра является ключ — параметр криптографического алгоритма, обеспечивающий выбор одного преобразования из совокупности преобразований, возможных для этого алгоритма. В современной криптографии предполагается, что вся секретность криптографического алгоритма сосредоточена в ключе, но не деталях самого алгоритма (принцип Керкгоффса).

Содержание [убрать]

• 1 Типы шифров
• 2 Асимметричные шифры
• 3 Симметричные шифры
• 3.1 Блочные шифры
• 3.2 Потоковые шифры

// [править] Типы шифров

Шифры могут использовать один ключ для шифрования и дешифрования или два различных ключа. По этому признаку различают:

• Симметричный шифр использует один ключ для шифрования и дешифрования.
• Асимметричный шифр использует два различных ключа.

Шифры могут быть сконструированы так, чтобы либо шифровать сразу весь текст, либо шифровать его по мере поступления. Таким образом существуют:

• Блочный шифр шифрует сразу целый блок текста, выдавая шифротекст после получения всей информации.
• Поточный шифр шифрует информацию и выдает шифротекст по мере поступления, таким образом имея возможность обрабатывать текст неограниченного размера используя фиксированный объем памяти.

Естественно, что блочный шифр можно превратить в поточный, разбивая входные данные на отдельные блоки и шифруя их по отдельности.

Также существуют не используемые сейчас подстановочные шифры, обладающие в своём большинстве, слабой криптостойкостью.

35. Говорят, что два целых числа a и b сравнимы по модулю натурального числа n, если при делении на n они дают одинаковые остатки.

Эквивалентные формулировки: a и b сравнимы по модулю n, если их разность a - b делится на n, или если a может быть представлено в виде a = b + kn, где k — некоторое целое число.

• Пример: 32 и −10 сравнимы по модулю 7, так как 32 = 7∙4 + 4, −10 = 7∙(-2) + 4.

Утверждение «a и b сравнимы по модулю n» записывается в виде:

Дата добавления: 2017-02-01