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

[VAL]

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

Возвращаясь к детерминированности ECM (гарантирует ли отсутствие делителя в заданном диапазоне). В одной из статей
(на неё и вики ссылается) обнаружил фразу (внизу стр.98) :

Цитата:

Возвращаемое значение FAIL в алгоритме означает, что метод эллиптических кривых является вероятностным, и попытка нахождения нетривиального делителя по вышеописанному алгоритму не всегда даёт положительный результат.

Получается информация в разных источниках разнится.

Допускаю, что не информация разнится, а реализация.
Т. е. классической считается быстрая реализация (кривые выбираются случайно), но с возможным пропуском делителя.
А в Alpertron'е реализован другой подход, когда используется полный список кривых, гарантирующих отделение делителей, не превышающих определенной границы.
В пользу этой версии говорит не только возможность запустить копию Alpertron'а с указанного номера кривой, но и еще один факт.
Всякий раз, когда оставшийся составной множитель был не очень огромен (скажем до 80 знаков), Alpertron успешно находил его и ни разу не попал в оставшиеся 37%.

[Dmitriy40]

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

Всякий раз, когда оставшийся составной множитель был не очень огромен (скажем до 80 знаков), Alpertron успешно находил его и ни разу не попал в оставшиеся 37%.

То что не увидели 37% - не показатель, ведь делитель находится не только по единственной кривой, но и по многим другим, в том числе с большими номерами (и якобы длиннее в цифрах). Например для числа

(Оффтоп)

2646227649753534131893 * 2488517596499804546265588868674190589073956666522507819 * 13240003859110038964973565829087951628854127345255459597241649781

альпетрон находит меньший делитель по кривым 106 (20-digits) и 163 и 406 и 414 (25-digits) и 431 и 473 и 498 и 533 (30-digits), а это означает что вероятность пропуска уже $e^{-3} \approx 5\%$.
Кроме того, Вы точно видели что делитель находился методом ECM, а не QS/NFS? Для чисел до 80 цифр оба этих метода работают быстро, до десятка минут (а ECM за полминуты).

Вот например для чисел

(Оффтоп)

99999999999999999999999859 * 999999999999999999999999999999999999999999999999999709
9999999999999999999999877 * 9999999999999999999999999999999999999999999999999999889
999999999999999999999743 * 99999999999999999999999999999999999999999999999999999407
99999999999999999999977 * 999999999999999999999999999999999999999999999999999999907
9999999999999999999973 * 9999999999999999999999999999999999999999999999999999999851
99999999999999999989 * 9999999999999999999999999999999999999983
9999999999999999961 * 99999999999999999999999999999999999999881
999999999999999989 * 999999999999999999999999999999999999999917
99999999999999997 * 9999999999999999999999999999999999999999919
9999999999999937 * 99999999999999999999999999999999999999999947
999999999999989 * 999999999999999999999999999999999999999999991

Alpetron методом ECM делитель не находит, запускает SIQS и за менее 10 минут разлагает. Хотя для всех чисел меньший делитель менее кубического корня из числа. А последнее число имеет делитель даже менее корня 4-й степени! И тоже не нашёлся!

Собственно это прямые контрпримеры к изначальному Вашему утверждению что Alpetron гарантированно находит делители до кубического корня (методом ECM, когда показывается XX-digit level). Не гарантированно. Можно ставить точку в обсуждении.

-- 14.09.2025, 11:03 --

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

которое уже почти неделю считается методом NFS, 3ГБ данных нагенерило, если правильно догадался, то надо ещё часов 10

Догадался неправильно, счёт не закончился. Значит понятия не имею сколько нужно времени.

[VAL]

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

Вот например для чисел(Оффтоп)
99999999999999999999999859 * 999999999999999999999999999999999999999999999999999709
9999999999999999999999877 * 9999999999999999999999999999999999999999999999999999889
999999999999999999999743 * 99999999999999999999999999999999999999999999999999999407
99999999999999999999977 * 999999999999999999999999999999999999999999999999999999907
9999999999999999999973 * 9999999999999999999999999999999999999999999999999999999851
99999999999999999989 * 9999999999999999999999999999999999999983
9999999999999999961 * 99999999999999999999999999999999999999881
999999999999999989 * 999999999999999999999999999999999999999917
99999999999999997 * 9999999999999999999999999999999999999999919
9999999999999937 * 99999999999999999999999999999999999999999947
999999999999989 * 999999999999999999999999999999999999999999991
Alpetron методом ECM делитель не находит, запускает SIQS и за менее 10 минут разлагает. Хотя для всех чисел меньший делитель менее кубического корня из числа. А последнее число имеет делитель даже менее корня 4-й степени! И тоже не нашёлся!

Собственно это прямые контрпримеры к изначальному Вашему утверждению что Alpetron гарантированно находит делители до кубического корня (методом ECM, когда показывается XX-digit level). Не гарантированно. Можно ставить точку в обсуждении.

Я бы поставил многоточие...
Запустил первый из Ваших примеров. После 200-й кривой Apertron переключился на SIQS и быстро разложил число.
В то же время, согласно приведенной в Help'е таблице, для разложения с помощью ECM ему бы потребовалось порядка 300-700 кривых.
Возможно, по каким-то признакам программа определила, что SIQS в данном случае сработает быстрее.
Вот если бы были использованы 700 кривых, тогда бы действительно можно было утверждать, что ECM прозевал множитель.

Заодно спрошу.

Цитата:

209662857453191172208774166556488590112931394712279012594955823904346331202445705641007789417542899809691474514127837942488639051212991896037675302171 (150 digits) (Composite)
55662212514374333854411247602870129064983737899272183727285204718917424705504387281480220130365957114197485014500556797138352686863076223979929623467 (149 digits) (Composite)

