ПСП нулей и единиц (гамма).

Считается, что «гарантированно» хорошим для криптографии способом генерации является построение гаммы рекуррентным соотношением

×   + C × q

1 + ... + Cm × qi m = 0

(2)

Здесь и ниже обозначено: С и q – двоичные числа {0, 1}, а символом «+» обозначено сложение по модулю два (логическая операция XOR). Множество полиномов (2) составляет одно из полей Галуа, т.е. поле, над которым определено: сложение – операция XOR, вычитание – операция XOR, умножение – операция AND.

Коэффициенты С₀ и С_m обязаны быть равны 1. следовательно, очередное псевдослучайное число вычисляется по ф-ле:

qi  + ... + Cm

× qi -( m-1) + qi -m

(3)

Последовательность бит, например, байт или слово (два бита) удобно рассматривать как многочлены. Например, байт представляется полиномом 7-й степени, каждый член которого соответствует ненулевому биту в байте:

1001010 )     1

+ 0 ×

+ 0 × q5 + 1× q 4 + 0 × q3 + 1× q 2 + 0 × q1 + 1× q0 = q 7 + 4

2  1 =

f (q)

Применение полиномов упрощает рассмотрение операций с ПСП бит. Полином f(q) называют неприводимым, если:

f(0) = 1 и f(1) = 1    (4)

Другими словами, полином m-ой степени неприводим, если он не раскладывается на множители (полиномы) степени ниже m.

ПСП бит, вычисляемая по формуле (3), будет  иметь  максимальную  длину  периода, равную 2^m–1, если полином (2) неприводим.

Примеры неприводимых полиномов и соответственно рекуррентных соотношений (3). 3-го порядка:   1 + q + q³ = 0     q_i = q_i-1 + q_i-3

1 + q² + q³ = 0     q_i  = q_i-2 + q_i-3

4- го порядка:     1 + q + q⁴ = 0

1 + q + q² + q³ + q⁴ = 0

5- го порядка:     1 + q² + q³ + q⁴ + q⁵ = 0

11-го порядка:   1 + q⁹ + q¹¹ = 0   q_i = q_i-9 + q_i-11

Заметим, что все неприводимые полиномы имеют нечетное количество членов.