, т.е. по имеющимся в нем подстановкам любая пара (y
>1,y
>2), в которой y
>1≠y
>2, сможет перейти в любую пару (z
>1,z
>2), в которой z
>1≠z
>2? Что в общем случае можно будет сказать про обобщение 2-транзитивности – m-транзитивность?
За свойство 2-транзитивности взялись основательно, чувствовалось, что здесь могут быть интересные криптографические зацепки: если 2-транзитивность отсутствует, то появляются запреты переходов биграмм текста, широкое поле деятельности для криптоаналитика. Например, если π - упомянутая выше линейная подстановка, то для любой пары (y>1,y>2) будет справедливо соотношение:
π(y>1)- π(y>2) = (ay>1+b) - (ay>2+b) = a(y>1-y>2)
В этом случае при применении подстановки π сохраняется соотношение между разностями знаков, а поэтому кратной транзитивности заведомо не будет.
А если π - не линейная, а произвольная подстановка? При каком минимальном значении k множество (Gπ)>k может достичь свойства 2-транзитивности? Всего имеется 2>n(2>n-1) различных пар (z>1,z>2), в которых z>1≠z>2, а количество различных подстановок в (Gπ)>k не превосходит (2>n)>k. Следовательно, свойства 2-транзитивности можно достичь только при k≥2. Можно ли при k=2?
Рассмотрим множество подстановок (Gπ)>2. Это множество реализует всевозможные преобразования произвольного значения t в значение s по формуле s = π (π (t+x>1)+x>2) при всевозможных x>1,x>2. Если бы это множество было 2-транзитивным, то для любых заранее фиксированных s>1,s>2, t>1,t>2 , в которых s>1≠s>2 и t>1≠t>2, система уравнений:
s>1 = π (π (t>1+x>1)+x>2)
s>2 = π (π (t>2+x>1)+x>2)
имела бы решение относительно x>1,x>2, а, следовательно, поскольку π - подстановка, то и система
s>1 = π (t>1+x>1)+x>2 (1)
s>2 = π (t>2+x>1)+x>2
имела бы решение для любых заранее фиксированных s>1,s>2, t>1,t>2, в которых s>1≠s>2 и t>1≠t>2
Отсюда, вычитая одно уравнение из другого, мы приходим к одной очень важной криптографической характеристики подстановки π - матрице частот встречаемости разностей переходов ненулевых биграмм P(π) размера (2>n-1)x(2>n-1), а именно, на пересечении i-ой строки и j-го столбца в этой матрице стоит значение p>ij - число решений системы уравнений относительно x и y:
x-y = i (2)
π(x) - π(y) = j
где i, j ≠ 0.
Если при каких-то i, j ≠ 0 p>ij =0, то это означает, что при заранее фиксированных s>1,s>2, t>1,t>2, в которых s>1≠s>2 и t>1≠t>2, а также t>1-t>2 = i, s>1-s>2 = j, система (1) заведомо не имеет решения, ибо в противном случае имела бы решение и система (2).
Заметим, что p>ij = p>(2>n>-i)(2>n>-j). Действительно, каждому решению (x