Разложение на два простых множителя хотя бы одного из вышеприведенных чисел дает цепочку из 8-и последовательных чисел с 1260-ю делителями.

3918379656357389606873359047195893747533485686015905036602677399573158885722032566725698392305436953685570352466693456774399905281974881795857 (142 digits) (Composite)
6478197682160135533232676025010796587683078229933245253455083741332424828397724440663355684763020130070666446674154783674124103294478717003233 (142 digits) (Composite)

А здесь разложение на два простых множителя каждого из вышеприведенных чисел дает цепочку из 8-и последовательных чисел с 1620-ю делителями.

Как я понял, первое из чисел - крепкий орешек.
А что с остальными? Вдруг они расколются легче? Или они тоже не поддались?

[Dmitriy40]

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

Как я понял, первое из чисел - крепкий орешек.
А что с остальными? Вдруг они расколются легче? Или они тоже не поддались?

Второе тоже не поддалось, оно сейчас ещё считается, про него и писал "которое уже почти неделю считается методом NFS, 3ГБ данных нагенерило, если правильно догадался, то надо ещё часов 10" (и не закончилось, продолжает).
Впрочем, остановлю, попробую последние два, по 142 цифры.

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

Вот если бы были использованы 700 кривых, тогда бы действительно можно было утверждать, что ECM прозевал множитель.

Так ведь изначально речь не про любой ECM, а конкретно про Alpetron. Вы же тогда сказали (выделение жирным моё)

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

При этом последний множитель является составным числом, не имеющим простых множителей, не превосходящих кубического корня из него. Это гарантирует требуемое значение $\tau(n+3)$

и это и прямо опровергается моими примерами (не про то число, а про Alpetron и его гарантию). В последнем моём числе делитель меньше корня 4-й степени, не кубического! И не находится (ECM, до переключения на SIQS). Уверен что можно подобрать аналогичный пример и с большим количеством цифр, просто дольше ждать.
Так что Alpetron не гарантирует отсутствия делителей при их ненахождении методом ECM. Без всяких "если бы".

-- 14.09.2025, 17:21 --

Другая программа (GMP-ECM) тоже не гарантирует нахождение делителя в последнем числе, даже при проверке до 20 цифр (не 15):

T:\YAFU\ECM>ecmfactor -t 40 999999999999988999999999999999999999999999991000000000000099 11e3
Performing 40 curve(s) with B1=11000
thread 0 with sigma -1:3709925874 found no factor
thread 1 with sigma -1:1149348676 found no factor
thread 2 with sigma -1:2283480440 found no factor
thread 3 with sigma -1:3801871564 found no factor
thread 4 with sigma -1:1043431779 found no factor
thread 5 with sigma -1:2875946446 found no factor
thread 6 with sigma -1:1012399597 found no factor
thread 7 with sigma -1:3222357868 found no factor
thread 8 with sigma -1:1053157322 found no factor
thread 9 with sigma -1:1553983165 found no factor
thread 10 with sigma -1:1052267362 found no factor
thread 11 with sigma -1:2147686811 found no factor
thread 12 with sigma -1:2744976363 found no factor
thread 13 with sigma -1:1603799396 found no factor
thread 14 with sigma -1:2464630276 found no factor
thread 15 with sigma -1:2779405998 found no factor
thread 16 with sigma -1:3788053202 found no factor
thread 17 with sigma -1:3465311451 found no factor
thread 18 with sigma -1:1330498622 found no factor
thread 19 with sigma -1:131402339 found no factor
thread 20 with sigma -1:1365426662 found no factor
thread 21 with sigma -1:2816573136 found factor in step 2: 999999999999989
thread 22 with sigma -1:2380529664 found no factor
thread 23 with sigma -1:714565104 found no factor
thread 24 with sigma -1:926441210 found no factor
thread 25 with sigma -1:328586039 found no factor
thread 26 with sigma -1:2738096960 found no factor
thread 27 with sigma -1:1476846401 found no factor
thread 28 with sigma -1:1198181637 found no factor
thread 29 with sigma -1:3103343956 found no factor
thread 30 with sigma -1:2234865279 found no factor
thread 31 with sigma -1:1316211101 found no factor
thread 32 with sigma -1:2381609567 found factor in step 2: 999999999999989
thread 33 with sigma -1:2459676260 found no factor
thread 34 with sigma -1:3097535624 found no factor
thread 35 with sigma -1:2394743452 found no factor
thread 36 with sigma -1:665471186 found no factor
thread 37 with sigma -1:3813813317 found no factor
thread 38 with sigma -1:441236676 found no factor
thread 39 with sigma -1:1980266805 found no factor

Видите, нашлось лишь в двух случаях из 40.
Проверка до 25 цифр:

(Оффтоп)

