Лекция №4.

Генераторы псевдослучайных чисел и последовательных чисел (продолжение).

1 x_i+1 = (lx_i)mod m (*) –> [0, 1]

2 x_i+1 = (lx_i+C)mod m, где x₀, x_i, l, C, m – целые и положительные. Когерентный – мультипликативный.

0, 1, …, m-1

x_i+1 = j(x_i)

Элементы криптографии.

x_i+1

0 n

m-1

0 1

x_i+1=0, < x_i+1>

В эмпирических условиях:

Период l = 8i ± 3, i = 1, 2, 3…

Модуль m = p₁ – простое число, l = p₂, то формула (*) – есть перестановка.

Алгоритм:

1. lx_i, [0, m-1]

2. lx_i/m, к

3. x_i+1 = r – остаток

4. x_i+1 –> X_i+1, [0, 1]

Пример.

l = 3, n = 7, x₀ = 1

x₁ = (3*1)/7 –> 3

x₂ = (3*3)/7 –> 2

x₃ = (3*2)/7 –> 6

x₄ = (3*6)/7 –> 4

x₅ = (4*3)/7 –> 5

x₆ = (5*3)/7 –> 1

x₇ = (1*3)/7 –> это повтор (новый период).

[1-p-1] [1, 2, 3, 4, 5, 6]

m = 2ⁿ

m, m = 2ⁿ-1 = p (**)

Пример (**)

2²-1 = 3, x_i+1 = (lx_i)mod m

n =2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 21609

l = 65069

1. lx_i

2. lx_i+C

3. (lx_i+C)/m –> r – остаток

4. x_i+1 = r

x_i+1 = (lx_i+C)mod m = (l mod m*x_i mod m)*mod m = (r₁*r₂)*mod m

|(l mod m*x_i mod m+C mod m)| - окончательный результат.