Форум

Уважаемые посетители. В связи с массовой регистрацией на форуме спамовых и рекламных аккаунтов нам пришлось установить некоторые защитные программные блоки. Если при регистрации на Ваш почтовый адрес не придет письмо с паролем для активации учетной записи, прошу написать на адрес tpp12@rambler.ru или boinc.ru@yandex.ru. Я активирую учетку в ручную и вышлю Вам временный пароль.
Пожалуйста or Регистрация для создания сообщений и тем.

Проект Gerasim@Home

Результаты поиска КФ ОДЛК порядка 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 новых комбинаторных структур.

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array

При входе на https://gerasim.boinc.ru/ браузер жалуется на неверный сертификат.

"As7.asx.local"

Array
Цитата: kotenok2000 от 02.11.2020, 00:44

При входе на https://gerasim.boinc.ru/ браузер жалуется на неверный сертификат.

"As7.asx.local"

Это потому, что я не знаю, где взять(или сделать) правильный сертификат, и как его подсунуть Герасиму.

"As7.asx.local" - это максимум, на что я оказался способен. 🙁 Делал в IIS, там же и подсунул.

Вообще-то, As7.asx.local - это локальный сервер, на  котором крутится Герасим.

Ребятки, может кто-нибудь напишет как надо сделать?

 

Array

Можно попробовать сие: https://www.snel.com/support/how-to-install-lets-encrypt-with-iis-on-windows-server-2019/

Array

@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

Всем привет и хорошего настроения. 🙂

 

Array
evatutin и PinkFloyd отреагировали на эту запись.
evatutinPinkFloyd

В дополнение к предыдущему посту (см. 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'е за конструктивное обсуждение и критику идеи! 🙂

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array
hoarfrost отреагировал на эту запись.
hoarfrost

Оказывается не все пандиагональные ЛК являются циклическими!

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

Array
hoarfrost отреагировал на эту запись.
hoarfrost

Циклические латинские квадраты готовы: https://oeis.org/A338522

Теперь очередь за циклическими диагональными: https://oeis.org/draft/A338562
 
PS. Науки, как известно, бывают естественные, не естественные и противоестественные :), а квадраты бывают циклические, полуциклические и пандиагональные, причем, как оказалось, это совсем даже не одно и то же начиная с порядка N=13 (спасибо Andrew Howroyd за ряд ценных комментариев!). Надо отразить это в OEIS...
Array
hoarfrost и SerVal отреагировали на эту запись.
hoarfrostSerVal

Информация о том, что число циклических ЛК определяется функцией Эйлера, добавлена в OEIS:

https://oeis.org/A000010

Это очень приятно с учетом того, что данная последовательность является "ядреной" (англ. core), т.е. одной из основных, ключевой в комбинаторике, и ее удалось расширить. Попросили подготовить публикацию в рецензируемом издании и желательно не на русском языке, чем видимо придется заняться в самом ближайшем будущем.

Array
ale4316 и SerVal отреагировали на эту запись.
ale4316SerVal
Цитата: evatutin от 04.11.2020, 11:41

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

Я сперва прочитал "в нецензурном издании" xD

Array