T:\YAFU\ECM>ecmfactor -t 40 999999999999988999999999999999999999999999991000000000000099 5e4
Performing 40 curve(s) with B1=50000
thread 0 with sigma -1:45226200 found factor in step 2: 999999999999989
thread 1 with sigma -1:356220467 found no factor
thread 2 with sigma -1:1088341862 found factor in step 2: 999999999999989
thread 3 with sigma -1:3752302639 found no factor
thread 4 with sigma -1:1228659744 found no factor
thread 5 with sigma -1:4208807869 found no factor
thread 6 with sigma -1:2064144193 found no factor
thread 7 with sigma -1:4095636252 found no factor
thread 8 with sigma -1:4149101461 found no factor
thread 9 with sigma -1:2772543116 found no factor
thread 10 with sigma -1:3934677763 found no factor
thread 11 with sigma -1:2313027909 found no factor
thread 12 with sigma -1:2897011649 found no factor
thread 13 with sigma -1:2565053966 found no factor
thread 14 with sigma -1:1995279994 found factor in step 2: 999999999999989
thread 15 with sigma -1:3048264893 found factor in step 2: 999999999999989
thread 16 with sigma -1:556047040 found no factor
thread 17 with sigma -1:4240240323 found factor in step 1: 999999999999989
thread 18 with sigma -1:237587558 found no factor
thread 19 with sigma -1:2240733329 found factor in step 2: 999999999999989
thread 20 with sigma -1:18499938 found no factor
thread 21 with sigma -1:3814488282 found no factor
thread 22 with sigma -1:1039024294 found factor in step 2: 999999999999989
thread 23 with sigma -1:197715498 found no factor
thread 24 with sigma -1:906656462 found no factor
thread 25 with sigma -1:3696363369 found no factor
thread 26 with sigma -1:2625443896 found no factor
thread 27 with sigma -1:1992581051 found no factor
thread 28 with sigma -1:2040812700 found no factor
thread 29 with sigma -1:1754807617 found no factor
thread 30 with sigma -1:1454287625 found no factor
thread 31 with sigma -1:1943087696 found no factor
thread 32 with sigma -1:1466845235 found no factor
thread 33 with sigma -1:3998598749 found no factor
thread 34 with sigma -1:3108291996 found no factor
thread 35 with sigma -1:260682210 found no factor
thread 36 with sigma -1:2644690635 found no factor
thread 37 with sigma -1:4281873649 found no factor
thread 38 with sigma -1:2989399662 found no factor
thread 39 with sigma -1:3981441712 found no factor

Находится вероятнее, но всё равно не 100%.

Проверка до 30 цифр:

(Оффтоп)

T:\YAFU\ECM>ecmfactor -t 40 999999999999988999999999999999999999999999991000000000000099 25e4
Performing 40 curve(s) with B1=250000
thread 0 with sigma -1:2099103219 found no factor
thread 1 with sigma -1:1827979104 found no factor
thread 2 with sigma -1:1869095382 found no factor
thread 3 with sigma -1:98371620 found no factor
thread 4 with sigma -1:1512656756 found factor in step 2: 999999999999989
thread 5 with sigma -1:1680434580 found no factor
thread 6 with sigma -1:3072850861 found factor in step 1: 999999999999989
thread 7 with sigma -1:4085030193 found factor in step 2: 999999999999989
thread 8 with sigma -1:827621207 found no factor
thread 9 with sigma -1:213708498 found factor in step 2: 999999999999989
thread 10 with sigma -1:1348326026 found no factor
thread 11 with sigma -1:789273937 found no factor
thread 12 with sigma -1:2829566451 found no factor
thread 13 with sigma -1:3221117680 found factor in step 2: 999999999999989
thread 14 with sigma -1:3095415340 found no factor
thread 15 with sigma -1:2766223358 found factor in step 2: 999999999999989
thread 16 with sigma -1:1283509870 found no factor
thread 17 with sigma -1:137686964 found factor in step 2: 999999999999989
thread 18 with sigma -1:1634191684 found no factor
thread 19 with sigma -1:3908576377 found no factor
thread 20 with sigma -1:381492327 found no factor
thread 21 with sigma -1:3202207507 found no factor
thread 22 with sigma -1:1924781681 found no factor
thread 23 with sigma -1:1599682681 found factor in step 2: 999999999999989
thread 24 with sigma -1:1967122925 found no factor
thread 25 with sigma -1:928973910 found no factor
thread 26 with sigma -1:4269381302 found factor in step 2: 999999999999989
thread 27 with sigma -1:1656084528 found no factor
thread 28 with sigma -1:3385447937 found no factor
thread 29 with sigma -1:4017426232 found factor in step 2: 999999999999989
thread 30 with sigma -1:7291593 found no factor
thread 31 with sigma -1:4294405236 found no factor
thread 32 with sigma -1:1532480121 found no factor
thread 33 with sigma -1:3829265154 found factor in step 2: 999999999999989
thread 34 with sigma -1:2013168483 found no factor
thread 35 with sigma -1:2241357105 found factor in step 2: 999999999999989
thread 36 with sigma -1:769220184 found no factor
thread 37 with sigma -1:971912917 found factor in step 2: 999999999999989
thread 38 with sigma -1:421816516 found no factor
thread 39 with sigma -1:122925823 found factor in step 2: 999999999999989

Проверка до 35 цифр:

(Оффтоп)

