Пентадекатлон мечты

[Dmitriy40]

А где они были? В help я их не увидел.
Просто читая описание метода факторизации по эллиптическим кривым я вижу что некоторые параметры выбираются случайным образом и нигде нет ограничения сверху на количество их вариантов, т.е. не полным перебором всех возможных вариантов, а значит нет гарантии что делитель будет обнаружен за фиксированное число циклов проверки. Правда и контрпример построить мне не удалось.
С другой стороны, посчитав примерное количество операций для нахождения делителя длиной 45 знаков по формуле из рувики я получил величину порядка $10^{18}$, что при скорости даже в $10^{10}$ операций в секунду (а это нереально много) даёт время нахождения делителя в $10^8$ секунд или больше 3 лет счёта. Алперон же проверяет 45-значные делители якобы максимум за дни. Подозрительно быстро! И похоже что-то тут не так с терминологией ...

[VAL]

В отличие от некоторых других методов факторизации, кухню ECM я не знаю.
Но...
ЕСМ ведь не вероятностный, а детерминированный алгоритм. Просто, чем больше число, тем сильнее он тормозит.
Кроме того у Алперна есть совет, как ускорить разложение, коим я регулярно пользуюсь. Для этого надо параллельно запустить несколько потоков, указывая лишь диапазоны номеров используемых кривых.
Не представляю, как это было бы возможно, если бы выбор кривых был случайным.

Кстати, в пояснениях к методу у Алперна напрямую приводится таблица соответствия номеров кривых и значности искомых множителей.

[Dmitriy40]

VAL в сообщении #1699121 писал(а):

ЕСМ ведь не вероятностный, а детерминированный алгоритм.

Насколько я понимаю он детерминированный в смысле что даёт точный ответ, но вероятностный в смысле что неизвестно когда именно будет получен ответ - вроде как это должно зависеть от выбора кривой и её параметров, а это случайное, YAFU кстати именно что случайно выбирает кривые, вполне может в следующем запуске считать сильно иначе (минуты вместо часов и наоборот). Да и слова типа "если не подошло, выбрать другое и повторить с начала" прямо намекают на недерминированность времени счёта (но не конечного результата).
Табличку я видел, но как понял она лишь рекомендует выбор оптимальных параметров кривых в зависимости от ожидаемого размера делителя, но не в обратную сторону. Так что ничего не гарантирует.
Правда тогда не понимаю почему оценка времени счёта даётся в зависимости от величины наименьшего делителя, ведь тогда он типа находится гарантированно (это вот и непонятно, есть ли гарантия) за вот это время что ли? Или это лишь мат.ожидание, среднее в каком-то смысле ...

Просто если можно быстро доказать что делителя нет в каком-то диапазоне (например менее 45 цифр), то это же уже нарушает NP сложность факторизации.

[VAL]

Dmitriy40 в сообщении #1699133 писал(а):

VAL в сообщении #1699121 писал(а):

ЕСМ ведь не вероятностный, а детерминированный алгоритм.

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

То что YAFU выбирает случайно, не гарантирует, что Alpertron тоже. Очень похоже, что он совершает перебор кривых, гарантирующий разложение в случае наличия множителей, определяемых этими кривыми. В пользу этого говорит и факт, про который я читал (не помню где): ECM подходит для отыскания "небольших" множителей или констатации их отсутствия.

Цитата:

Табличку я видел, но как понял она лишь рекомендует выбор оптимальных параметров кривых в зависимости от ожидаемого размера делителя, но не в обратную сторону. Так что ничего не гарантирует.
Правда тогда не понимаю почему оценка времени счёта даётся в зависимости от величины наименьшего делителя, ведь тогда он типа находится гарантированно (это вот и непонятно, есть ли гарантия) за вот это время что ли? Или это лишь мат.ожидание, среднее в каком-то смысле ...

Просто если можно быстро доказать что делителя нет в каком-то диапазоне (например менее 45 цифр), то это же уже нарушает NP сложность факторизации.

Не вижу нарушений. Скажем, я могу перебором снизу убедиться в отсутствии множителей до $10^{10}$. И чего это нарушает? Кроме того, что значит "быстро"? У меня 15 потоков Ryzen 9 молотили больше суток.

Я хоть и спорю, но сомнения во мне Вы посеяли. Тем самым, отложив на пару суток констатацию, что

$M(972)\ge 8$.

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

(Оффтоп)

