Построение однонаправленных функций на основе возведения в степень в модульной арифметике

Возведение очень большого числа A в очень большую степень x по любо-му модулю M (), то есть вычисление является не-сложной задачей для ЭВМ. Однако решение обратной задачи — нахождения степени x по известным у, A, M такой, что (задача дискретного логарифмирования,), практически не разрешима за приемлемое время на современных ЭВМ (эффективного алгоритма вычисления дискретного логарифма пока не найдено). Поэтому модульная экспонента является однонаправленной функцией.

Регистр сдвига и линейные рекуррентные последовательности

Регистр сдвига с линейной обратной связью (РСЛОС, англ. Linear feedback shift register, LFSR) — регистр сдвига битовых слов, у которого входной (вдвигаемый) бит является линейной булевой функцией состояния остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами и применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии.

В регистре сдвига с линейной обратной связью выделяют две части (модуля): собственно регистра сдвига и схемы (или подпрограммы) вычисляющих значение вдвигаемого бита. Регистр состоит из функциональных ячеек (или битов машинного слова или нескольких слов), в каждой из которой хранится текущее состояние одного бита. Количество ячеек, называют длиной регистра. Биты (ячейки) обычно нумеруются числами, каждая из которых способна хранить бит, причём в ячейку происходит вдвижение вычисленного бита, а из ячейки извлекается выдвигаемый очередной сгенерированный бит. Вычисление вдвигаемого бита обычно производится до сдвига регистра, и только после сдвига значение вычисленного бита помещается в ячейку .

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

Для РСЛОС функция обратной связи является линейной булевой функцией от состояний всех или некоторых битов регистра. Например, сумма по модулю два или её логическая инверсия является линейной булевой функцией (операция XOR, в формулах обозначают как) и наиболее часто применяется в таких регистрах.

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

Управление регистром в аппаратных реализациях производится подачей сдвигающего импульса (иначе называемого тактового или синхроимпульса) на все ячейки, в программных — выполнением программного цикла, включающего вычисление функции обратной связи и сдвига битов в слове.

Линейной рекуррентной последовательностью (линейной рекуррентной) называется всякая числовая последовательность, задаваемая линейным рекуррентным соотношением:

для всех.

с заданными начальными членами, где n — фиксированное натуральное число, — заданные числовые коэффициенты,. При этом число n называется порядком последовательности.

Линейные рекуррентные последовательности иногда называют также возвратными последовательностями.