T:\YAFU\ECM>ecmfactor -t 40 999999999999988999999999999999999999999999991000000000000099 1e6
Performing 40 curve(s) with B1=1000000
thread 0 with sigma -1:2363281025 found factor in step 2: 999999999999989
thread 1 with sigma -1:902025767 found no factor
thread 2 with sigma -1:3195490596 found factor in step 2: 999999999999989
thread 3 with sigma -1:59142094 found factor in step 1: 999999999999989
thread 4 with sigma -1:1071031781 found no factor
thread 5 with sigma -1:2393965293 found no factor
thread 6 with sigma -1:3260213677 found no factor
thread 7 with sigma -1:1861444253 found no factor
thread 8 with sigma -1:2988377287 found factor in step 1: 999999999999989
thread 9 with sigma -1:1416649064 found factor in step 2: 999999999999989
thread 10 with sigma -1:1893389558 found no factor
thread 11 with sigma -1:1064507858 found no factor
thread 12 with sigma -1:2649652341 found factor in step 2: 999999999999989
thread 13 with sigma -1:2317269588 found factor in step 1: 999999999999989
thread 14 with sigma -1:3770040356 found factor in step 1: 999999999999989
thread 15 with sigma -1:2546874103 found no factor
thread 16 with sigma -1:2846916613 found factor in step 2: 999999999999989
thread 17 with sigma -1:2194750193 found no factor
thread 18 with sigma -1:2093093176 found factor in step 2: 999999999999989
thread 19 with sigma -1:1463248662 found no factor
thread 20 with sigma -1:2397180179 found factor in step 2: 999999999999989
thread 21 with sigma -1:928309271 found no factor
thread 22 with sigma -1:1185016063 found factor in step 2: 999999999999989
thread 23 with sigma -1:470862734 found no factor
thread 24 with sigma -1:2171932164 found no factor
thread 25 with sigma -1:3417816361 found no factor
thread 26 with sigma -1:4125797819 found factor in step 2: 999999999999989
thread 27 with sigma -1:3474809589 found factor in step 1: 999999999999989
thread 28 with sigma -1:1168282428 found factor in step 2: 999999999999989
thread 29 with sigma -1:2575730641 found no factor
thread 30 with sigma -1:1404869690 found factor in step 2: 999999999999989
thread 31 with sigma -1:323857962 found no factor
thread 32 with sigma -1:2828241554 found no factor
thread 33 with sigma -1:3325565492 found no factor
thread 34 with sigma -1:1720047221 found factor in step 2: 999999999999989
thread 35 with sigma -1:692244756 found no factor
thread 36 with sigma -1:3112326288 found no factor
thread 37 with sigma -1:60392764 found factor in step 1: 999999999999989
thread 38 with sigma -1:2040962361 found factor in step 1: 999999999999989
thread 39 with sigma -1:1533469802 found factor in step 2: 999999999999989

Даже проверкой до 35 цифр делитель из 15 цифр может не найтись! Смотря как будут выбраны случайные параметры кривой и начальной точки. А каковы они у Alpetron неизвестно. Это и есть "нахождение не гарантируется".

[VAL]

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

AL в сообщении #1701791

писал(а):
Как я понял, первое из чисел - крепкий орешек.
А что с остальными? Вдруг они расколются легче? Или они тоже не поддались? Второе тоже не поддалось, оно сейчас ещё считается, про него и писал "которое уже почти неделю считается методом NFS, 3ГБ данных нагенерило, если правильно догадался, то надо ещё часов 10" (и не закончилось, продолжает).
Впрочем, остановлю, попробую последние два, по 142 цифры.

Понятно!

А вот с аргументами по ECM на Alpertron'е не понятно.
Не понятно, как Ваши аргументы опровергают мои гипотезы.

[Dmitriy40]

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

Не понятно, как Ваши аргументы опровергают мои гипотезы.

Ещё раз: Вы сказали что Alpetron гарантирует нахождение делителя до кубического корня (так как факт ненахождения делителя Вы использовали как уверенность в их отсутствии), я же привёл кучу примеров когда факт ненахождения Alpetron-ом делителя до кубического корня (и даже до корня 4-й степени!) не означает что таковых делителей нет. Т.е. Ваши слова (раз не нашёл, значит точно нет) были некорректны.
Кроме того, вовсе не факт что Alpetron проверяет точно до кубического корня, обычно я вижу что порог переключения с ECM на SIQS/NFS несколько ниже. Но учитывая последний пример с корнем 4-й степени это уже неважно.
Плюс я привёл доводы что ECM в принципе не является детерминированным методом в том смысле что не гарантирует нахождение делителей, по крайней мере если ограничено количество проверяемых кривых (если до упора - очевидно найдёт делители, но неизвестно сколько потребуется времени). Да, реализация Alpetron-ом метода ECM детерминирована в том смысле что от запуска к запуску выдаёт одинаковый результат (не используется случайностей), но это не означает что он непременно найдёт делители - как видно из моих примеров, нет, не находит.

[VAL]

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

Ещё раз: Вы сказали что Alpetron гарантирует нахождение делителя до кубического корня (так как факт ненахождения делителя Вы использовали
как уверенность в их отсутствии), я же привёл кучу примеров когда факт ненахождения Alpetron-ом делителя до кубического корня (и даже до корня 4-й степени!) не означает что таковых делителей нет. Т.е. Ваши слова (раз не нашёл, значит точно нет) были некорректны.

Дмитрий, просто перечитайте, пожалуйста, внимательнее мои аргументы.

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

Запустил первый из Ваших примеров. После 200-й кривой Alpertron переключился на SIQS и быстро разложил число.
В то же время, согласно приведенной в Help'е таблице, для разложения с помощью ECM ему бы потребовалось порядка 300-700 кривых.
Возможно, по каким-то признакам программа определила, что SIQS в данном случае сработает быстрее.
Вот если бы были использованы 700 кривых, тогда бы действительно можно было утверждать, что ECM прозевал множитель.

Я, разумеется, не гарантирую, что Alpertron действует именно так (не вникал в его кухню). Но по внешним признакам он работает именно так:
уходит на SICS, если в процессе выполнения ECM находит какой-то модуль, который гарантирует нахождение разложения за приемлемое время.

А в случае с цепочкой для 648, он не ушел на SICS, а честно перебрал все кривые, которые он использует для нахождения делителей, не превышающих 40 (или 45, уже не помню) знаков.

[Dmitriy40]

VAL
Ну то есть Вы предлагаете мне поискать контрпример длиной 121 цифр с наименьшим делителем в 40 цифр и каждый раз ждать неделю пока он переберёт все 45 цифр делителей и не найдёт делителя, так что ли? Только такой контрпример Вас убедит что ECM не гарантирует нахождения делителя при ограничении количества кривых?
А этот пример

(Оффтоп)

