РЕКУРРЕНТНАЯ ЗАВИСИМОСТЬ КОЛИЧЕСТВА ПЕРЕСТАНОВОК С ЗАДАННЫМ ЧИСЛОМ ИНВЕРСИЙ

Казахский национальный университет имени аль-Фараби, Алматы, Казахстан

1. Введение

Необходимость большого числа опробований возникает при анализе криптографических алгоритмов. Для шифров простой замены мощность ключевого множества составляет n!, где объем алфавита равен n [1]. Формула Стирлинга дает оценку [2]. Поэтому, для того чтобы перебрать ключевое множество всевозможных замен для английского алфавита понадобится 26! ≈ 4,03⋅1026 ≈ 288 опробований. Следует заметить, что даже на самом мощном суперкомпьютере из списка top500 – пятисот самых высокопроизводительных из известных ЭВМ, данная задача пока не выполнима за реальное время. Если взять современный самый производительный суперкомпьютер (Tianhe-2, Китай) [3], то за 1 год работы он выполнит 33,86⋅1015 (производительность, операций в секунду) Ч 365 (дней в году) Ч 24 (часов в сутки) Ч 3600 (секунд в часе) операций, что примерно равно 1,07⋅1024 ≈ 280 операций с плавающей запятой.

Существуют и другие методы криптографического анализа шифра замены, например, использующие частотный анализ [1, 4]. Однако для успешного осуществления частотного анализа обычно требуется наличие большого объема шифрованного текста. В этой связи, для коротких текстов представляется предпочтительным комбинирование данных методов. При этом на каждом шаге оптимальным видится перебор близких перестановок.

Некоторой мерой беспорядка перестановки является понятие инверсии. Два числа в перестановке образуют инверсию, если меньшее из них расположено в этой перестановке правее большего. Каждой перестановке можно сопоставить число инверсий в ней, которое подсчитывается следующим образом: для каждого из чисел определяют количество стоящих правее его меньших чисел, и полученные результаты складываются. Например, число инверсий в перестановке: (5, 3, 1, 4, 2, 6) равно 4 + 2 + 0 + 1 + 0 = 7. Действительно за 7 элементарных транспозиций (замены двух соседних в перестановке элементов) возможно привести данную перестановку к тождественной (1, 2, 3, 4, 5, 6).

НЕ нашли? Не то? Что вы ищете?

Понятно, что тождественная перестановка имеет 0 инверсий, а убывающая перестановка (n, n – 1, n – 2, …, 3, 2, 1) имеет максимальное количество инверсий n(n – 1)/2 при фиксированной длине перестановки n.

Самостоятельный интерес представляет собой нахождение оптимального алгоритма нахождения всех перестановок заданной длины, количество инверсий которых не превышает определенного числа. Но в данной работе мы сосредоточимся на подсчете числа перестановок определенной длины, число инверсий которых ограничено наперед заданным числом.

2. Способы вычисления числа перестановок

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

Тем не менее, путем перебора построим таблицу значений числа перестановок заданной длины и с заданным числом инверсий (Таблица 1).

Таблица 1 – Число перестановок

Длина\ Число инверсий

0

1

2

3

4

5

6

7

8

9

10

1

1

2

1

1

3

1

2

2

1

4

1

3

5

6

5

3

1

5

1

4

9

15

20

22

20

15

9

4

1

Заметим, что в данной таблице сумма чисел в каждой строке равна факториалу длины. Но основная закономерность, которая прослеживается в данной таблице, – значение в n-той строке и k-том столбце равно сумме n значений в предыдущей n – 1-ой строке, с номерами столбцов не превосходящими k (пустые ячейки будем считать нулевыми; если номер столбца k меньше номера строки n, то прибавляются k первых значений из предыдущей строки). Другими словами, если через a(n, k) обозначить количество перестановок n элементов с числом инверсий k, то

a(n, k) = a(n – 1, k) + a(n – 1, k – 1) + … + a(n – 1, k – n + 1), если n ≤ k,

a(n, k) = a(n – 1, k) + a(n – 1, k – 1) + … + a(n – 1, 0), если n > k.

Данная закономерность имеет следующее объяснение: для того чтобы построить все перестановки длины n c числом инверсий k, необходимо во всех перестановках длины n – 1 и числом инверсий  k – i (0 ≤ i ≤ min(n, k)) поставить новое число n на i-тую позицию справа. Понятно, что этим методом мы перечислим все необходимые перестановки, причем по одному разу.

Таким образом, для вычисления числа перестановок длиной n с числом инверсий k понадобится не более k ⋅ n2 операций сложения.

3. Способы дальнейшей оптимизации

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

a(n, k) = a(n, k – 1) + a(n – 1, k), если n ≥ k;

a(n, k) = a(n, k – 1) + a(n – 1, k) – a(n – 1, k – n), если n < k.

В этом легко убедиться, например, во втором случае:

a(n, k) = a(n – 1, k) + a(n – 1, k – 1) + … + a(n – 1, k – n + 1) =

a(n – 1, k) + a(n – 1, k – 1) +…+ a(n – 1, k – n + 1) + a(n – 1, k – n) – a(n – 1, k – n) = a(n – 1, k) + a(n, k – 1) – a(n – 1, k – n).

Тогда для вычисления числа перестановок длиной n с числом инверсий k понадобится не более 2⋅k⋅n операций сложения, что существенно снижает предыдущую оценку.

4. Способ прямого вычисления

Приведенные выше методы дают рекуррентную зависимость для вычисления числа перестановок фиксированной длины и с фиксированным числом инверсий. Покажем, как при n >> k возможно построить прямую формулу вычисления числа перестановок a(n, k) при небольших предварительных рекуррентных вычислениях. Для этого предварительно вычислим значения a(k, 0), a(k, 1), …, a(k, k). Тогда

a(n, k) = a(k, 0)⋅ + a(k, 1)⋅ + … + a(k, k)⋅.

Здесь мы пользовались числом разбиения натурального числа s на m неупорядоченных неотрицательных целых слагаемых, где – формула вычисления биномиального коэффициента.

Литература

1. Smart N. Cryptography: An Introduction. - McGraw-Hill, 2003. - 433 p.

2. Комбинаторные алгоритмы: Учебное пособие.  - Новосибирск: Новосиб. гос. ун-т., 2011. - 118 с.

3. www. top500.org.

4. , , Основы криптографии. - М.: Гелиос АРВ, 2002. - 480 с.