Информационная безопасность / Информационная безопасность2006

Программные датчики. Общая модель

Исходные величины фиксируются заранее и называются стартовыми величинами.

Линейные рекуррентные формулы

Мультипликативный конгруентный метод (метод вычетов)

–натуральные числа – параметры программного датчика.

Эта ПСП зацикливается, начиная с некоторого номера i=T. Её период, равный Т, не превосходит М-1.

Пусть М = 2^q,q– количество бит целой константы ПК. Тогда:

T_max= 2^q^-2=M/4 достигается, если:

1) – нечётное число, причём;

2) mod8 = 3mod8 илиmod8 = 5mod8.

Это условие выполняется, например, при = 5²^p⁺¹,p= 0,1,2,… , или когда= 2^m+ 3,m= 3,4,5,…

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

Для получения максимального периода следует брать М = 2ⁿи использовать= 2^q+ 1,q2,C– нечётное и– произвольное. Хоффман рекомендует выбиратьиз условияmod4 = 1.

Методы, использующие нелинейные рекуррентные формулы

Метод середины квадрата.

Параметры датчика: kи. Заметим, что– число, образованное средними 2kбитами 4k-разрядного двоичного числа.

Модификация метода – метод середины произведения.

Квадратичный конгруентный метод (обобщение линейного).

Параметры датчика: .

Если М = 2^qиq2, то наибольший период

Т_max=M= 2^qдостигается, если, С – нечётные,– чётное, причём

Метод Маклорена-Марсальи.

Метод основан на комбинации двух простейших датчиков. Пусть {b_i} и {c_i},i= 0,1,2,… есть ПСП, порожденные двумя независимо работающими датчикамиD₁иD₂соответсвенно. АV= {V(0),V(1), …,V(k-1)} – вспомогательная таблица изkцелых чисел.

Сначала таблица Vзаполненаkчленами ПСП {b_i}, т.е.V(j) =b_j,j= 0,1,2,…,k-1.

Результирующая ПСП получается в результате следующей последовательности действий:

s := Int(c_jk)

d_i := V(s) i = 1,2,…

V(s) :=b_i₊_k

Т.е. датчик D₂делает случайный выбор из таблицыV, а также случайно заполняет её числами, порождёнными датчикомD₁. Можно получить очень большой период ПСП, если периоды датчиковD₁иD₂– взаимно простые числа.

Содержание