9999910372955553645852281 * 9999999809574298023011445664133124093724900786643634139948527259922489

Вас конечно не убедит? Только смотрите внимательнее, через 1м40с он переходит к перебору кривых для 30-digit level, т.е. 25-значного делителя не нашёл при полном переборе соответствующих кривых! Да, за 4м он его таки найдёт, на 508 кривой, но это уже 30-digit кривые, не 25!
Почему это Вас не убеждает?
Или мне непременно надо подобрать число чтобы он закончил перебор и следующего уровня и всё равно не нашёл делитель? Уверен таких много, просто долго их проверять, ведь вероятность порядка $e^{-2} \approx 13.5\%$.

[DemISdx]

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

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

Возможно мной что-то пропущено. И уже ранее был клич от VAL "на посчитать".
Присоединяюсь с аналогичным предложением (если конечно еще есть в этом необходимость).
Ресурсы не ахти какие, но попробовать можно.

[Dmitriy40]

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

Или мне непременно надо подобрать число чтобы он закончил перебор и следующего уровня и всё равно не нашёл делитель? Уверен таких много, просто долго их проверять, ведь вероятность порядка $e^{-2} \approx 13.5\%$.

Похоже я недооценил вероятность, она сильно меньше, наверное $e^{-\left(\frac{300}{90}+1\right)} \approx 1.3\%$ (для 20-значного делителя с перебором и всей 25-digit группы кривых). Из 200 проверенных примеров длиной 94 цифры с делителем 20 цифр все разложились, где-то четверть (или треть, не уследил) потребовали запуска 25-digit level.

[VAL]

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

Ну то есть Вы предлагаете мне поискать контрпример длиной 121 цифр
с наименьшим делителем в 40 цифр и каждый раз ждать неделю пока он переберёт все 45 цифр делителей
и не найдёт делителя, так что ли?

Я не требую от Вас поиска контрпримеров.
Если Вы заметили, под воздействием Ваших аргументов я больше не обосновывал наличие требуемого разложения тем, что Alpertron ничего не нашел, перебрав сколько-то кривых. А вместо этого прислал число, нужное для восьмерки чисел по 6480 делителей, Вам. Хотя проверку на Alpertron'е оно прошло.

Другой вопрос, что Ваши аргументы не опровергают моей версии. Как и мои не доказывают.

-- 16 сен 2025, 19:26 --

DemISdx в сообщении #1702046 писал(а):

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

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

Возможно мной что-то пропущено. И уже ранее был клич от VAL "на посчитать".
Присоединяюсь с аналогичным предложением (если конечно еще есть в этом необходимость).
Ресурсы не ахти какие, но попробовать можно.

Новых чисел для разложения пока нет. Но "могучая кучка" старых жива:

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

209662857453191172208774166556488590112931394712279012594955823904346331202445705641007789417542899809691474514127837942488639051212991896037675302171 (150 digits) (Composite)
55662212514374333854411247602870129064983737899272183727285204718917424705504387281480220130365957114197485014500556797138352686863076223979929623467 (149 digits) (Composite)

Разложение на два простых множителя хотя бы одного из вышеприведенных чисел дает цепочку из 8-и последовательных чисел с 1260-ю делителями.

3918379656357389606873359047195893747533485686015905036602677399573158885722032566725698392305436953685570352466693456774399905281974881795857 (142 digits) (Composite)
6478197682160135533232676025010796587683078229933245253455083741332424828397724440663355684763020130070666446674154783674124103294478717003233 (142 digits) (Composite)

А здесь разложение на два простых множителя каждого из вышеприведенных чисел дает цепочку из 8-и последовательных чисел с 1620-ю делителями.

А чем Вы планируете факторизовать?

[Dmitriy40]

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

Если Вы заметили, под воздействием Ваших аргументов я больше не обосновывал наличие требуемого разложения тем, что Alpertron ничего не нашел, перебрав сколько-то кривых.

ОК, я к этому и вёл. Остальное скорее догадки.

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

А чем Вы планируете факторизовать?

Для начала дам ему YAFU и объясню как запускать. Потоков у него под три десятка вместо моих 4, будет в разы быстрее.

Я кстати пару дней назад обнаружил (не могу сказать "нашёл" так как и не искал, но наткнулся) более новую версию YAFU, 3.00 вместо 1.34, у неё два существенных для меня плюса: 1) умеет ECM многопоточно, 2) показывает ETA (оставшееся время) для NFS.
Вам не предложил так как для NFS (а это более 95-100 цифр, меньше справляется SIQS) она всё равно требует внешних файлов типа gnfs-lasieve4I11e.exe, с чем у Вас тогда и не получилось. Впрочем ссылку указал, можете снова попробовать (файлы для NFS брать отсюда, не знаю какая версия запустится).

-- 16.09.2025, 22:07 --

А вот тут под убунтой обещают факторизацию 154-цифирного числа за пару часов в один поток ... Я проверить не могу.

[DemISdx]

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

Но "могучая кучка" старых жива

Тогда нужны какие-то пояснения, как это запускать.

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

А чем Вы планируете факторизовать?

Видимо на YAFU, если имеется ввиду программное обеспечение.

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

более новую версию YAFU
, 3.00

Такая версия для AVX2 у меня запускается без ошибок.
Но как проверить работу - не знаю.
Нужны инструкции.

[Dmitriy40]

ОК, напишу подробно здесь.

DemISdx
К самой YAFU надо в комплект ещё файлы gnfs-lasieve*.exe, брать отсюда https://download.mersenne.ca/GGNFS версию для ivybridge (более новых нету) gnfs-win64-ivybridge-asm64.zip, из архива нужны только файлы gnfs-lasieve4I11e.exe и gnfs-lasieve4I11e_argfix.exe (с любыми цифрами, 11-16, все 12шт), положить в папку к YAFU, остальные файлы не нужны.

