Моделирование

													Рис.13
1	1	0	0	0	0
2	1	1	0	0	0
3	1	1	1	0	0
4	1	1	1	1	0
5	1	1	1	1	1
6	0	1	1	1	1
7	1	0	1	1	1
8	0	1	0	1	1
9	1	0	1	0	1
10	0	1	0	1	0
11	0	0	1	0	1
12	1	0	0	1	0
13	1	1	0	0	1
14	0	1	1	0	0
15	0	0	1	1	0
														1	0	1	1	1	0
16	0	0	0	1	1									2	0	0	1	1	1
17	1	0	0	0	1									3	1	0	0	1	1
18	0	1	0	0	0									4	0	1	0	0	1
19	0	0	1	0	0		1	1	1	0	1	1		5	1	0	1	0	0
20	0	0	0	1	0		2							6
								0	1	1	0	1			1	1	0	1	0
21	0	0	0	0	1									7
							3								1	1	1	0	1
								1	0	1	1	0
22	1	0	0	0	0		4	1	1	0	1	1		8	0	1	1	1	0
		T1 = 21							T2 = 7							T3 = 3
T = 21 + 7 + 3 = 31

АКФ.

f(x) = x3 + x + 1 Рис.16

1	0	1	0
2	1	0	1
3	1	1	0
4	1	1	1
5	0	1	1
6	0	0	1
7	1	0	0
8	0	1	0

0111001

1011100

r= 3−7 4 =−71 τ=1 r= 3−7 4 =−71 τ=2

r= 2−n−11 ; τ≠0 ; τ≠2n−1 r=1; τ=0 ; τ=2n−1

M-1-последовательность

T = 2n – 2

Рис.14

f(x) = x4 + x3 + 1

1	1	0	0	0
2	0	1	0	0
3	1	0	1	0
4	0	1	0	1
5	0	0	1	0
6	1	0	0	1
7	1	1	0	0
8	0	1	1	0
9	1	0	1	1
10	1	1	0	1
11	1	1	1	0
12	0	1	1	1
13	0	0	1	1
14	0	0	0	1
15	0	0	0	0
16	1	0	0	0

Рис.15

f(x) = x4 + x3 + x2 + 1

1	1	0	0	0
2	0	1	0	0
3	0	0	1	0
4	1	0	0	1
5	1	1	0	0
6	1	1	1	0
7	1	1	1	1
8	0	1	1	1
9	1	0	1	1
10	1	1	0	1
11	0	1	1	0
12	0	0	1	1
13	0	0	0	1
14	0	0	0	0
15	1	0	0	0

A)SSIGN – оператор для изменения параметров транзакта.

A)SSIGN 1,1

A)SSIGN TYP,2

SA)VEVA)LUE 1,P1+ P1+, 1

Свойства:

1.Запрещённая комбинация — чередование нулей и единиц.

2.Вероятности появления нуля или единицы одинаковы, равны 0,5.

3.Сложение по модулю два двух сдвинутых друг относительно друга M-1- последовательностей даёт новую последовательность, не являющуюся M-1- последовательностью.

Конгруэнтные ГПСЧ

Линейные конгруэнтные генераторы Общая схема линейных конгруэнтных генераторов была предложена Д.Г. Лехмером в 1949 году.

Сформируем последовательность {xxn} в соответствии с алгоритмом xn+1 = (a xn + b) mod m, где xn+1 – следующий элемент последовательности;

m — модуль, m>0;

a – множитель, 0 <= a < m b – приращение, 0 <= b < m 0 <= xn < m

m = 11 a = 5 b = 3 x0 = 4

x1 = (5*4 + 3) mod 11 = 1

x2 = (5*1 + 3) mod 11 = 8

x3 = (5*8 + 3) mod 11 = 10

x4 = (5*10 + 3) mod 11 = 9

x5 = (5*9 + 3) mod 11 = 4

Максимальный период конгруэнтного генератора равен M.

Линейная конгруэнтная последовательность, определённая числами m, a, b, xn, имеет период тогда и только тогда, когда:

1.Числа b и m взаимно простые

2.a-1 кратно p для каждого простого p, являющегося делителем m

3.a-1 кратно четырём, если m кратно четырём.

m = 32 a = 5 b = 7 x0 = 4

x1 = (5*4 +7) mod 32 = 27

x2 = (5*27 + 7) mod 32 = 14

x3 = (5*14 + 7) mod 32 = 13

x4 = (5*13 + 7) mod 32 = 8

x5 = (5*8 + 7) mod 32 = 15

x6 = (5*15 + 7) mod 32 = 18

x7 = (5*18 + 7) mod 32 = 1

x8 = (5*1 + 7) mod 32 = 12

x9 = (5*12 + 7) mod 32 = 3

x10 = (5*3 + 7) mod 32 = 22

x11 = (5*22 + 7) mod 32 = 21

x12 = (5*21 + 7) mod 32 = 16

x13 = (5*16 + 7) mod 32 = 23

x14 = (5*23 + 7) mod 32 = 26

x15 = (5*26 + 7) mod 32 = 9

x16 = (5*9 + 7) mod 32 = 20

x17 = (5*20 + 7) mod 32 = 11

x18 = (5*11 + 7) mod 32 = 30

Частным случаем классического линейного конгруэнтного генератора является т. н. мультипликативный генератор, если в формуле классического генератора

xn+1 = (a xn + b) mod m b = 0.

Тогда его формула равна: xn+1 = (a xn) mod m

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

(a – 1)S = 0 mod m (a – 1)S mod m = 0

Утверждается, что последовательности с потенциалом 5 и выше обладают достаточно хорошими статистическими свойствами.

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