Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
По результатам расчетов в проектах Gerasim@Home (http://gerasim.boinc.ru) и RakeSearch (https://rake.boincfast.ru/rakesearch/) найдены еще 6 новых комбинаторных структуры из ДЛК порядка 9:
1. 26N74M26C - 012345678120483567465721380657832401346570812783164025274608153801256734538017246
2. 28N81M14C - 012345678123486750756120483534861207645078312807234561480753126261507834378612045
3. 28N81M28C - 012345678120486753401857362834561207368274015675038124756123480547602831283710546
4. 32N82M10C - 012345678123876054756028431678450123205613847431287560847502316560134782384761205
5. 36N93M18C - 012345678123458067345876210587601432601234785234587106750163824876012543468720351
6. 48N117M18C - 012345678120478536867153024601582347273014865458736210736820451345601782584267103
Пройдено 41,64% пространства перебора, всего найдено 52207 КФ ОДЛК порядка 9.
Циклические ДЛК и пандиагональные ДЛК. Один и тот же тип квадратов или разные?
Существует 2 специальных типа ДЛК:
* циклические — каждая строка i+1 получена из строки i путем циклического смещения на d позиций;
* пандиагональные — все ломаные диагонали (параллельны главной) и ломаные антидиагонали (параллельны побочной) являются трансверсалями.
Определения вроде бы разные и задают разные квадраты, но... Полным перебором всех нормализованных ДЛК для N <= 8 установлено, что все циклические ДЛК являются пандиагональными ДЛК и наоборот:
Зависимость числа пандиагональных ДЛК от N: 1, 0, 0, 0, 2, 0, 4, 0 (https://oeis.org/A123565)
Зависимость числа циклических ДЛК от N: 1, 0, 0, 0, 2, 0, 4, 0 (https://oeis.org/A123565)
Далее был организован небольшой эксперимент, в ходе которого производилось построение всех циклических ЛК порядка N<=25 с их проверкой на пандиагональность: все они оказались пандиагональным. По итогам мини эксперимента можно предположить, что все циклические ДЛК являются пандиагональными. Однако открытым остается вопрос: существуют ли не циклические пандиагональные ДЛК порядков N>8? Пока таковых обнаружить не удалось, однако это не гарантирует, что их нет вообще...
О вычислении функции Эйлера с использованием циклических латинских квадратов
Несколькими днями ранее было установлено, что число циклических ЛК порядка N равно функции Эйлера phi(N) (см. https://oeis.org/A000010, https://vk.com/wall162891802_1408). А раз так, то ее значение можно считать через латинские квадраты... На практике для вычисления ее значения используют либо подсчет числа k (1 <= k < n), взаимно простых с n (расчет по определению), либо разложение n на простые сомножители по основной теореме арифметики (см. https://ru.wikipedia.org/wiki/Основная_теорема_арифметики) n = p1^a1 * p2^a2 * ... * pm^am (p1, p2, ..., pm — простые числа) с последующим вычислением искомого значения функции Эйлера с использованием ее свойства мультипликативности: phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm). Первый способ наиболее эффективно реализуется с использованием алгоритма Евклида (см. https://ru.wikipedia.org/wiki/Алгоритм_Евклида), второй требует факторизации числа n. Первый способ при практической программной реализации медленнее, поэтому обычно на практике применяется второй. Оба способа требуют операций деления или остатка от деления, что не всегда удобно (особенно при реализации операций длинной арифметики или в виде специализированного вычислителя), алгоритм Евклида еще и не распараллеливается (поправьте меня, если я не прав). Указанных недостатков лишен предлагаемый способ вычисления через циклические ЛК...
Простейшей практической реализацией метода определения функции Эйлера через циклические ЛК порядка N является следующий: для каждого смещения d (0 < d < N) формируется ЛК, который проверяется на корректность, число корректных ЛК представляет собой искомое значение функции Эйлера. Некорректность может возникать в некоторых случаях из-за дублирования значений в столбцах формируемого циклического ЛК. Например, для N=6 есть как корректные квадраты, так и нет:
d=1
0 1 2 3 4 5
1 2 3 4 5 0
2 3 4 5 0 1
3 4 5 0 1 2
4 5 0 1 2 3
5 0 1 2 3 4
корректный
d=2
0 1 2 3 4 5
2 3 4 5 0 1
4 5 0 1 2 3
0 1 2 3 4 5
2 3 4 5 0 1
4 5 0 1 2 3
некорректный
d=3
0 1 2 3 4 5
3 4 5 0 1 2
0 1 2 3 4 5
3 4 5 0 1 2
0 1 2 3 4 5
3 4 5 0 1 2
некорректный
d=4
0 1 2 3 4 5
4 5 0 1 2 3
2 3 4 5 0 1
0 1 2 3 4 5
4 5 0 1 2 3
2 3 4 5 0 1
некорректный
d=5
0 1 2 3 4 5
5 0 1 2 3 4
4 5 0 1 2 3
3 4 5 0 1 2
2 3 4 5 0 1
1 2 3 4 5 0
корректный
Таким образом, получено N-1 = 5 ЛК, из которых 3 некорректных и 2 корректных, phi(6) = 2. (Для d=0 или d=N, что одно и то же, квадраты всегда будут некорректными, т.к. они состоят из одинаковых строк, их можно не рассматривать.)
Оценим вычислительную сложность данного алгоритма проверки. Проверить требуется N-1 смещение d. При каждой проверке на корректность формируемого ЛК производится определение N-1 строки ЛК (первая фиксирована и не меняется) по N элементов, сама проверка реализуется путем заполнения одномерного булева массива с уже использованными в столбце значениями за время, не зависящее от N. Таким образом, временнАя сложность алгоритма составляет величину порядка t ~ O(N^3). На хранение формируемого ЛК требуется N^2 ячеек, на хранение вектора использованных в столбце булевых значений — N ячеек, для N столбцов — суммарно N^2 ячеек, т.е. емкостная сложность алгоритма составляет m ~ O(N^2).
В ходе оптимизации кода проверки временнУю сложность можно сократить до t ~ O(N^2), а емкостную — до m ~ O(N). Причем в коде после выполнения оптимизации нет не только делений, но и даже умножений, т.е. код проверки очень простой и эффективный.
Теперь от теории к практике. Была разработана программная реализация 4 способов вычисления функции Эйлера:
1 — через факторизацию (забегая вперед, самая быстрая даже с примитивным алгоритмом факторизации путем перебора делителей до sqrt(N));
2 — через подсчет взаимно простых чисел с использованием алгоритма Евклида (медленнее);
3 — через построение и подсчет корректных циклических ЛК "в лоб" (самая медленная);
4 — через построение и подсчет корректных циклических ЛК с оптимизациями (быстрее реализации "в лоб", медленнее алгоритма Евклида).
Т.е. пока быстрее существующих аналогов сделать не получилось, все-таки k1*N^2 > k2*sqrt(N), пусть и при k1 « k2. Но у текущей реализации, отметим еще раз, есть ряд ключевых преимуществ:
* отсутствие необходимости в операциях деления и умножения (что может быть особенно эффективно при длинной арифметике);
* отличный потенциал для распараллеливания (вплоть до N^2 потоков, правда дополнительные проверки могут потребовать времени порядка O(log(N))).
Таким образом, есть робкая надежда, что открыт новый способ вычисления значения функции Эйлера через циклические латинские квадраты (если это повторяет какие-то работы из теории групп, в которой я не являюсь крупным специалистом, прошу дать мне знать!). Данный результат имеет практическое значение, выражающееся в возможности организации атаки на известный алгоритм RSA, в основе которого как раз и лежит сложность вычисления значения функции Эйлера от произведения пары больших простых чисел... Для текущей реализации это не будет особенно эффективным, однако она работает, а значит при необходимости ее можно дополнительно поковырять на предмет распараллеливания... 
Да и не только в RSA применяется функция Эйлера...
На мой, непросвещенный взгляд, это чертовски интересно. Даже если этот метод не будет наиболее эффективным, - само его наличие - большое дело. И это может оказаться реальным "выхлопом" "непонятных латинских квадратов"
Цитата: AlexA от 28.10.2020, 21:38На мой, непросвещенный взгляд, это чертовски интересно. Даже если этот метод не будет наиболее эффективным, - само его наличие - большое дело. И это может оказаться реальным "выхлопом" "непонятных латинских квадратов"
Пока получается менее эффективно по сравнению с разложением на множители. Но у меня есть определенные надежды, что при обработке больших аргументов (для этого потребуется длинная арифметика) + распараллеливание нашей реализации соотношение затрат вычислительного времени может сместиться в нашу пользу. Одним словом надо садиться и пробовать, оценивать...
PS. Я тут списался с коллегами — взаимная простота интересна еще и в полях Галуа при декодировании кодов Рида-Соломона... А тем же подходом мы и ее определять можем. Я не утверждаю, что это будет эффективно и лучше, чем имеющиеся аналоги, но попробовать поработать в эту сторону тоже можно... Тем более, мне попадались работы, где квадрат порождается многочленами из полей Галуа, но глубоко в них я не втыкался, возможно стОит...
По результатам расчетов в проектах Gerasim@Home (http://gerasim.boinc.ru) и RakeSearch (https://rake.boincfast.ru/rakesearch/) найдены еще 7 новых комбинаторных структур из ДЛК порядка 9:
1. 24N80M12C - 012345678120458736365271084453782160534867201608514327271036845847603512786120453
2. 28N85M14C - 012345678120486753481750362764531280638274015375068124856123407547602831203817546
3. 31N79M21C - 012345678123458067376812540287501436561034782634287105450763821845670213708126354
4. 35N85M35C - 012345678120486735856123407738561240384672051473058126645710382567204813201837564
5. 36N93M18C - 012345678120478536278534160601782345367251084453016827536827401845603712784160253
6. 56N126M28C - 012345678120478536534867201601584327453712860278036145845603712367251084786120453
7. 77N193M55C - 012345678123478056568231704480752163754860231635014827271586340847603512306127485
Пройдено 42,61% пространства перебора, всего найдено 53476 КФ ОДЛК порядка 9.
Надо бы в Wikipedia, на страницах про латинские квадраты, на русском, английском:
https://ru.wikipedia.org/wiki/%D0%9B%D0%B0%D1%82%D0%B8%D0%BD%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82
https://en.wikipedia.org/wiki/Latin_square
и, по возможности, на других языках указать, сделать ссылки, что их поиском занимаются Gerasim@Home и RakeSearch
Кто у нас с форума занимается правкой wikipedia ?
О числе перестановочных ЛК и ДЛК
Недавно мы научились считать функцию Эйлера без умножений и делений. А нельзя ли сделать что-то подобное с другими функциями? Например, с факториалом? Оказывается, что можно...
Попытаемся обобщить понятие циклических ЛК, в которых, напомню, каждая следующая строка получается путем циклического сдвига предыдущей на d позиций. Подобный сдвиг можно описать следующим образом:
(1) str[i+1] := P(str[i]),
где P — циклическая перестановка. Например, для d=1
P = [1, 2, 3, 4, ..., N-1, 0],
для d=2:
P = [2, 3, 4, ..., N-1, 0, 1]
и т.д. Несложно убедиться в том, что число подобных перестановок равно N и соответствующее число циклических ЛК не превосходит N (точнее, N-1, т.к. для d=0 ЛК будет корректным только в вырожденном случае N=1, для всех остальных размерностей будут дублирования одних и тех же значений в столбцах). А нельзя ли найти другие перестановки, для которых аналогично рассмотренному выше по формуле (1) можно построить корректный ЛК или ДЛК? Оказывается, можно, и их количество превосходит N. Фактически, имея на входе такую перестановку, можно по ней построить ЛК и посмотреть на его свойства. Зависимости числа таких ЛК и ДЛК, которые будем называть перестановочными (не путать со строчно-перестановочными ОДЛК, поиск которых производился в проекте RakeSearch!), приведены ниже.
Для ЛК: 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 — факториал (https://oeis.org/A000142)
Для ДЛК: 1, 0, 0, 0, 2, 0, 4, 0, 0, 0, 8, 0 — https://oeis.org/A123565
Видно, что для порядка N число таких перестановочных ЛК равно (N-1)!, что неожиданно. Число соответствующих ДЛК не отличается от числа циклических (пандиагональных) ДЛК. Для наиболее интересного для нас порядка N=10 данные ЛК имеют ровно 0 трансверсалей, что не позволяет получить от них ни ДЛК, ни тем более ОДЛК с потенциально интересными свойствами. Зато теперь мы еще умеем считать факториал без умножений...
PS. Примеры квадратов и порождающих их перестановок:
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 0
2 3 4 5 6 7 8 9 0 1
3 4 5 6 7 8 9 0 1 2
4 5 6 7 8 9 0 1 2 3
5 6 7 8 9 0 1 2 3 4
6 7 8 9 0 1 2 3 4 5
7 8 9 0 1 2 3 4 5 6
8 9 0 1 2 3 4 5 6 7
9 0 1 2 3 4 5 6 7 8
P = [1,2,3,4,5,6,7,8,9,0]
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 9 0 8
2 3 4 5 6 7 9 8 1 0
3 4 5 6 7 9 8 0 2 1
4 5 6 7 9 8 0 1 3 2
5 6 7 9 8 0 1 2 4 3
6 7 9 8 0 1 2 3 5 4
7 9 8 0 1 2 3 4 6 5
9 8 0 1 2 3 4 5 7 6
8 0 1 2 3 4 5 6 9 7
P = [1,2,3,4,5,6,7,9,0,8]
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 8 0 9 7
2 3 4 5 6 8 9 1 7 0
3 4 5 6 8 9 7 2 0 1
4 5 6 8 9 7 0 3 1 2
5 6 8 9 7 0 1 4 2 3
6 8 9 7 0 1 2 5 3 4
8 9 7 0 1 2 3 6 4 5
9 7 0 1 2 3 4 8 5 6
7 0 1 2 3 4 5 9 6 8
P = [1,2,3,4,5,6,8,0,9,7]
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 8 9 7 0
2 3 4 5 6 8 7 0 9 1
3 4 5 6 8 7 9 1 0 2
4 5 6 8 7 9 0 2 1 3
5 6 8 7 9 0 1 3 2 4
6 8 7 9 0 1 2 4 3 5
8 7 9 0 1 2 3 5 4 6
7 9 0 1 2 3 4 6 5 8
9 0 1 2 3 4 5 8 6 7
P = [1,2,3,4,5,6,8,9,7,0]
У всех перестановок P, порождающих соответствующие им перестановочные ЛК, структура мультимножества длин циклов одна и та же: {N}, т.е. все элементы перестановок входят в один цикл максимальной длины, что и определяет число таких перестановок, равное (N-1)!.
Число циклических ЛК и ДЛК с фиксированной первой строкой мы посчитали, а общее число — упустили, восполняем этот пробел. Как и с большинством других типов ЛК/ДЛК искомое число отличается от числа ЛК/ДЛК с фиксированной первой строкой на N!. Соответственно, получаем следующие числовые ряды:
ЛК — 1, 2, 12, 48, 480, 1440, 30240, 161280, 2177280, 14515200, 399168000, 1916006400, 74724249600, 523069747200, 10461394944000, 167382319104000, 5690998849536000, 38414242234368000, 2189611807358976000
ДЛК — 1, 0, 0, 0, 240, 0, 20160, 0, 0, 0, 319334400, 0, 62270208000, 0, 0, 0, 4979623993344000, 0, 1946321606541312000, 0, 0, 0
Оба не представлены в OEIS.