Запускать командой
yafu-x64.exe "factor(999999999999989 * 999999999999999999999999999999999999999999991)" -threads 4 -p
где 4 сколько потоков выделить, -p работать с Idle (в фоне), все параметры не обязательны.
У меня такое число раскладывается за секунду, конец вывода:

...
***factors found***
P15 = 999999999999989
P45 = 999999999999999999999999999999999999999999991

***factorization:***
999999999999988999999999999999999999999999991000000000000099=999999999999989*999999999999999999999999999999999999999999991

ans = 1

Чтобы проверить работу SIQS метода нужно число с делителем побольше, например:
yafu-x64.exe "factor(99999597927516812804847414529880573 * 99999683550587277607185624599397449)" -threads 4 -p
За секунду отрабатывает ECM метод (номера кривых увеличиваются), потом запускается SIQS и у меня работает 10 секунд. В выводе явно видны два делителя.

Это всё не требовало файлов gnfs-lasieve*.exe, для проверки их подключения нужно число подлинее (чтобы не париться с ключами запуска), более 95 цифр, например:
yafu-x64.exe "factor(999997295611437149904888116876355641383731732523 * 999996832699836009738971023727097284971253907401)" -threads 4 -p
ECM отрабатывает за минуту и запускается NFS.
Если те 12 файлов (точнее два из них) не найдены или не смогли запуститься, то вывод ещё через полминуты будет

".\gnfs-lasieve4I12e.exe" не является внутренней или внешней
командой, исполняемой программой или пакетным файлом.

и вылетит.
Если же всё ОК, то пойдёт процесс, признаком работы будут строки типа
nfs: commencing algebraic side lattice sieving over range: 795000 - 800000
total yield: 4323, q=785003 (0.00098 sec/rel)
nfs: found 358951 relations, need at least 1936352 (filtering ETA: 0h 13m), continuing with sieving ...
У меня обещала работать 13 минут. Реально затратила 25 минут.

Теперь заменяете выражение в скобках на нужное число от VAL и запускаете счёт.
Те два числа 150 и 149 цифр у меня считались по неделе (4 потока) и не досчитались, данных выдали больше 3ГБ каждое.
Число 391837...95857 считается пару суток и собирается ещё сутки, может и досчитается, его пока не берите.
Длинные логи показывать как Вы любите не надо, достаточно разложения на множители (то что после "factors found" или "factorization").

При работе SIQS и NFS методов в текущей папке создаются рабочие файлы, для 150-значных чисел они будут несколько гигабайт.

Если не хотите тратить время на предпроверку методом ECM (она обычно лишняя, небольшие делители VAL проверяет и сам, а YAFU тратит несколько часов), то добавляете ключ -noecm. Я обычно не добавляю - вдруг повезёт и YAFU найдёт делитель методом ECM, такое иногда бывает (ECM тут инициализируется случайными значениями и потому от запуска к запуску может то находить делитель, то не находить). SIQS и NFS находят гарантированно, но работают сильно дольше.

Если оборвали счёт, то его можно продолжить, обязательно добавив ключ -R.
Help как обычно по ключу --help.

-- 16.09.2025, 23:43 --

VAL
Вы можете попытаться настроить у себя то же самое, только надо будет определить какие из https://download.mersenne.ca/GGNFS файлов нормально запускаются и работают (ждать разложения нет нужды, если по ошибке не вылетает, а пишет вон те строки про yield и ETA, значит работает). Проверять в порядке (вероятно уменьшения скорости): ivybridge, westmere, core2, p4. Чем svn413 версии лучше или хуже обычных я не смотрел.

[DemISdx]

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

напишу подробно здесь

Смотрим, что у меня получается на тестировании:

(Оффтоп)

Число ядер оставил пока как в Вашем примере.
Первый тест:

yafu-x64.exe "factor(999999999999989 * 999999999999999999999999999999999999999999991)" -threads 4 -p
warning: could not open yafu.ini, no options parsed


fac: factoring 999999999999988999999999999999999999999999991000000000000099
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
fac: no tune info: using qs/snfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C60
rho: x^2 + 2, starting 1000 iterations on C60
rho: x^2 + 1, starting 1000 iterations on C60
pm1: starting B1 = 150K, B2 = gmp-ecm default on C60
ecm: 30/30 curves on C60, B1=2k, B2=gmp-ecm default
ecm: 4/49 curves on C45, B1=11k, B2=gmp-ecm default

starting SIQS on c45: 999999999999999999999999999999999999999999991
Total factoring time = 0.2500 seconds


***factors found***
P15 = 999999999999989
P45 = 999999999999999999999999999999999999999999991

***factorization:***
999999999999988999999999999999999999999999991000000000000099=999999999999989*999999999999999999999999999999999999999999991

ans = 1

Второй тест:

yafu-x64.exe "factor(99999597927516812804847414529880573 * 99999683550587277607185624599397449)" -threads 4 -p
warning: could not open yafu.ini, no options parsed


fac: factoring 9999928147937644642379725977605228346537270939217998465938501730858277
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
fac: no tune info: using qs/snfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C70
rho: x^2 + 2, starting 1000 iterations on C70
rho: x^2 + 1, starting 1000 iterations on C70
pm1: starting B1 = 150K, B2 = gmp-ecm default on C70
ecm: 30/30 curves on C70, B1=2k, B2=gmp-ecm default
ecm: 74/74 curves on C70, B1=11k, B2=gmp-ecm default
ecm: 56/56 curves on C70, B1=50k, B2=gmp-ecm default, ETA: 0 sec

