Description of the class of permutations, represented as a product of two ermutations with fixed number of mobile point.pdf Пусть SN - группа подстановок степени N; G G Sn; r(G) С { 1 , . . . , N} - множе-ство мобильных точек подстановки G; 2 ^ q ^ N; rN(q) = {G G SN : |T(G)| = q} -множество всех подстановок степени N, имеющих ровно q мобильных точек.В данной работе описано множество всех подстановок из Г^ (q) Г^ (q). Данныйрезультат имеет практические приложения в криптографии.В научной литературе рассматривается схожая задача описания множества подста-новок, принадлежащих произведению двух или более классов сопряженных элементовиз Sn (или из An - знакопеременной группы подстановок) [1-6].Доказаны следующие результаты.Утверждение 1. Если N ^ 6, 2 ^ q1 < q2 ^ N/2, то rN(q1) rN(q1) С rN(q2) xхГм (52).Теорема 1. Пусть N ^ 8, 4 ^ q ^ N/2, G G SN. Если |r(G)| ^ 2q - 2,то существуют подстановки H1,H2 G Tn (q), для которых выполняется равенствоG = H H2.Далее рассмотрим, какие подстановки из множеств Tn(2q - 1), Tn(2q) принадлежатпроизведению rN (q) rN (q).Утверждение 2. Пусть N ^ 4, 2 ^ q ^ N/2, подстановка G G rN(2q) яв-ляется произведением r неединичных циклов, длины которых равны m1 , m2 ,... , mr,rУ] mi = 2q. Подстановка G лежит в rN(q) rN(q) в том и только в том случае, когдаi=1существует такое подмножество { i 1 , . . . , ik} С {1,... , r}, что mi1 + ... + mik = q.Утверждение 3. Пусть N ^ 4, 2 ^ q ^ N/2, подстановка G G rN(2q - 1) яв-ляется произведением r неединичных циклов, длины которых равны m1 ,m2,... ,mr,rmi = 2q - 1. Подстановка G лежит в rN(q) rN(q) в том и только в том случае,i=1когда выполнено условие: существует i0 G {1,... , r} и существует такое подмножество{i 1 , . . . , ik} С { 1 , . . . , r} \ {io}, что mi0 > 2 и q - m^ + mi2 + ... + mik G { 2 , . . . , mi0 - 1}.Итак, в теореме l, утверждениях 2 и 3 полностью описано строение множестваrN (q) rN (q) при 4 ^ q ^ N/2.

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