Involutions numeration.pdf Пусть задано конечное множество X. Отображение q : X ^ X со свойством ин-волютивности Vx,y Е X(q(x) = y ^ q(y) = x) называется инволюцией. Представиминволюциювектором (qi, q 2 , . . . , qn), где n = |X |. Зададим на множестве всех инволюций на Xлексикографический порядок, согласно которому каждой инволюции можно сопоста-вить порядковый номер. Возникают две задачи: построить инволюцию по заданномуномеру и вычислить номер заданной инволюции [1].Приведём примеры того, где возникают эти задачи. Если инволюция используетсяв качестве ключа шифра и требуется построить случайный ключ, то можно случайносгенерировать число (номер инволюции), а затем по номеру восстановить саму ин-волюцию. Можно изучать свойства инволюций (в том числе и криптографические),используя параллельные вычисления. Нумерация позволяет разбить все инволюциина классы требуемой мощности и строить и изучать эти классы параллельно.В данной работе предлагаются алгоритмы решения поставленных задач и приво-дятся результаты их испытаний.Алгоритм 1 построения инволюции по заданному номеруВход: n - длина инволюции, I - номер инволюции.Выход: вектор (qi, q 2 , . . . , qn), представляющий I-ю (в лексикографическом поряд-ке) инволюцию.Число всех инволюций длины n вычисляется по рекуррентной формуле rn = rn_ i ++ (n - 1 ) r „ _ 2 , где ri = 1 и Г2 = 2 [2].1. Y = {1, 2 , . . . , n}, t = 1.2. Если t = n, то переход в п. 5.3. Если I ^ rn_t , то qyi = yi , Y = Y \ { y i } , t = t + 1 и переход в п. 2;иначе если t < n - 1, то k = |~(/ - rra_t)/rra_t - i ] + 1, иначе k = 2.4. qt = yfc.Если qt = t, то t = t + 1, I = I - r„_t - (k - 2)rn_t_i, Y = Y \ {yfc},иначе qyk = t, I = I - r„_t - (k - 2)rn_t_i, t = t + 2, Y = Y \ {yfc, t} и переходв п. 2.5. qt = y i.Алгоритм 2 вычисления номера заданной инволюцииВход: n - длина инволюции, вектор (qi,q2 , . . . ,qn), представляющий инволюцию.Выход: I - искомый номер инволюции.1. I = 1, t = П.2. Если q1 = 1, то t = t - 1,иначе I = I + r t - i + (qi - 2)rt_2, t = t - 2.3. i = 1.4. Если i = n, то переход в п. 6,иначе если q^ = i, то t = t - 1 и переход в п. 5,иначе если q^ > i, то I = I + r t - 1 + (q^ - n + t - 1)rt, t = t - 2 и переходв п. 5.5. i = i + 1 и переход в п. 4.6. I - результат.Приведённые алгоритмы реализованы программно на языке Си+-+ с использовани-ем процессора Intel(R) Pentium(R) 4CPU, работающего с частотой 300 ГГц. В таблицеприведено усреднённое по 10000 случайных примеров время работы алгоритмов для25 < n < 31.n Время работы алгоритма 1, с Время работы алгоритма 2, с25 0,0055 0,00126126 0,008729 0,00190227 0,013972 0,003228 0,022783 0,00519929 0,037049 0,00826330 0,057267 0,01303831 0,091838 0,021003

Скачать электронную версию публикации