starting SIQS on c70: 9999928147937644642379725977605228346537270939217998465938501730858277

==== sieving in progress (  4 threads):   13104 relations needed ====
====             Press ctrl-c to abort and save state            ====
13362 rels found: 5901 full + 7461 from 81670 partial, (43790.14 rels/sec) ETA 0 sec)

SIQS elapsed time = 2.3904 seconds.
Total factoring time = 3.3147 seconds


***factors found***
P35 = 99999597927516812804847414529880573
P35 = 99999683550587277607185624599397449

***factorization:***
9999928147937644642379725977605228346537270939217998465938501730858277=99999597927516812804847414529880573*99999683550587277607185624599397449

ans = 1

Третий тест:

yafu-x64.exe "factor(999997295611437149904888116876355641383731732523 * 999996832699836009738971023727097284971253907401)" -threads 4 -p
warning: could not open yafu.ini, no options parsed


fac: factoring 999994128319838769982467633196885446178425983605747722551635504341166213013946711179719142102723
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
fac: no tune info: using qs/snfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C96
rho: x^2 + 2, starting 1000 iterations on C96
rho: x^2 + 1, starting 1000 iterations on C96
nfs: searching for brent special forms...
nfs: searching for homogeneous cunningham special forms...
nfs: searching for XYYXF special forms...
nfs: searching for direct special forms...
nfs: snfs form detection took 0.046869 seconds
nfs: couldn't find special form
pm1: starting B1 = 150K, B2 = gmp-ecm default on C96
ecm: 30/30 curves on C96, B1=2k, B2=gmp-ecm default
ecm: 74/74 curves on C96, B1=11k, B2=gmp-ecm default
ecm: 214/214 curves on C96, B1=50k, B2=gmp-ecm default, ETA: 0 sec
pm1: starting B1 = 3750K, B2 = gmp-ecm default on C96
ecm: 363/363 curves on C96, B1=250k, B2=gmp-ecm default, ETA: 0 sec
nfs: commencing nfs on c96: 999994128319838769982467633196885446178425983605747722551635504341166213013946711179719142102723
nfs: searching for brent special forms...
nfs: searching for homogeneous cunningham special forms...
nfs: searching for XYYXF special forms...
nfs: searching for direct special forms...
nfs: snfs form detection took 0.046874 seconds
nfs: couldn't find special form
nfs: thread 0 commencing polynomial search over range: 8942 - 9192
nfs: thread 3 commencing polynomial search over range: 8192 - 8442
nfs: thread 1 commencing polynomial search over range: 8692 - 8942
nfs: thread 2 commencing polynomial search over range: 8442 - 8692
No progressions found with the supplied parameters
No NFS polynomials found or read
No progressions found with the supplied parameters
No NFS polynomials found or read
coeff coeff 8400 specialq 1 - 391427 other 2835 - 6804
8820 specialq 1 - 398965 other 2817 - 6760
aprogs: 183 entries, 536 roots
aprogs: 184 entries, 530 roots
nfs: thread 2 commencing polynomial search over range: 9442 - 9692
nfs: thread 0 commencing polynomial search over range: 9192 - 9442
coeff 9660 specialq 1 - 412756 other 2785 - 6684
coeff 9240 specialq 1 - 405841 other 2801 - 6722
aprogs: 207 entries, 614 roots
aprogs: 165 entries, 442 roots
coeff: 9660, entries: 14020, sizeopt: 1024, rootopt: 50, saved: 0, best_e: 0.0000e+00, time: 1.61 sec

coeff: 9240, entries: 17240, sizeopt: 1024, rootopt: 84, saved: 0, best_e: 0.0000e+00, time: 2.39 sec

