Компьютерная безопасность и криптография

Сложность последовательности по Колмогорову [Kolmogorov complexity] —под сложностью последовательности v по Колмогорову понимают наименьшую длину последовательности и, перерабатываемой некоторым алгоритмом (машиной Тьюринга) в последовательность v. Понятие предложено А. Н. Колмогоровым для алгоритмического определения понятий случайности и количества информации. Другие подходы к определению сложности и случайности разрабатывали Р. Соло-монофф, П. Мартин-Леф и др. В криптографии алгоритмические подходы к определению случайности находят применение при построении и анализе свойств генераторов последовательностей псевдослучайных криптографически сильных. См. также энтропия алгоритмическая.

Сложность последовательности 2-адическая [2-adic complexity] — под 2-адической сложностью бесконечной периодической двоичной последовательности v понимается величина Iog2(max(|p|,| q|), где p/q — несократимая дробь, у которой 2-адическое представление совпадает с последовательностью v.

Сложность линейная последовательности [linear complexity] — для последовательности над кольцом R — наименьшая длина регистра сдвига линейного над R, порождающего эту последовательность.

Сложность Лемпела—Зива последовательности [Lempel— Ziv complexity] — отношение объема словаря, построенного по последовательности символов алгоритмом сжатия Лемпела—Зива, к объему словаря, построенного по последовательности случайной идеальной. Понятие сложность Лемпела—Зива последовательности находит применение, например, при построении наборов тестов статистических.

Сложность (протокола) коммуникационная [communication complexity] —функция, выражающая зависимость максимального количества битов информации, пересылаемых в процессе выполнения распределенного алгоритма от длины записи исходных данных. С. к. —показатель эффективности реализации протоколов криптографических.

Сложность квадратичная последовательности [linear complexity] — для последовательности над кольцом R — наименьшая длина регистра сдвига над R с функцией обратной связи второй степени, порождающего эту последовательность.

Сложность алгоритма емкостная [space complexity] — функция, выражающая зависимость числа ячеек памяти, используемых в работе алгоритма, от длины записи исходных данных. Обычно рассматривается с. а. е. в худшем случае, то есть максимальное значение емкостной сложности по всем исходным данным одинаковой длины. Рассматривается также с. а. е. в среднем, то есть среднее значение сложности емкостной при случайном выборе исходных данных одинаковой длины.

Сложность алгоритма временная [time complexity] — функция, выражающая зависимость числа элементарных операций, производимых при работе алгоритма, от длины записи исходных данных. Обычно рассматривается с. а. в. в худшем случае, то есть максимальное значение сложности временной по всем исходным данным одинаковой длины. Рассматривается также с. а. в. в среднем, то есть среднее значение сложности временной при случайном выборе исходных данных одинаковой длины.