Description of the class of permutations represented as a product of two permutations with fixed number of mobile points.pdf Пусть подстановка G Е Sn, r(G) С { 1 , . . . , N} - множество мобильных точек под-становки G, 2 ^ q ^ N, rN( q ) = {G Е SN : |r(G)| = q} - множество всех подстановокстепени N, имеющих ровно q мобильных точек.В предшествующей работе (см. [1]) полностью описано строение множестваr N (q) r N (q) при 4 ^ q ^ N/2 и N ^ 8.В данной работе описано множество всех подстановок из rN (q) rN (q +1) при t ^ 1.Этот результат имеет практические приложения в криптографии.Сначала приведём результаты о строении множества rN (q) rN (q + 1).Утверждение 1. Если N ^ 6, 2 ^ q1 < q2 < N, то имеет место включениеrN(q1) rN(q2) С rN(q1 + 1) rN(q2 + 1).Теорема 1. Пусть N ^ 8, 3 ^ q ^ N/2, G Е SN. Если 1 < |r(G)| ^ 2q - 1,то существуют подстановки H1 Е rN (q), H2 Е rN (q + 1 ) , для которых выполняетсяравенство G = H1 H2.Далее рассмотрим, какие подстановки из множеств rN(2q + 1 ) , rN(2q) принадлежатпроизведению rN( q ) r N ( q + 1).Утверждение 2. Пусть N ^ 4, 2 ^ q < N/2, подстановка G Е rN( 2 q + 1) яв-ляется произведением r неединичных циклов, длины которых равны m1 , m 2 , . . . , mr ,r. mj = 2q + 1. Подстановка G принадлежит множеству rN (q) rN (q + 1) в том иj=1только в том случае, когда существует такое подмножество { i 1 , . . . , i ? } С { 1 , . . . , r } ,что mj1 + + mjk = q.Утверждение 3. Пусть N ^ 4, 2 ^ q ^ N/2, подстановка G Е rN(2q) яв-ляется произведением r неединичных циклов, длины которых равны m1 , m 2 , . . . , mr ,r. mj = 2q. Подстановка G принадлежит множеству rN (q) rN (q + 1) в том и толькоj=1в том случае, когда выполнено условие: существует io Е { 1 , . . . , r} и существует такоеподмножество { i 1 , . . . , i k } С { 1 , . . . , r} \ { i 0 } , что mj 0 > 2 и q - mj 1 + mj 2 + + mjfc ЕЕ { 2 , . . . , m j 0 - 1}.Итак, в теореме 1 и утверждениях 2 и 3 полностью описано строение множестваrN(q) rN(q + 1) при 3 ^ q ^ N/2.Наконец, приведем результаты о строении множества rN (q) rN (q +1), t ^ 2.Теорема 2. Пусть N > 10, 2 ^ t < N - 2, 2 ^ q < (N - t ) /2 + 1, G Е SN. Еслиt ^ |r(G)| ^ 2q + t - 2, то существуют подстановки H1 Е rN( q ) , H2 Е r N ( q + t), длякоторых выполняется равенство G = H1 H2.Можно доказать утверждения, аналогичные утверждениям 2 и 3, которые показы-вают, какие подстановки из множеств rN(2q + t - 1), rN(2q + t) принадлежат произ-ведению rN (q) rN (q + t).

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