elapsed time: 3.6287 seconds (43 second deadline); poly select done
nfs: commencing algebraic side lattice sieving over range: 780000 - 785000
nfs: commencing algebraic side lattice sieving over range: 795000 - 800000
nfs: commencing algebraic side lattice sieving over range: 790000 - 795000
nfs: commencing algebraic side lattice sieving over range: 785000 - 790000
total yield: 71509, q=785003 (0.00046 sec/rel)
total yield: 72151, q=800011 (0.00047 sec/rel)
total yield: 73903, q=790003 (0.00046 sec/rel)
total yield: 84976, q=795001 (0.00046 sec/rel)
nfs: found 302539 relations, need at least 1936352 (filtering ETA: 0h 3m), continuing with sieving ...
nfs: commencing algebraic side lattice sieving over range: 815000 - 820000
nfs: commencing algebraic side lattice sieving over range: 810000 - 815000
nfs: commencing algebraic side lattice sieving over range: 805000 - 810000
nfs: commencing algebraic side lattice sieving over range: 800000 - 805000
total yield: 69005, q=810013 (0.00047 sec/rel)
total yield: 71992, q=805019 (0.00046 sec/rel)
total yield: 74056, q=820037 (0.00047 sec/rel)
total yield: 79139, q=815029 (0.00047 sec/rel)
nfs: found 596731 relations, need at least 1936352 (filtering ETA: 0h 2m), continuing with sieving ...
nfs: commencing algebraic side lattice sieving over range: 835000 - 840000
nfs: commencing algebraic side lattice sieving over range: 830000 - 835000
nfs: commencing algebraic side lattice sieving over range: 820000 - 825000
nfs: commencing algebraic side lattice sieving over range: 825000 - 830000
total yield: 68985, q=830003 (0.00047 sec/rel)
total yield: 69726, q=840023 (0.00047 sec/rel)
total yield: 71744, q=825001 (0.00047 sec/rel)
total yield: 72717, q=835001 (0.00047 sec/rel)
nfs: found 879903 relations, need at least 1936352 (filtering ETA: 0h 2m), continuing with sieving ...
nfs: commencing algebraic side lattice sieving over range: 855000 - 860000
nfs: commencing algebraic side lattice sieving over range: 845000 - 850000
nfs: commencing algebraic side lattice sieving over range: 840000 - 845000
nfs: commencing algebraic side lattice sieving over range: 850000 - 855000
total yield: 71576, q=855031 (0.00047 sec/rel)
total yield: 74455, q=860009 (0.00047 sec/rel)
total yield: 77498, q=845003 (0.00047 sec/rel)
total yield: 82407, q=850009 (0.00047 sec/rel)
nfs: found 1185839 relations, need at least 1936352 (filtering ETA: 0h 1m), continuing with sieving ...
nfs: commencing algebraic side lattice sieving over range: 875000 - 880000
nfs: commencing algebraic side lattice sieving over range: 865000 - 870000
nfs: commencing algebraic side lattice sieving over range: 860000 - 865000
nfs: commencing algebraic side lattice sieving over range: 870000 - 875000
total yield: 70393, q=875011 (0.00048 sec/rel)
total yield: 72374, q=865001 (0.00047 sec/rel)
total yield: 73698, q=880001 (0.00048 sec/rel)
total yield: 75503, q=870007 (0.00048 sec/rel)
nfs: found 1477807 relations, need at least 1936352 (filtering ETA: 0h 0m), continuing with sieving ...
nfs: commencing algebraic side lattice sieving over range: 895000 - 900000
nfs: commencing algebraic side lattice sieving over range: 885000 - 890000
nfs: commencing algebraic side lattice sieving over range: 890000 - 895000
nfs: commencing algebraic side lattice sieving over range: 880000 - 885000
total yield: 65419, q=895003 (0.00048 sec/rel)
total yield: 67557, q=900001 (0.00048 sec/rel)
total yield: 73962, q=885023 (0.00047 sec/rel)
total yield: 75666, q=890003 (0.00048 sec/rel)
nfs: found 1760411 relations, need at least 1936352 (filtering ETA: 0h 0m), continuing with sieving ...
nfs: commencing algebraic side lattice sieving over range: 915000 - 920000
nfs: commencing algebraic side lattice sieving over range: 900000 - 905000
nfs: commencing algebraic side lattice sieving over range: 905000 - 910000
nfs: commencing algebraic side lattice sieving over range: 910000 - 915000
total yield: 69358, q=915007 (0.00048 sec/rel)
total yield: 73471, q=905011 (0.00048 sec/rel)
total yield: 75582, q=920011 (0.00048 sec/rel)
total yield: 75945, q=910003 (0.00048 sec/rel)
nfs: commencing msieve filtering
999994128319838769982467633196885446178425983605747722551635504341166213013946711179719142102723
nfs: commencing algebraic side lattice sieving over range: 920000 - 925000
nfs: commencing algebraic side lattice sieving over range: 935000 - 940000
nfs: commencing algebraic side lattice sieving over range: 930000 - 935000
nfs: commencing algebraic side lattice sieving over range: 925000 - 930000
total yield: 67422, q=940001 (0.00048 sec/rel)
total yield: 67986, q=930011 (0.00048 sec/rel)
total yield: 74275, q=925019 (0.00048 sec/rel)
total yield: 84070, q=935003 (0.00048 sec/rel)
nfs: commencing msieve filtering
999994128319838769982467633196885446178425983605747722551635504341166213013946711179719142102723
nfs: commencing algebraic side lattice sieving over range: 940000 - 945000
nfs: commencing algebraic side lattice sieving over range: 955000 - 960000
nfs: commencing algebraic side lattice sieving over range: 945000 - 950000
nfs: commencing algebraic side lattice sieving over range: 950000 - 955000
total yield: 67543, q=955037 (0.00049 sec/rel)
total yield: 69224, q=960017 (0.00049 sec/rel)
total yield: 71407, q=950009 (0.00049 sec/rel)
total yield: 81798, q=945031 (0.00048 sec/rel)
nfs: commencing msieve filtering
999994128319838769982467633196885446178425983605747722551635504341166213013946711179719142102723
nfs: commencing algebraic side lattice sieving over range: 965000 - 970000
nfs: commencing algebraic side lattice sieving over range: 960000 - 965000
nfs: commencing algebraic side lattice sieving over range: 975000 - 980000
nfs: commencing algebraic side lattice sieving over range: 970000 - 975000
total yield: 69174, q=970027 (0.00049 sec/rel)
total yield: 70292, q=980027 (0.00049 sec/rel)
total yield: 74337, q=965023 (0.00049 sec/rel)
total yield: 80236, q=975011 (0.00049 sec/rel)
nfs: commencing msieve filtering
999994128319838769982467633196885446178425983605747722551635504341166213013946711179719142102723
checking relations array at location 1
checking relations array at location 1
nfs: commencing msieve linear algebra
linear algebra completed 156751 of 157070 dimensions (99.8%, ETA 0h 0m)
nfs: commencing msieve sqrt
NFS elapsed time = 543.8319 seconds.
Total factoring time = 565.7874 seconds


***factors found***
P48 = 999996832699836009738971023727097284971253907401
P48 = 999997295611437149904888116876355641383731732523

***factorization:***
999994128319838769982467633196885446178425983605747722551635504341166213013946711179719142102723=999996832699836009738971023727097284971253907401*999997295611437149904888116876355641383731732523

ans = 1

В третьем тесте смутило наличие "couldn't find special form", но возможно это нормальная реакция программы на поиск.
Не понял как запустить число от VAL, т.к. в Ваших примерах участвуют два числа.