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

[Dmitriy40]

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

[VAL]

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

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

[Dmitriy40]

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

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

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

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