Комментарии 13
иными словами задачу нахождения такой перестановки x, что x * x = p.
не серчайте, но если пишете пост на более-менее широкую публику, то эта фраза мало что объясняет непосвещенному (мне она понятна хоть и не с первого прочтения)
Плюс неплохо будет смотреться пояснение - зачем нам это знание :)
Добрый день!
Откровенно говоря, я прекрасно понимаю, что непосвященному эта статья вообще ничего не скажет, потому что никакой подготовки я практически не даю. Сомневаюсь, что это заинтересует публику, поэтому я даже не стал стараться.
"Зачем нам это знание" - не знаю) Мог бы отделаться словами, что имеет применение в криптографии, но это мой максимум.
Да нет, достаточно забавная комбинаторная задачка, и с момента, как вы сказали про "паспорт" перестановки – достаточно несложная, но всё равно получил удовольствие, прикинув способ вычисления и сверив с вашими рассуждениями.
Возможно, стоило дать какую-нибудь "детскую" формулировку, не опирающуюся на другие определения (это часто практикуется в комбинаторных задачках для программистов), но и так неплохо вышло.
"Зачем нам это знание" - не знаю)
Возможно, оно имеет отношение к очень занятной штуке: есть какая-то связь между типами и структурой полиморфных функций, а также тестами, которые надо для этих функций писать.
Можете посмотреть статью Wadler'a "Theorems for free", он в ней не упоминает этого, но всё строится на том, что есть симметрия полиморфных функций относительно преобразований внутри множества. Например, функция с сигнатурой
f :: [a] -> [a]коммутирует с функцией, работающей исключительно внутри множества a.
Можно подойти с другой стороны - у Кнута есть знаменитая теорема о том, что сортировку, базирующуюся на операции CAS (compare-and-swap), можно проверить на булевых числах, и тогда она гарантированно будет работать на целых. Шутка в том, что операция cas имеет сигнатуру
cas :: (a, a) -> (a, a)
То есть, тоже симметрично относительно каких-то преобразований в a. Эти два момента, грубо говоря, связывают тесты, полиморфизм и симметрии. И, значит, практическое применение тут - создание какого-то подхода, который позволит резко уменьшить число тестов.
Поэтому, возможно, вся эта теор-групповая штука имеет большое значение и вне криптографии.
Вчерась в МГУ дядька кошек с собаками не стеснялся при детях складывать.
Число решений квадратного уравнения в конечной группе может быть найдено через ее линейные представления и их характеры. Для групп перестановок таблицы характеров известны, а формула сводится к суммированию по всем неприводимым характерами. Больше подробностей в этом сообщении https://mathoverflow.net/a/41788
Я конечно не претендую на истину в последней инстанции , но мне кажется что ваше изложение данной темы несколько громоздко и потому непонятно для тех , кто не в теме .
Я думаю , что писать перестановки надо в виде произведения циклов : так нагляднее и на мой взгляд – понятнее , ( рядом пишу вашу запись ) . Итак :
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 .
Ну и так далее . Все вычисляется вручную и очень быстро …
Здравствуйте!
Именно подход с цикловой записью, о которой вы пишете, в статье и применяется. Алгоритмы у нас совпадают.
Задача же в том, чтобы посчитать количество корней в общем виде, зная паспорт перестановки.
Вот именно : формула для числа корней в общем виде совсем не очевидна , по кра
Вот именно : формула для числа корней в общем виде совсем не очевидна , по крайней мере для меня . Любопытно было бы увидеть подробное доказательство .
Я думаю проще попытаться найти контрпример , посчитав число корней x^2=e для групп вида S(p^n) , где р - простое . И сравнить результат .
Извиняюсь , опечатался : хотел написать S(p*2^n) , где р - простое . То есть проверить формулу для групп S3 и S4 для числа корней x^2=e
Я бы посоветовал вместо корневой карты рисовать перестановки в виде циклов (граф где n вершин и направленое ребро из i в p(i)). Потом на картинке показать, что просиходит с перестановкой при возведении в квадрат. Вот так вы наглядно покажете, что нечетные циклы просто перетасовываются, а четные распадаются на 2 цикла одинаковой длины.
Оттуда будет более наглядно видно, что для обратной операции можно циклы нечетной длины перетасовывать определенным образом, а также объединять по 2 цикла одинаковой длины в один. Раз надо все циклы так обработать, то и получается ваш критерий - циклы четной длины должны идти парой с циклом такой же длины.
Как извлечь квадратный корень из перестановки чисел?