Реализация простейшего генератора псевдослучайной последовательности (ПСП) в Matlab

Прошу прощения за большой перерыв в публикациях.

Псевдослучайные последовательности чисел используются в криптографии буквально во всех методах. Очевидно, что для ее родственницы - стеганографии они тоже имеют большую важность.

Псевдослучайная последовательность – это… последовательность т. е. ее элементы можно пронумеровать: 1, 2, 3, … В то же время, элементы последовательности не должны зависеть от своих соседей или соседей соседей, это значит что следующий элемент последовательности должен быть непредсказуем.

Реализуем простенький алгоритм генерации ПСП на MATLAB. Реализовывать будем предложенный Д.Г. Лехмером в 1949г. конгруэнтный генератор ПСП. (В викисловаре одно из значений слова «конгруэтный» обозначает свойство алгебраического объекта — быть связанным с другим алгебраическим объектом стабильным отношением эквивалентности на алгебраической системе).

Последовательность чисел данного ПСП генератора определяется формулой: Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:

данная последовательность определяется целочисленными коэффициентами a, c, m и начальным членом X(0). Максимально возможная длинна ряда порождаемого данным генератором равна m. При превышении данной длинны последовательность начнет повторять цикл «случайных» чисел. Чтобы длина последовательности была максимальной коэффициенты a, c и m должны подчиняться правилам:

1.      НОД(c,m) = 1 то есть, c и m взаимно просты (НОД - наибольший общий делитель. Например, для 12 и 20 НОД равен 4, что записывается как (12,20) = 4 . Наибольший общий делитель для взаимно простых чисел - 1)

2.      a-1 кратно p для всех простых делителей p числа m. Данное условие означает, что a-1 должно состоять как минимум из всех простых делителей числа, исключая их повторение. Например если число m = 450 =2*3*3*5*5, то a-1 может быть произведением 2*3*5=30 следовательно a = 31

3.      a-1 кратно 4, если m кратно 4. Данное условие означает, что если m делится на 4 без остатка, то значение a-1 так же должно делится на 4 без остатка.

Несоблюдение перечисленных правил резко (в 2-5 раз) сокращает длину псевдослучайной последовательности по сравнению с максимальной.

Привила 2 и 3 накладывают некоторые ограничения и на выбор числа m:

−        если число m простое, длинна ПСП будет меньше максимальной;

−        если m будет состоять из простых делителей, которые не повторяются, a-1 будет равно m. Например, если m = 2*3*5=30, невозможно подобрать такое a-1, которое меньше m и кратно всем простым делителям – 2 3 5;

−        аналогично не решает проблему наличие двух делителей равных 2 (см. правило 3). Например, нельзя подобрать a-1 для m = 2*2*3*5=60

Учитывая сказанное, для формирования ПСП максимальной длинны будем брать m кратным 8, тогда a-1 может быть равно произведению всех простых делителей кроме первой двойки. Например, если m = 2*2*2*3*5 =120, то a-1= 2*2*3*5 = 60. 


Простой Matlab скрипт реализует описанный ПСП - генератор:

function [X_PRS, O ] = psp( M )

%%PSP  X_(k+1)=(a*X_k+c)mod m. Length = m.

%% searching for (m < M) & (m mod 8 = 0)

  X=mod(M,8);

  m=M-X;

 

  % prime factor decomposition 

  f = factor(m);

%% getting a

  a=1;

  k=find(f>2);

  for l=1:size(k,2)

    a=a*f(k(l));

  end;

  a=a*4+1;

%% getting c

  c=2*round(m./3);

  while gcd(m,c)~=1

    c=c+1;

  end;

%% generation of pseudorandom sequence

  X0=c+2;

  X_PRS=zeros(1,m);

  X_PRS(1)=X0;

  for k=2:m

    X_PRS(k)=mod((a*X_PRS(k-1)+c),m);

  end;

  % ranking PRS

  O = sort(X_PRS);

end

Выполним данный скрипт в командной строке Matlab.


>> [X_PRS, O ] = psp(3145728); 


В результате имеем массив - псевдослучайную последовательность  X_PRS и ряд O, состоящий из тех же чисел но упорядоченных по возрастанию.


Первая двадцатка X_PRS выглядит так:



>> X_PRS20=X_PRS(1:20)

X_PRS20 =

Columns 1 through 6

2097157 1048644 887 2108686 1198521 1949288

Columns 7 through 12

2272075 176850 1250477 2624716 1615455 1077974

Columns 13 through 18

382177 774000 2721971 2879770 1785429 141908

Columns 19 through 20

796231 3010974

Первая двадцатка O, очевидно, выглядит так:


>> O20=O(1:20)

O20 =

Columns 1 through 12

0 1 2 3 4 5 6 7 8 9 10 11

Columns 13 through 20

  12 13 14 15 16 17 18 19
 
 График первой тысячи псевдослучайных чисел выглядит так: