Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Результаты поиска КФ ОДЛК порядка 10 в проекте Gerasim@Home за месяц:
ONCE (A):1 - 388584, where:
1 CFs - 33160
2 CFs - 355424
LINE3 (B):1 - 76283, where:
2 CFs - 18735
3 CFs - 57548 (+794)
LINE3 (B):2 - 47509, 8:1, where:
2 CFs - 18735
3 CFs - 28774 (+437)
LINE4 (C):1 - 128, where:
2 CFs - 4
4 CFs - 124
LINE4 (C):2 - 128, where:
2 CFs - 4
4 CFs - 124 (+2)
LINE5 (D):1 - 17, where:
3 CFs - 17
LINE5 (D):2 - 34, where:
3 CFs - 34
LOOP4 (E):2 - 2252, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 648
1TO3 (F):1 - 378, where:
4 CFs - 378
1TO3 (F):3 - 126, where:
4 CFs - 126
1TO4 (G):1 - 1302, where:
3 CFs - 882
5 CFs - 420
1TO4 (G):4 - 546, where:
3 CFs - 441
5 CFs - 105
1TO5 (k):1 - 10, where:
6 CFs - 10
1TO5 (k):5 - 2, where:
6 CFs - 2
1TO6 (H):1 - 42, where:
4 CFs - 24
7 CFs - 18
1TO6 (H):6 - 11, where:
4 CFs - 8
7 CFs - 3
1TO7 (h):1 - 7, where:
8 CFs - 7
1TO7 (h):7 - 1, where:
8 CFs - 1
1TO8 (I):1 - 48, where:
5 CFs - 32
9 CFs - 16
1TO8 (I):8 - 10, where:
5 CFs - 8
9 CFs - 2
RHOMBUS3 (J):2 - 9, where:
5 CFs - 9
RHOMBUS3 (J):3 - 6, where:
5 CFs - 6
RHOMBUS4 (K):2 - 73, where:
3 CFs - 2
4 CFs - 23
5 CFs - 32
6 CFs - 16
RHOMBUS4 (K):4 - 34, where:
3 CFs - 1
4 CFs - 17
5 CFs - 8
6 CFs - 8
FISH (N):1 - 7, where:
4 CFs - 1
6 CFs - 6
FISH (N):2 - 11, where:
4 CFs - 2
6 CFs - 9
FISH (N):4 - 4, where:
4 CFs - 1
6 CFs - 3
TREE1 (V):1 - 2, where:
4 CFs - 2
TREE1 (V):2 - 1, where:
4 CFs - 1
TREE1 (V):3 - 1, where:
4 CFs - 1
CROSS (X):1 - 16, where:
6 CFs - 16
CROSS (X):2 - 4, where:
6 CFs - 4
CROSS (X):4 - 4, where:
6 CFs - 4
DAEDALUS10 (i):1 - 6, where:
12 CFs - 6
DAEDALUS10 (i):2 - 4, where:
12 CFs - 4
DAEDALUS10 (i):4 - 1, where:
12 CFs - 1
DAEDALUS10 (i):10 - 1, where:
12 CFs - 1
FLYER (j):1 - 2, where:
8 CFs - 2
FLYER (j):2 - 3, where:
8 CFs - 3
FLYER (j):4 - 3, where:
8 CFs - 3
VENUS (l):1 - 1, where:
5 CFs - 1
VENUS (l):2 - 3, where:
5 CFs - 3
VENUS (l):4 - 1, where:
5 CFs - 1
DAEDALUS8 (m):1 - 2, where:
6 CFs - 2
DAEDALUS8 (m):2 - 2, where:
6 CFs - 2
DAEDALUS8 (m):4 - 1, where:
6 CFs - 1
DAEDALUS8 (m):8 - 1, where:
6 CFs - 1
RHOMBUS5 (n):2 - 4, where:
5 CFs - 4
RHOMBUS5 (n):5 - 1, where:
5 CFs - 1
1TO10 (o):1 - 5, where:
6 CFs - 5
1TO10 (o):10 - 1, where:
6 CFs - 1
ROBOT (p):1 - 4, where:
5 CFs - 4
ROBOT (p):2 - 4, where:
5 CFs - 4
ROBOT (p):4 - 2, where:
5 CFs - 2
STINGRAY (q):1 - 1, where:
5 CFs - 1
STINGRAY (q):2 - 3, where:
5 CFs - 3
STINGRAY (q):3 - 1, where:
5 CFs - 1
Эксперимент по исследованию свойств окрестностей обобщенных симметрий:
* парастрофический срез 1 [Px Py Pv]: пройдено 638 (+21) окрестностей из 903 (70,6%, +2,3%);
* парастрофический срез 3 [Py Px Pv]: пройдено 122 (+24) окрестностей из 1764 (6,9%, +1,4%).
Эксперимент по исследованию свойств ДЛК порядка 9:
* проект Gerasim@Home — завершена обработка линеек 1, 2, 3, 5, 6, 9, 17, 20; в обработке линейка 7;
* проект RakeSearch — завершена обработка линеек 4, 10, 14, 18, 19; ожидаются хвосты от линеек 8, 11; в обработке линейка 12.
Итого: обработано 45,29% пространства перебора, найдено 55515 КФ ОДЛК и 406 новых комбинаторных структур.
При входе на https://gerasim.boinc.ru/ браузер жалуется на неверный сертификат.
"As7.asx.local"
Цитата: kotenok2000 от 02.11.2020, 00:44При входе на https://gerasim.boinc.ru/ браузер жалуется на неверный сертификат.
"As7.asx.local"
Это потому, что я не знаю, где взять(или сделать) правильный сертификат, и как его подсунуть Герасиму.
"As7.asx.local" - это максимум, на что я оказался способен. 
Делал в IIS, там же и подсунул.
Вообще-то, As7.asx.local - это локальный сервер, на котором крутится Герасим.
Ребятки, может кто-нибудь напишет как надо сделать?
Можно попробовать сие: https://www.snel.com/support/how-to-install-lets-encrypt-with-iis-on-windows-server-2019/
@AenBleidd, Спасибо за отклик. Похоже, это то что нужно, но определённо сказать не могу. Герасим стоит на Windows Server 2008r2 и IIS у него такой-же древний. И Visual Studio, SQL 2008 и всё остальное.,
Надо маленько обновить платформу. Для этого поставил на рабочую машинку SATA диск 250 GB и соответственно Winows Server 2016, Visual Studio 2019, SQL 2019.
Новый "MS SQL Server" уже проверил. Герасимовские базы он себе устанавливает(из бэкапов). Вроде бы всё ок. IIS пока не устанавливал. Надо перенести операционку и всё остальное с SATA диска на RAID-0. Этим сейчас и занимаюсь. Если на рабочей машинке всё заработает, тогда начну обновление Герасима и Сертификата.
*перенести Систему с SATA диска на RAID-0 пока не получается. Чего только не пробовал. Загружаиться с рэйда система не хочет. Раньше я просто клонировал системный диск на рэйд. А сейчас - не тут-то было! мой"Disk Clone" устарел и уже не запускается.. Ну чёрти что.. 
Для обновления рабочей машинки(Core Quad 3,0 GHz) купил:
Материнская плата ASUS ROG CROSSHAIR VIII HERO. процессор Райзен 5 3500(6 ядер, 6 потоков) и две планки памяти по 16 GB каждая(итого 32 GB). https://www.regard.ru/catalog/tovar357903.htm
Материнка:
https://www.regard.ru/catalog/tovar324393.htm
Всем привет и хорошего настроения.
В дополнение к предыдущему посту (см. https://vk.com/wall162891802_1418) приведем описание нескольких практических оптимизаций, оказывающихся полезными при вычислении функции Эйлера через циклические латинские квадраты.
Прежде всего, можно не хранить все строки формируемого ЛК, а только текущую. Но множества использованных в столбцах значений элементов хранить все равно необходимо, емкостная сложность снижается с 2*N^2 до N^2 + N, а в асимптотике — не снижается вовсе, оставаясь квадратичной.
Проверку корректности формируемого квадрата можно организовать не по строкам, а по столбцам. А если подумать, то только по одному столбцу, для определенности — по первому. Несложно показать, что в формируемом квадрате первый столбец будет состоять из значений
0
0 + d (mod N)
0 + 2*d (mod N)
0 + 3*d (mod N)
...
0 + i*d (mod N)
...
0 + (N-1)*d (mod N)
Например, для приведенного выше примера с N=6 и d=5 получаем:
0
0 + 5 (mod 6) = 5
0 + 10 (mod 6) = 4
0 + 15 (mod 6) = 3
0 + 20 (mod 6) = 2
0 + 25 (mod 6) = 1
Все верно. Второй столбец будет образован значениями
1
1 + d (mod N)
1 + 2*d (mod N)
1 + 3*d (mod N)
...
1 + i*d (mod N)
...
1 + (N-1)*d (mod N)
третий — значениями
2
2 + d (mod N)
2 + 2*d (mod N)
2 + 3*d (mod N)
...
2 + i*d (mod N)
...
2 + (N-1)*d (mod N)
и т.д. Цель проверки на корректность — убедиться в том, что все значения в столбце различны. Несложно показать, что если значения различны в одном столбце, то они будут различны и во всех остальных. А значит, что проверять можно только один из столбцов, что и было отмечено выше. Математически проверка сводится к тому, чтобы среди значений
v1 = d (mod N)
v2 = 2*d (mod N)
v3 = 3*d (mod N)
...
vi = i*d (mod N)
...
v{N-1} = (N-1)*d (mod N)
не было повторов (в случае отсутствия повторов они формируют множество {1, 2, 3, ..., N-1}). Таким образом, упрощенный вариант алгоритма сводится к следующему: для всех смещений d (0 < d < N) убедиться в неповторяемости значений i*d (mod N) для всех i (0 < i < N). Несложно заметить, что в данном алгоритме t ~ O(N^2) (в N раз меньше, чем в предыдущем варианте реализации "в лоб"), а для проверки неповторяемости нужен линейный массив из N булевых элементов, т.е. m ~ O(N) (тоже в N раз меньше реализации "в лоб").
Несложно заметить, что для заданных d и N уникальность всех значений i*d (mod N) для всех i (0 < i < N) является ни чем иным, как проверкой чисел d и N на взаимную простоту. Повторяя эту проверку для всех d, получаем значение функции Эйлера по определению. И без делений! Это к вопросу, доказано ли, или просто установлено — теперь доказано!
Но ведь в формулах есть операции по модулю N, а нахождение остатка от деления ничем не хуже самого деления? Казалось бы, есть противоречие... Однако при практической программной реализации при переходе от итерации к итерации можно использовать код вроде
curr_value = 0;
for (i = 1; i < N; i++) {
curr_value += d;
if (curr_value >= N)
curr_value -= N;
// Проверка уникальности значения curr_value
...
}
В котором нет не только делений, но и даже умножений, т.е. код проверки очень простой и эффективный.
Несложно показать, что повторы можно искать не во всех значения, а можно ожидать только повтора значения 0, который встретится через N итераций в случае взаимной простоты N и d, и раньше в случае, если указанная пара чисел имеет общие делители. Это позволяет отказаться от использования массива для проверки дублирования значений, сократив емкостную сложность алгоритма до m ~ O(1).
Ну и напоследок про симметрию. Очевидно, что сдвиг строк циклического квадрата вправо на d позиций и влево на d позиций будет давать один и тот же результат с позиции свойств получаемого квадрата (один квадрат из другого можно получить путем отражения по горизонтали с последующей нормализацией по первой строке). А раз так, то проверять можно не все d, а только в диапазоне [2, floor((N-1)/2)] (проверок в 2 раза меньше!). Если для некоторого d квадрат получился корректным, то и для d' = N-d = -d (mod N) он тоже будет корректным. Для четных N при этом остается непроверенным центральное значение d = N/2, но его можно и не проверять, квадрат для него корректным не будет, т.к. N/2 и N не взаимно просты. Учет этой особенности позволяет снизить время работы программы примерно в 1.8x-1.9x раза. Однако O(N^2) на практике все равно оказывается медленнее, чем O(sqrt(N)), что наглядно демонстрирует скриншот внизу.
Теперь пару слов о длинной арифметике... Для алгоритма RSA, который использует в своем составе вычисление функции Эйлера, важна работа с n=1024-разрядными двоичными числами (308 цифр в десятичной форме записи). Для их обработки и требуется длинная арифметика. Т.е. в данном случае число двоичных разрядов — n, значение аргумента функции Эйлера (с точностью до порядка) — N = 2^n. Кратко пробежавшись по литературе, результаты (асимптотические временнЫе сложности основных необходимых операций в длинной арифметика):
* сложение: O(n);
* умножение:
** O(n^1.59) по методу Карацюбы;
** O(n^1.4) по методу Тоома (приблизительно);
** O(n * log(n)) через дискретное преобразование Фурье (на практике эффективно для существенно больших чисел, чем в нашем примере);
* деление: O(n^1.4) по алгоритму Бурникеля — Циглера (см. https://ru.wikipedia.org/wiki/Алгоритм_Бурникеля_—_Циглера), значение экспоненты определяется алгоритмом умножения Тоома.
Таким образом, вычисление функции Эйлера через факторизацию потребует приблизительно sqrt(N) x n^1.4 = sqrt(2^n) * n^1.4 = 2^(n/2) * n^1.4 шагов (с точностью до константы), а через циклические квадраты — N^2 * n = 2^(2*n) * n. Выигрыш n ("длинные" сложения) по сравнению с n^1.4 ("длинные" деления) с лихвой компенсируется проигрышем в сравнении 2^(n/2) vs 2^(2*n), причем на много порядков. Таким образом, очень похоже на то, что и на длинной арифметике выиграть через циклические квадраты не получится.
PS. Выражаю благодарность citerra'е за конструктивное обсуждение и критику идеи!
Оказывается не все пандиагональные ЛК являются циклическими!
7 1 0 3 6 5 12 2 8 9 10 11 4
2 3 4 10 0 7 6 9 12 11 5 8 1
4 11 1 7 8 9 10 3 6 0 12 2 5
6 5 8 11 10 4 7 0 1 2 3 9 12
8 9 2 5 12 11 1 4 3 10 0 6 7
3 6 12 0 1 2 8 11 5 4 7 10 9
10 0 3 2 9 12 5 6 7 8 1 4 11
1 7 10 4 3 6 9 8 2 5 11 12 0
11 4 5 6 7 0 3 10 9 12 2 1 8
5 8 7 1 4 10 11 12 0 6 9 3 2
12 2 9 8 11 1 0 7 10 3 4 5 6
9 10 11 12 5 8 2 1 4 7 6 0 3
0 12 6 9 2 3 4 5 11 1 8 7 10
Пандиагональный, но не циклический! Спасибо Andrew Howroyd и статье https://www.researchgate.net/publication/270884574_Constructing_non-cyclic_pandiagonal_Latin_squares_of_prime_orders
Циклические латинские квадраты готовы: https://oeis.org/A338522
Информация о том, что число циклических ЛК определяется функцией Эйлера, добавлена в OEIS:
Это очень приятно с учетом того, что данная последовательность является "ядреной" (англ. core), т.е. одной из основных, ключевой в комбинаторике, и ее удалось расширить. Попросили подготовить публикацию в рецензируемом издании и желательно не на русском языке, чем видимо придется заняться в самом ближайшем будущем.