• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Рожков М. И., Обросов П. А.

В работе предложен новый алгоритм проверки статистической неотличимости (относительно вероятностей выходных s-грамм) последовательностей, вырабатываемых  функциями усложнения f:Xn®F2 по закону

gi=f(xi,xi+1,…,xi+n-1), i=1,2,…

При этом исходная последовательность x1,x2,… рассматривается как последовательность независимых одинаково распределенных случайных величин, заданных на входном алфавите X и принимающих значение xÎX с вероятностью px>0, Spx=1. Данный алгоритм выявляет неотличимость выхода для заданной пары f,j функций усложнения от 2n переменных, которые представляются суммой двух функций от n непересекающихся переменных

f=(f1,f2)=f(x1,x2,…,x2n)=f1(x1,x2,…,xn)+f2(xn+1,xn+2,…,x2n),

j=(j1,j2)=j(x1,x2,…,x2n)=j1(x1,x2,…,xn)+j2(xn+1,xn+2,…,x2n).

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