$n=7378711511814667915014747119345616747246110616880988960531272638307322602887651602029433997459131422926048708247398317 04194205737512890621$

$61225516322405420311381102984214112067 | n+7$

$11468104526861504295209515756109239006883 | n$

или

$n=754160484416403282094724852369515219555448026336551510746387570432533227019875415900771407513794452337036314839289387304058696956512890621$

$4225264375128824860412216586418103563 | n$

[Dmitriy40]

VAL в сообщении #1699422 писал(а):

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

Я вот что-то не припомню где бы видел "констатации отсутствия" ... Но особо не интересовался, мог и не понять.

VAL в сообщении #1699422 писал(а):

Не вижу нарушений. Скажем, я могу перебором снизу убедиться в отсутствии множителей до $10^{10}$. И чего это нарушает? Кроме того, что значит "быстро"? У меня 15 потоков Ryzen 9 молотили больше суток.

Если можно посчитать сильно быстрее полного перебора (NP) - то нарушает.
А "быстро" - на порядки быстрее оценки, я же привёл выше, порядка $10^{18}$ операций (плюс вряд ли маленький константный множитель), даже если Ваш Ryzen делает $10^{11}$ операций в секунду (повторюсь, это нереально много), всё равно это $10^7$ секунд или 115 дней. И за "пару дней" такого никак не вычислить.

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

[VAL]

Dmitriy40 в сообщении #1699435 писал(а):

VAL в сообщении #1699422 писал(а):

Не вижу нарушений. Скажем, я могу перебором снизу убедиться в отсутствии множителей до $10^{10}$. И чего это нарушает? Кроме того, что значит "быстро"? У меня 15 потоков Ryzen 9 молотили больше суток.

Если можно посчитать сильно быстрее полного перебора (NP) - то нарушает.
А "быстро" - на порядки быстрее оценки, я же привёл выше, порядка $10^{18}$ операций (плюс вряд ли маленький константный множитель), даже если Ваш Ryzen делает $10^{11}$ операций в секунду (повторюсь, это нереально много), всё равно это $10^7$ секунд или 115 дней. И за "пару дней" такого никак не вычислить.

Не вижу, в чем нарушение.
Скажем, функции $10^x$ и $1.1^{0.1x}$ обе обязательно обгонят $x^2$, но для разных $x$.
Так и тут. Полный перебор уйдет в фактическую бесконечность для 40-значных чисел, ECM - для 120-значных, а метод решета числового поля 220-значных. Везде рост экспоненциальный, но с разными параметрами.

Цитата:

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

Спасибо!
Хотя, я не знаю, что значит, нужные? Но если какой-то случай меня зацепит, обращусь.
У меня была такая мысль для $k=648$. Но базовая программка на PARI поставляла кандидатуры настолько исправно, что было ясно: рано или поздно найдется цепочка, где все числа разложатся быстро.

[Dmitriy40]

VAL в сообщении #1699458 писал(а):

Не вижу, в чем нарушение.

Возможно я и не прав про нарушение NP полноты. И действительно время наверстается потом на больших делителях.

VAL в сообщении #1699458 писал(а):

Но базовая программка на PARI поставляла кандидатуры настолько исправно, что было ясно: рано или поздно найдется цепочка, где все числа разложатся быстро.

Ну вот и ответ - если пару-тройку дней (быстрее я всё равно вряд ли успею, пока прочитаю, пока посчитает, пока тоже увидите) не получается найти ни делитель, ни легко разлагаемые числа, то пишите (можно и ЛС).

[VAL]

База просчитанных случаев стала слишком большой.
Сегодня обнаружил, что 3-й день ищу цепочку из 8-и чисел по 588 делителей, которую я, оказывается уже нашел (причем не 3 года, а менее месяца тому назад, и не за три дня, а за один)
Причем я даже опубликовал начальное число цепочки и обновил данные в одной из таблиц, куда заношу все результаты. А в другой - забыл. И именно на основании другой таблицы приступил к повторному поиску.

Дабы впредь избежать подобных эксцессов я ... изготовил еще одну таблицу
Речь идет только о длинных цепочках.

В процессе наполнения нашел кое-какие странности. Например, нашлась готовая программа для $k=960$ (с виду, вполне берущийся случай), а следов запуска этой программы я не обнаружил.

Есть и другие вопросы. Так, насколько я помню, поиск цепочки длиннее 11 для $k=84$ интенсивно проводился (скорее всего Евгением), но искать подтверждение этому в дву с лишним сотнях страниц темы = убить еще полдня.

