12.10.2024 08:44
rplacroix 13 6100 Источник

В этой статье мы исследуем проблему извлечения квадратного корня из перестановки p, иными словами задачу нахождения всех таких перестановок x, что x \cdot x = p. Будет сформулирован критерий возможности извлечения квадратного корня, алгоритм нахождения корней и формула их подсчёта в общем виде.

Действующие лица

Пусть дана перестановка p = \{2, 4, 3, 1\}. Если ее применить на последовательность из четырёх объектов s = \{n_1, n_2, n_3, n_4\}, то 1 переходит в 2, 2 в 4 и т.д. Над перестановкой расставляем верхние индексы и смотрим кто куда переходит. Тогда p \circ s = \{n_2, n_4, n_3, n_1\}.

Для каждой перестановки можно записать ее цикловую структуру. Для этого снова пишем над p верхние индексы и смотрим куда переходит 1. 1 переходит в 2, следовательно пока пишем так: p = (12 \dots . 2 переходит в 4, 4 переходит в 1, 1 переходит в 2. Цикл замкнулся, его длина 3, т.е. это 3-цикл. А 3 переходит в 3, образуя 1-цикл. Итого: p = (124)(3), но 1-циклы обычно опускают.

Назовем паспортом перестановки такой словарь (в терминах Python), где ключами выступают длины циклов существующих в перестановке, а значениями - количество циклов такой длины. Паспорт для p запишется так: {1: 1, 3: 1}.

Перестановка \hat{p} = \{4, 1, 3, 2\} = (142)(3) тоже 3-цикл и имеет такие же свойства (порядок, четность и количество корней), как и p. Поэтому для группы перестановок длины n (обозначаетсяS_n) имеет смысл рассматривать "посольство" от каждой возможной цикловой структуры, а не все сразу.

Корневые карты

Для начала попробуем проанализировать проблему поиска корней эмпирически. Составим корневую карту (ориентированный граф), где вершины - это цикловые структуры, а А и Б соединяются ребром, если при извлечении корня из перестановки А можно получить перестановку с цикловой структурой Б.

Карта для группы S5
Карта для группы S5

Зеленым цветом показаны четные перестановки, желтым - нечётные. Вершина () - это нейтральный элемент, перестановка, полностью состоящая из 1-циклов, которая ничего не переставляет. Обратим внимание на вершину (3). Из нее выходит ребро в само себя и ребро в (2, 3). То есть при извлечении корня из любой перестановки с структурой 3-цикл, получится несколько ответов: как минимум будет 1 3-цикл и 1 (2, 3)-цикл.

Карта для группы S6
Карта для группы S6

Подметим закономерность с нейтральным элементом (). На обоих графах он соединён ребрами с k 2-циклами. И так будет продолжаться и дальше. Дело в том, что есть понятие порядка: такое наименьшее n, что p^n = e (e - нейтральная перестановка). Порядок для перестановки считается как НОК (наименьшее общее кратное) от длины его цикловых структур. Так и получается, что 2-циклы разной длины при возведении в квадрат всегда будут давать нейтральную перестановку.

На картах можно заметить и другие паттерны, однако перейдем уже к менее эмпирической части нашего рассказа.

Реверсивная психология

Мы уже выяснили, что нам важна цикловая структура. Понаблюдаем за поведением перестановок при обратной операции - возведении в квадрат. Нам достаточно проанализировать поведение цикла, так как пусть p = c_1 \cdot \ldots \cdot c_n, а p^2 = c_1^2 \cdot \ldots \cdot c_n^2 ввиду того что непересекающиеся циклы коммутируют.

Запишем цикл в общем виде как c = (x_1x_2 \ldots x_k). Квадрат цикла c^2 переведет x_1 в x_3, x_2 в x_4 и т.д. В общем виде: x_i \rightarrow x_{(i+2) mod \ k} . Но возможны два случая, обратим внимание на чётность длины цикла k:

Если k нечётное, то квадрат также будет k-циклом. Если k чётное, то квадрат разобьется на два цикла: c^2 = (x_1x_3 \ldots x_{k-1})(x_2x_4 \ldots x_k).

Теперь применим полученные знания в обратную сторону. Из одного цикла нечетной длины корень всегда можно извлечь, причём однозначно. Но пара циклов одинаковой длины m при извлечении корня схлопнутся в новый цикл длины 2m. В этом моменте и берется неоднозначность при извлечении корня - существует же несколько способов выбрать пару.

Обратите внимание и на другой факт: если в исходной перестановке p есть хоть один случай, когда нечетное количество циклов четной длины, то из него нельзя извлечь корень. Поскольку при разбиении на двойки, одному из циклов четной длины не найдется пары, и тогда непонятно, как он вообще здесь появился, если мы предполагаем, что p = x^2. Так, мы формулируем критерий извлечения квадратного корня: каждый цикл четной длины должен входить в перестановку четное количество раз.

При выводе формулы будем полагать, что этот критерий соблюдается.

Выводим формулу

Подчеркнем еще раз важное отличие между циклами четной и нечетной длины. Когда мы будем формировать пары, то для циклов нечетной длины могут остаться свободные члены. Более того, количество пар может варьироваться от 0 до \lfloor \frac{n}{2} \rfloor(округление вниз), где n - количество циклов одинаковой длины. Для простоты будет пользоваться Python-обозначением n // 2. Для циклов четной длины такой свободы выбора нет - каждый должен найти себе пару.

Составил таблицу истинного числа корней (данные получены перебором на Python)
Составил таблицу истинного числа корней (данные получены перебором на Python)

Чтобы дальнейшие заключения не выглядели слишком умозрительными, то я приведу таблицу с количеством корней. Вы сейчас можете прикинуть - понимаете ли вы алгоритм или нет.

Переформулирую задачу на язык комбинаторики: найти количество пар из n элементов, где порядок между и внутри парами не важен. Обозначим этот ответ за A(k, n), выразить его не проблема.

Обратим внимание на извлечение корня из (3,3)-цикла в S_7.

Результат перебора программой
Результат перебора программой

Первый случай это извлечения корня из нечетных циклов. Другие три - комбинация 3-циклов для получения 6-цикла. Она может быть проведена 3 способами (нужно выбрать, что будет идти после 1, т.е. равна длине цикла, выбираем 1 раз). Эти выборы необходимо учесть в итоговой формуле.

Мы готовы записать результат. Введём функцию R(k, n, m), где k - количество пар, а рассматриваем мы n циклов длины m.

пришлось вставить скрин, так как Хабр лагает
пришлось вставить скрин, так как Хабр лагает

Первый множитель отражает циклы с нечетной длиной, у которых есть свобода выбора - объединяться в пары или нет. Второй множитель это циклы с четной длиной, последнее слагаемое первой суммы. Это выражение записано для одной пары ключ-значение в паспорте перестановки. Общее количество корней это произведение для каждой существующей пары. Код на Python, считающий количество корней (необходимо реализовать класс Permutation с методом pasport):

def find_amountofsquareroots(perm: Permutation):
    def member_of_sum(n, cyclen, k):
        return (math.factorial(n) * cyclen ** k) // (math.factorial(k) * (2 ** k) * math.factorial(n - 2 * k))

    def odd_count(n, cyclen):
        total_sum = 0
        for k in range(0, n // 2 + 1):
            total_sum += member_of_sum(n, cyclen, k)

        return total_sum

    def even_count(n, cyclen):
        assert n % 2 == 0, 'для извлечения корня m должно быть четным'
        return member_of_sum(n, cyclen, n // 2)

    psp = perm.passport()
    answer = 1
    for cycle_len, cnt in psp.items():
        if cycle_len % 2 != 0:
            answer *= odd_count(cnt, cycle_len)
        else:
            if cnt % 2 == 0:
                answer *= even_count(cnt, cycle_len)
            else:
                answer = 0
                break
    return answer

Повторюсь, что могу ошибаться, так как свою формулу не смог проверить в доступных источниках информации.

Комментарии (13)


  1. RodionGork
    12.10.2024 11:22
    #27408178

     иными словами задачу нахождения такой перестановки x, что x * x = p. 

    не серчайте, но если пишете пост на более-менее широкую публику, то эта фраза мало что объясняет непосвещенному (мне она понятна хоть и не с первого прочтения)

    Плюс неплохо будет смотреться пояснение - зачем нам это знание :)


    1. rplacroix Автор
      12.10.2024 11:22
      #27408276

      Добрый день!
      Откровенно говоря, я прекрасно понимаю, что непосвященному эта статья вообще ничего не скажет, потому что никакой подготовки я практически не даю. Сомневаюсь, что это заинтересует публику, поэтому я даже не стал стараться.

      "Зачем нам это знание" - не знаю) Мог бы отделаться словами, что имеет применение в криптографии, но это мой максимум.


      1. aamonster
        12.10.2024 11:22
        #27408406

        Да нет, достаточно забавная комбинаторная задачка, и с момента, как вы сказали про "паспорт" перестановки – достаточно несложная, но всё равно получил удовольствие, прикинув способ вычисления и сверив с вашими рассуждениями.

        Возможно, стоило дать какую-нибудь "детскую" формулировку, не опирающуюся на другие определения (это часто практикуется в комбинаторных задачках для программистов), но и так неплохо вышло.


        1. rplacroix Автор
          12.10.2024 11:22
          #27408438

          Спасибо!


      1. vkni
        12.10.2024 11:22
        #27411112

        "Зачем нам это знание" - не знаю)

        Возможно, оно имеет отношение к очень занятной штуке: есть какая-то связь между типами и структурой полиморфных функций, а также тестами, которые надо для этих функций писать.

        Можете посмотреть статью Wadler'a "Theorems for free", он в ней не упоминает этого, но всё строится на том, что есть симметрия полиморфных функций относительно преобразований внутри множества. Например, функция с сигнатурой

        f :: [a] -> [a]

        коммутирует с функцией, работающей исключительно внутри множества a.

        Можно подойти с другой стороны - у Кнута есть знаменитая теорема о том, что сортировку, базирующуюся на операции CAS (compare-and-swap), можно проверить на булевых числах, и тогда она гарантированно будет работать на целых. Шутка в том, что операция cas имеет сигнатуру

        cas :: (a, a) -> (a, a)

        То есть, тоже симметрично относительно каких-то преобразований в a. Эти два момента, грубо говоря, связывают тесты, полиморфизм и симметрии. И, значит, практическое применение тут - создание какого-то подхода, который позволит резко уменьшить число тестов.

        Поэтому, возможно, вся эта теор-групповая штука имеет большое значение и вне криптографии.


    1. leshabirukov
      12.10.2024 11:22
      #27414560

      Вчерась в МГУ дядька кошек с собаками не стеснялся при детях складывать.


  1. jzha
    12.10.2024 11:22
    #27409750

    Число решений квадратного уравнения в конечной группе может быть найдено через ее линейные представления и их характеры. Для групп перестановок таблицы характеров известны, а формула сводится к суммированию по всем неприводимым характерами. Больше подробностей в этом сообщении https://mathoverflow.net/a/41788


  1. tarlex2001
    12.10.2024 11:22
    #27410138

    Я конечно не претендую на истину в последней инстанции  , но мне кажется что ваше изложение  данной темы несколько громоздко и потому непонятно для тех , кто не в теме .

    Я думаю , что писать перестановки надо  в виде произведения циклов   :  так нагляднее и на мой взгляд – понятнее ,  ( рядом пишу вашу запись )  . Итак :

    1 ) s =  ( 1 , 2, 3, 4 , 5 ) (6) = { 2,3,4,5,1,6 } 

    Так как для любой вообще перестановки p всегда существует натуральное число m , такое что : p^m=e ( или  p^(m+1)=p ) , где e – тождественная перестановка ( это очевидно , так как степени конкретно взятой перестановки образуют подгруппу конечной группы – группы всех перестановок данного множества ) . В частности для цикла длинной m  это и есть минимальная степень ( тоже очевидно ) . Итак – в нашем случае m=5 . Поэтому s^((m+1)/2) = s^3– корень данной перестановки и он единственный . То есть сразу и без вычисления , смотря на сам цикл , пишем ответ :

    P= ( 1 , 4 , 2 , 5 , 3 ) ( 6 )      ;   p^2 = s 

    2 ) s = ( 1 , 2 ) ( 3 ,4 ) ( 5) ( 6) = { 2 , 1 ,4 , 3 , 5 , 6 }

    Видим два четных цикла длины два и значит будем иметь два варианта цикла длины четыре ( поменяв их местами )  , один вариант цикла длины два ( объединив единичные )  и оставляя единичные  циклы неизменными . Всего четыре варианта . И тоже , можем сразу и без вычислений , лишь глядя на исходное представление перестановки , писать ответы :

    P1= ( 1 ,3 , 2 , 4 ) ( 5 ) (6) ;  P2= ( 1 ,4 , 2 , 3 ) ( 5 ) (6)  ;  P3= ( 1 ,3 , 2 , 4 ) ( 5 ,6)  ; P4= ( 1 ,4 , 2 , 3 ) ( 5 ,6) 

    Pk^2= s .  

    3) s = ( 1 , 2 , 3 ) ( 4 ) ( 5) ( 6) = { 2 , 3 ,1 , 4 , 5 , 6 }

    Видим один цикл длины три и три цикла единичной длины . У нас всего три варианта объединить единичные циклы в цикл длиной два и один вариант – оставить единичные циклы .  Всего четыре корня :

     P1= ( 1 ,3 , 2  ) ( 4, 5 ) (6) ;  P2= ( 1 ,3 , 2 ) ( 4, 6 ) (5);  P3= ( 1 ,3 , 2 ) ( 5 ,6) (4) ; P1= ( 1 ,3 , 2  ) ( 4 ) ( 5 ) (6)

    Pk^2= s .

    4) s = ( 1 , 2 ) ( 3 , 4 ) ( 5 , 6 , 7 ) = { 2 , 1 , 4 , 3 , 6 , 7 , 5 }

    Имеем два цикла длиной два и один цикл длиной три . То есть здесь будут всего два корня от перемены мест двух четных циклов :

    ( 1 , 2 ) ( 3 , 4 )  получим ( 1 , 3 , 2 , 4 )  и ( 3 , 4 ) ( 1 , 2 )  получим  ( 3 , 1 , 4  , 2 ) = ( 1 , 4 , 2 , 3 ) . Итак , имеем :

    P1= ( 5 ,7 , 6  ) ( 1, 3 , 2 , 4 ) ;  P2= ( 5 ,7 , 6  ) ( 1, 4 , 2 , 3 )  ; Pk^2= s .

    5 ) s = ( 1 , 2 , 3 , 4 , 5 ) ( 6 ) ( 7)  = { 2 , 3 ,4 , 5 , 1 , 6 , 7 }

    Видим один цикл длины 5 и два единичных цикла . А значит всего два корня – оставляем единичные циклы без изменений и объединяем их . Так как ( 5+1)/2 = 3 , то s^3 – корень квадратный . Итак :

      P1= ( 1 ,4 , 2 , 5 , 3 ) ( 6 ) ( 7) ;  P2= = ( 1 ,4 , 2 , 5 , 3 ) ( 6 , 7) ; Pk^2= s .

    Ну и так далее . Все вычисляется вручную и очень быстро …  


    1. rplacroix Автор
      12.10.2024 11:22
      #27410918

      Здравствуйте!

      Именно подход с цикловой записью, о которой вы пишете, в статье и применяется. Алгоритмы у нас совпадают.

      Задача же в том, чтобы посчитать количество корней в общем виде, зная паспорт перестановки.


      1. tarlex2001
        12.10.2024 11:22
        #27412018

        Вот именно : формула для числа корней в общем виде совсем не очевидна , по кра


      1. tarlex2001
        12.10.2024 11:22
        #27412040

        Вот именно : формула для числа корней в общем виде совсем не очевидна , по крайней мере для меня . Любопытно было бы увидеть подробное доказательство .

        Я думаю проще попытаться найти контрпример , посчитав число корней x^2=e для групп вида S(p^n) , где р - простое . И сравнить результат .


      1. tarlex2001
        12.10.2024 11:22
        #27412130

        Извиняюсь , опечатался : хотел написать S(p*2^n) , где р - простое . То есть проверить формулу для групп S3 и S4 для числа корней x^2=e


  1. wataru
    12.10.2024 11:22
    #27411606

    Я бы посоветовал вместо корневой карты рисовать перестановки в виде циклов (граф где n вершин и направленое ребро из i в p(i)). Потом на картинке показать, что просиходит с перестановкой при возведении в квадрат. Вот так вы наглядно покажете, что нечетные циклы просто перетасовываются, а четные распадаются на 2 цикла одинаковой длины.

    Оттуда будет более наглядно видно, что для обратной операции можно циклы нечетной длины перетасовывать определенным образом, а также объединять по 2 цикла одинаковой длины в один. Раз надо все циклы так обработать, то и получается ваш критерий - циклы четной длины должны идти парой с циклом такой же длины.