On the largest order of substitutions of a given degree.pdf Каждая подстановка есть произведение независимых циклов. Если длины циклов подстановки g равны l1 , . . . , lm, то её порядок равен ordg = НОК(11, . . . ,lm). Если в записи подстановки имеется ki циклов длины li, i = 1,... , m, то это свойство записывается с помощью цикловой структуры C (g) подстановки g: C(g) = {l!4...,lJkm]}; (1) эти числа связаны со степенью n подстановки равенством k1 l1 + . . . + k m lm = n. Далее считаем, что длины циклов упорядочены: l1 < . . . < lm . Обозначим: - Sn - группа всех подстановок степени n; (m ) - оП -множество всех подстановок степени n, состоящих из m циклов, 1 m n; - ORDn = {ordg : g G Sn}; - ^(n) = max ord g; gESn - gmax - подстановка g G Sn, такая, что ordg = g,(n). Необходимым требованием к системе шифрования является достаточно большой порядок группы, которая ассоциируется с шифром (то есть порождается подстановками шифра). В связи с этим представляет интерес величина ц(п), оценивающая порядки циклических групп подстановок степени n, в том числе циклических групп, порождённых шифрующими подстановками. Тривиальные оценки для порядка подстановок из Sn имеют вид 1 < ord g < n!. где нижняя оценка достижима при любом n для тождественной подстановки и верхняя оценка достижима лишь при n 2. Задача нахождения ^(n) сводится к определению наибольшего значения 11ОК(/|. ... , lm), где максимум берётся по всем разбиениям n-множества на m непустых блоков порядков l| , . . . , lm . Утверждение 1. Функция ^(n) монотонно неубывающая с ростом n. Доказательство. Пусть g = gnmax и цикловая структура подстановки g определена равенством (1). Возьмём подстановку h G Sn+| со свойством C(h) = l1 = 1, l1 > 1. Доказательство. Следует из существования в Sn подстановки gl с цикловой структурой C(gl) = {1[n-l],l[1]}, l = 1,...,n. ■ Множество натуральных чисел L = {l1, l2, . . ., lm}, где m > 1 и l1 < . . . < lm, назовём r-разреженным, r 0, если lm - l1 = m - 1 + r; при r = 0 множество L назовём сплошным. Множество натуральных чисел L' = {A1, A2,... , Am} назовём 2-сжатием множества L, если положительны обе разности А1 -l1 и lm - Am, и 1-сжатием множества L, если одна из разностей А1 -l1 и lm - Am положительна, а другая равна 0. Обозначим: S(L) = l1 + l2 + ... + lm; Z(L) = l1l2 ... lm. Утверждение 3. Для любого r-разреженного множества L = {l1 ,l2,... ,lm} имеется сплошное множество L', являющееся: 1) 2-сжатием множества L при r > 1, таким, что S(L) С S(L') и Z(L) < Z(L'); 2) 1-сжатием множества L при r =1, таким, что E(L) С E(L') и Z(L) < Z(L1). Занумеруем простые числа в порядке возрастания: p1 = 2, p2 = 3, . . . При n > 1 обозначим: Q(n) = {(pi1 , ...,pir)} - семейство всех множеств простых чисел, для которых pi1 + ... + pir С n, r С n/2, числа i1,... , ir натуральные; П(п) = = maxpi1 .. .pir -наибольшее (по всем наборам из Q(n)) значение произведения чисел Q(n) набора. Теорема 1. Для любого n > 3 верны оценки: П(п) С ц(п) С \\^2(n - 1) "]!. Доказательство. Для любого n > 3 и любого набора простых чисел (pi1,... ,pir) G Qn существует подстановка степени n, содержащая циклы длины pi1, . . . , pir. Порядок такой подстановки равен pi1 . . . pir в силу попарной взаимной простоты чисел набора. Нижняя оценка доказана. Пусть подстановка g степени n порядка ц(п) содержит циклы, множество длин которых есть L = {l1,... ,lm}. Если E(L) = d < n, то подстановка g имеет два или более циклов одинаковой длины lr, r G {1,... , m}, где 1 С lr С n - d. Тогда существует подстановка h степени n с множеством длин циклов L1 = {l1, . . . , lm-1, lm + lr}, при этом Z(L) < Z(L1). Отсюда получаем ordg = HOK(L) С Z(L) < Z(Li). Рассуждая аналогично, за конечное число шагов перейдём от подстановки g к подстановке g' степени n, у которой длины всех циклов различные и ord g < n(L'), где L' - множество длин всех циклов подстановки g'. Значит, ^(n) не превышает наибольшее значение Z(L), где максимум берется по наборам L для множества всех подстановок степени n с различными длинами всех циклов. В соответствии с утверждением 3, верхняя оценка Z(L) достигается на одной из подстановок степени n, у которой множество длин циклов L есть сплошное множество. Оценим произведение n(l,m) = (l + 1)... (l + m) при условии, что числа l и m таковы, что £(l,m) = (l + 1) + ... + (l + m) есть величина порядка n + o(n), что не нарушает справедливость оценки ordg с помощью числа n(l,m). Суммируя арифметическую прогрессию, получаем £(l, m) = (l + (m + 1)/2)m = n + o(n). (2) Если при фиксированном l > 0 взять m = V2(n - l) то e(l, p2(n - o]) > e(l, V2(n - = n + V2(n - l)(l + 1/2) - l. Тогда значение e(l. р2(П-Г) удовлетворяет (2) при l = о(д/й). Взяв l = 1, m = s/2(n -1) , получим n (1. p2(n - 1)]} С p2(n - 1f|!. Следовательно, ord g < \\/2(n - 1) !. ■ Следствие 1. При любом n 1000 и k = -^/2n/ln n верна нижняя оценка ^(n) > 224 k!(1.665)k(ln k)(k-15)/2. Доказательство. Для получения ограничения снизу для ord g оценим произведение первых простых чисел, сумма которых не превышает n. В соответствии с верхней оценкой Россера [2] pk < k ln k + k ln ln k + 8k. Заметим, что p1 + p2 + p15 = 328. p16 = 53. Следовательно, при любом n 381 выполнено условие E({pi.p2.....pk}) < n. (3) если k 16, и условие k V гф(г) С n - 328. r=16 где ф(г) = ln r + lnlnr + 8. Так как при r 1 функция ф(г) монотонно возрастает, то kk (k - 15)(k + 16) 2 V гф(т-) < ф(к) ^2 r = Ф(к) r=16 r=16 Значит, условие (3) удовлетворено, если ф(к) (k - 15)(k + 16) 2 С n - 328. (4) В частности, при n 1000 и 16 С k С ^2n/ln n имеем (k - 15)(k + 16) С - + J-^- - 120 2 ln n 2 ln n ф(&) = - ln 2n - - ln ln n + ln(- ln 2n - - ln ln n) + 8. Заметим, что при n 1000 ln | - ln 2n--ln ln n r lnr, где r > 1 [2], по теореме 1 при n 1000 и k = ^2n/ln n получаем (7) ^(n) > cis П r ln r = c15П ln r > 4,7 • 105k! П ln r. r=16 15!r=16 r=16 Функция ln r выпуклая вверх, тогда (ln r)2 > ln(r - h) ln(r + h) при любых r > 1 и h < r. Следовательно, при k 16 k ln r > (ln 16)(k-i5)/2(ln k)(k-i5)/2. r=i6 Заметим, чт^/ln 16 > 1,665 и 4,7^ 105(ln 16) 15/2 > 224. Отсюда и из (7) следует нужная оценка для ^(n). ■ В таблице приведены оценки и точные значения функции ^(n) для n C 12. n 4 5 6 7 8 9 10 11 12 Верхняя оценка 6 6 24 24 24 24 120 120 120 Точное значение, длины циклов gmax 4, 4 6, 2+3 6, 6 12, 3+4 15, 3+5 15, 1+3+5 30, 2+3+5 30, 1+2+3+5 60, 3+4+5 Нижняя оценка по наборам простых чисел 3, {3} 6, {2,3} 6, {2,3} 10, {2,5} 15, {3,5} 15, {3,5} 30, {2,3,5} 30, {2,3,5} 42, {2,3,7}

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