Дискретная математика и криптология



СТРУКТУРА И ПЕРИОДЫ ПРЕОБРАЗОВАНИЙ - часть 7


свободных позициях окружности всех n различных элементов множества X. Число различных таких размещений равно числу различных перестановок элементов n-множества, то есть, равно п!.

В то же время, перестановки элементов эквивалентны, если отличаются лишь параллельным сдвигом, так как представляют один и тот же цикл преобразования. Следовательно, множество всех построенных циклов разбивается на классы эквивалентных циклов, где в каждом классе содержится по п циклов. Таким образом, число п.ц. преобразований п-множества равно числу неэквивалентных циклов, то есть (п-1)!.                                                                                                                                        ¨

Пример 6.2. Линейный конгруэнтный генератор (ЛКГ).

Пусть Еk - кольцо вычетов по модулю k, j - преобразование ЛКГ множества Еk, если для любого хÎЕk:

j(x)=(a×x+b)modk,

где a, b и k – константы из Еk, называемые множителем, сдвигом, и модулем соответственно.

ЛКГ имеет период не более k. Для любых k и x имеются константы a и b, при которых tj=k. Такие генераторы называют ЛКГ полного (или максимального) периода. Приведём без доказательства следующую теорему [61].

Теорема 6.5.

Преобразование ЛКГ имеет период k Û:

1)          (b,k)=1;

2)          a-1 кратно любому простому делителю числа k;

3)          a-1 кратно 4, если k кратно 4.                                                                           

В частности, если k=2r, то tj=2r тогда и только тогда, когда

b - нечётное число и аº1(mod4).

Теорема 6.6.

Биективное преобразование j n-множества X является п.ц. тогда и только тогда, когда для любого отличного от константы отображения y:X®Y, где êYê³2, отображения y и y×j различны.

Доказательство. Пусть для п.ц. преобразования j множества X, для любого xÎX




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