В общем, буду благодарен за любые уточнения и исправления (табличка сырая).

Кстати, я внес туда не только $k$, для которых есть длинные цепочки, но и перспективные.

[Dmitriy40]

VAL в сообщении #1699626 писал(а):

Так, насколько я помню, поиск цепочки длиннее 11 для $k=84$ интенсивно проводился (скорее всего Евгением), но искать подтверждение этому в дву с лишним сотнях страниц темы = убить еще полдня.

Сомневаюсь: папка M84n11_x32SSE у меня есть, а вот других папок с 84 в имени нет.
Я пытался посмотреть на M84n13, но даже список паттернов не получил, только очень предварительные прикидки. И было это месяцем ранее M84n11. Так что думаю длиннее 11 никто всерьёз не искал. А нашли лишь длиной 10.

[VAL]

Dmitriy40 в сообщении #1699637 писал(а):

VAL в сообщении #1699626 писал(а):

Так, насколько я помню, поиск цепочки длиннее 11 для $k=84$ интенсивно проводился (скорее всего Евгением), но искать подтверждение этому в двух с лишним сотнях страниц темы = убить еще полдня.

Сомневаюсь: папка M84n11_x32SSE у меня есть, а вот других папок с 84 в имени нет.
Я пытался посмотреть на M84n13, но даже список паттернов не получил, только очень предварительные прикидки. И было это месяцем ранее M84n11. Так что думаю длиннее 11 никто всерьёз не искал. А нашли лишь длиной 10.

Вот и первая поправка. Спасибо!
У меня во всех местах тоже 10 записано. Кроме головы. Там почему-то 11
Поправил. Обновлю таблицу, когда утрясется. Там наверняка еще ляпы есть.

[EUgeneUS]

VAL в сообщении #1699626 писал(а):

Есть и другие вопросы. Так, насколько я помню, поиск цепочки длиннее 11 для $k=84$ интенсивно проводился (скорее всего Евгением), но искать подтверждение этому в дву с лишним сотнях страниц темы = убить еще полдня.

Может быть и искали 11. Уже не помню.
Но всё, что находили до $k \le 100$, публиковали в файлике Хуго в 292580. А там только 10.
А раз 11 не нашли, то и более длинные цепочки не искали (я точно не искал больше 11 для $k=84$).

[VAL]

EUgeneUS в сообщении #1699639 писал(а):

VAL в сообщении #1699626 писал(а):

Есть и другие вопросы. Так, насколько я помню, поиск цепочки длиннее 11 для $k=84$ интенсивно проводился (скорее всего Евгением), но искать подтверждение этому в дву с лишним сотнях страниц темы = убить еще полдня.

Может быть и искали 11. Уже не помню.
Но всё, что находили до $k \le 100$, публиковали в файлике Хуго в 292580. А там только 10.
А раз 11 не нашли, то и более длинные цепочки не искали (я точно не искал больше 11 для $k=84$).

Спасибо! Уже разобрались.
У меня в голове смещение произошло, что нашли цепочку длиной 11 (тогда было бы естественно искать 12). Хотя во всех таблицах и сводках у меня записано 10. 11 я набрал по памяти (в смысле "по склерозу").

[Dmitriy40]

VAL
Понравилось разделение:
"Была попытка"
"Была упорная попытка"

[VAL]

Dmitriy40 в сообщении #1699644 писал(а):

VAL
Понравилось разделение:
"Была попытка"
"Была упорная попытка"

Так я решил высветить попытку доказать, что $M(192) \ge 15$.
К концу 22-го года мы все отошли от проекта, а комп у меня на кафедре продолжал еще два года денно и нощно искать эту пятнашку.
Причем эмпирическая оценка вероятности, которая в предыдущих случаях более или менее работала, обещала где-то месяц.
За эти два года я нашел пару сотен пятнашек с одним проколом (в разных местах), но целой так и не нашел...
Так что, грех было не выделить этот случай.

[VAL]

$M(1512) \ge 8$

(Оффтоп)

 3252567369094587050882647094060555157179720540521077652724495065085765720586647141441453684061011934270056987581753254198061128846671870

Этот результат следствие составления вчерашней таблицы. При систематизации еще не рассмотренных $k$ стало ясно, что этот случай будет легким. В отличие от тех, с которыми бился на тот момент мой комп. Так и вышло.

А вот выглядевший еще более легким случай $k=960$ пока сопротивляется. Впрочем, полагаю, это не затянется.