Лучший алгоритм факторизации чисел

[Skipper]

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

Странно, слишком медленный у Вас комп, у меня справился за 10с на ECM и 43с на SIQS.

Ну тогда у вас ECM не справился за 10с.
SIQS справился за 43 секунды.

Насчёт yafu - 3-й версии просто отсуствует, ничего не скачивается.
2-й версии- скачивается, запускается и тут же exe вылетает.

Но я скачал yafu-1.34 (x64) - этот ECM он долго не гонял, а быстро переключился на SIQS,
и разложил вышеупомянутое 70-значное число
6944789012800024057080093442480380292657619004509430413362525412029247
за (в логе написано) 156 секунд, то есть 2,5 минуты.

У вас было в браузере другим алгоритмом за 43с на SIQS, но мой скачанный
yafu-1.34 (x64) , 1-поточный , об этом в лог-файле написано, потому медленнее.

Попробовал, то 78-значное полупростое с двумя 39-значными делителями, которое этот
в браузере https://www.alpertron.com.ar/ECM.HTM раскладывал у меня 1 час с ECM впустую
(не разложил), и затем 1 час SIQS - разложил.
yafu-1.34 (x64) - у меня раскладывает за 491 секунду , что равно примерно 8 минут.

Выходит, действительно у меня дело в браузере, или этот алгоритм-
https://www.alpertron.com.ar/ECM.HTM
какая-то полная ерунда по сравнению с yafu-1.34.
У него многопоточность, и раскладывает 1 час, а yafu-1.34 - 1-поточный, разложил за 8 минут.

Почти на порядок быстрее!

Так что не могу согласиться, что,

Цитата:

Хороший вот этот: https://www.alpertron.com.ar/ECM.HTM - ввести число

у меня он не хороший.

PS Интересно, можно ли этот yafu-1.34 заставить гонять ECM до конца, не переключаясь на SIQS ?
Тогда мы могли бы сравнить реально во сколько раз ECM дольше если делители
порядка корня квадратного..

-- Пт дек 05, 2025 18:20:40 --

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

Или Вы не видите ссылок под словами "более новую версию YAFU"

Вижу. Открывается страница, на ней нахожу что нужно для моего процессора AMD-
"If you have another AMD CPU newer than 2015, use AVX2."
Кликаю по ссылке, и наблюдаю такую надпись- "Not found. Please browse from the top."
Ну и где тогда эту 3-ю версию найти чтобы и многопоточность была, и чтобы ECM можно было гонять до конца не переключаясь на SIQS ?

[Dmitriy40]

Skipper в сообщении #1711773 писал(а):

У него многопоточность,

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

Skipper в сообщении #1711773 писал(а):

Вижу. Открывается страница, на ней нахожу что нужно для моего процессора AMD-
"If you have another AMD CPU newer than 2015, use AVX2."
Кликаю по ссылке, и наблюдаю такую надпись- "Not found. Please browse from the top."

Кликать надо не по AVX2 в этой фразе, а по папке вверху с названием avx2 в прямоугольнике с надписью "Showing directory: /YAFU/v3.00/", это ссылка https://download.mersenne.ca/YAFU/v3.00/avx2, там будет выбор из 4 файлов, нужен yafu-x64.exe, ссылка https://download.mersenne.ca/YAFU/v3.00 ... fu-x64.exe.
Прям как будто первый раз видите файлопомойку каталог файлов.

Skipper в сообщении #1711773 писал(а):

PS Интересно, можно ли этот yafu-1.34 заставить гонять ECM до конца, не переключаясь на SIQS ?

Skipper в сообщении #1711773 писал(а):

и чтобы ECM можно было гонять до конца не переключаясь на SIQS ?

Указать ключи -plan custom -pretest_ratio 0.5 - это значит гонять ECM до квадратного корня (степень 1/2).

[Skipper]

Интересна зависимость времени от длины для SIQS.
70-значное в 10-тичной, это 233 бита, потребовалось 2,5 минуты,
78-значное в 10-тичной, это 256 бит (почти 257, так как уже близко к 2^256) , потребовалось 8 минут.
Последнее больше примерно в 16 млн раз, это значит при увеличении раскладываемого на 24 бита,
время растёт в 3 раза.
Сложность $O (exp ( (\log N) ^ {1/2} \cdot (\log \log N)^{1/2}) )$
если представить с логарифмом по основанию 2, и возведению в степень 2-ки, то изменится константа
определяемая $O$ большим, и если $M$ - длина числа $N$ в двоичной записи,
то сложность можно переписать как
$O ( 2 ^ { (M) ^ {1/2} \cdot ( \log M)^{1/2} }) $
при $ M = 233$ (в битах), и времени в минутах $T = 2.5$ , получим константу $C$ вместо $O$ ,
$C \cdot (2^ { (233 \cdot log 233)^{1/2} } ) =~ C \cdot (2^ { (233 \cdot 8)^{1/2} }) = 2.5 $ ,
значит $C =~ 2,5191325 \cdot 10 ^ {-13} $ , подставив сюда длину $257 $ получим,
$T = 2,5191325 \cdot 10 ^ {-13} \cdot (2^ { (257 \cdot 8 )^{1/2} }) $
= примерно $11$ (в минутах). Значит, время даже более чем в 4 раза должно вырасти,
выросло только примерно в 3 раза.
Так, можно по аналогии высчитать, для любых длин, т.е. сколько времени понадобилось бы для 1024-битного числа, 1536-битного, 2048-битного..

Цитата:

Нет у Альпетрона многопоточности, он в один поток работает.

Ну всё равно, на порядок медленнее у меня получилось, чем тот же однопоточный (выше писал), yafu-1.34 (x64) . Да и вы выше писали, что даже у вас на Альпетроне медленнее в разы.
У меня медленнее аж на порядок, видимо потому что ещё и с браузером что-то не то.
Короче, разочаровался я в Альпетроне, даже очень сильно..

Цитата:

Указать ключи -plan custom -pretest_ratio 1/2 - это значит гонять ECM до квадратного корня (степень 1/2).

Спасибо, сейчас буду пробовать..

-- Пт дек 05, 2025 19:45:16 --

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

"Showing directory: /YAFU/v3.00/", это ссылка https://download.mersenne.ca/YAFU/v3.00/avx2 , там будет выбор из 4 файлов, нужен yafu-x64.exe, ссылка https://download.mersenne.ca/YAFU/v3.00 ... fu-x64.exe .

Скачал, exe запускается и сразу вылетает. Видимо, не годится старый ini-файл, нужен именно под версию 3.0.

[Dmitriy40]

В ключе лучше указывать не 1/2, а 0.5 - что-то у меня с дробью криво работает.

Три запуска для одного и того же полупростого числа 70 знаков: делитель 35 знаков нашёлся на 15, 45, 786 из 824 кривых с B1=1M (это 35-digit). Время при этом в 4 потока было 79с, 97с, 478с.
Запуск сразу QS, без ECM (ключ -noecm), разлагает за 6.6с.
Вот такой он, ECM для полупростых.

-- 05.12.2025, 20:54 --

Skipper в сообщении #1711777 писал(а):

Видимо, не годится старый ini-файл, нужен именно под версию 3.0.

У меня работает без ini.
Положите exe в новую папку и там запускайте.

-- 05.12.2025, 20:59 --

Skipper в сообщении #1711777 писал(а):

Скачал, exe запускается и сразу вылетает.

Неудивительно: Phenom II 945 2009 года и не поддерживает AVX2, только SSE4. Берите версию под SSE41 - https://download.mersenne.ca/YAFU/v3.00 ... fu-x64.exe

-- 05.12.2025, 21:14 --

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

Три запуска для одного и того же полупростого числа 70 знаков: делитель 35 знаков нашёлся на 15, 45, 786 из 824 кривых с B1=1M (это 35-digit). Время при этом в 4 потока было 79с, 97с, 478с.
Запуск сразу QS, без ECM (ключ -noecm), разлагает за 6.6с.
Вот такой он, ECM для полупростых.

Вот я и говорил, что ECM медленнее QS. И хорош лишь для делителей заметно меньше квадратного корня, а лучше и кубического, тогда да, ECM их найдёт быстрее, потому что ECM зависит от величины меньшего делителя, а QS и GNFS от самого числа, соответственно чем меньше делитель, тем выгоднее ECM. Ну его так и применяют, для быстрого поиска небольших делителей (даже меньше кубического корня), вдруг они есть.

[Skipper]

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

Неудивительно: Phenom II 945 2009 года и не поддерживает AVX2, только SSE4. Берите версию под SSE41 - https://download.mersenne.ca/YAFU/v3.00 ... fu-x64.exe

Что то (надеюсь, временно) сайт перестал вообще открываться.

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

Вот я и говорил, что ECM медленнее QS. И хорош лишь для делителей заметно меньше квадратного корня, а лучше и кубического, тогда да, ECM их найдёт быстрее, потому что ECM зависит от величины меньшего делителя, а QS и GNFS от самого числа, соответственно чем меньше делитель, тем выгоднее ECM. Ну его так и применяют, для быстрого поиска небольших делителей (даже меньше кубического корня), вдруг они есть.

Вот я и хочу проверить, на конкретном примере. То, что медленнее если делители порядка корня квадратного, это понятно. Хочу поэкспериментировать, что если порядка корня кубического.
Скажем, 200-битное полупростое, такое что один делитель 66-битный, второй, 134-битный.

Даже интересно, что тут будет быстрее, ECM или SIQS..

[Dmitriy40]

20-значный делитель слишком мал, вот например число
980100000000000000702899999999999999992772999999999999994817 = 99000000000000000071 * 9899999999999999999999999999999999999927
ECM раскладывает в один поток за 1с-3с (чаще всего, в 70% случаев), или за 5с, или за 9с, или за 16с. Меньше 2с где-то в 30% случаев (навскидку).
QS раскладывает стабильно за 2.3с.

[Skipper]

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

Ну его так и применяют, для быстрого поиска небольших делителей (даже меньше кубического корня)

Вот "меньше кубического" я для себя только что на примере выяснил, что не надо думать, что
ECM хуже.
Конкретный пример, работала 1-поточная программа yafu-x64 версии 1.34.exe (многопоточная 3 версии
не загружается- сайт просто перестал работать. так что сравнивать с вашими 3 секундами тут не надо,
у меня 1 поток, у вас 8 потоков, если 4 физическиз ядра, и 8 логических)..

factor(1072656156935368954161128157526180397144973598635246980290921)
(61 цифра длина, делители 30-значный, и 31-значный, оба сильно простые, т.к. большие множители есть у (p+-1) и (q+-1),
время ECM-> 458.4336 seconds, и SIQS-> 11.5037 seconds )
,
factor(1403854865227606713189286434576929844650766524361718260983623)
(61 цифра длина, делители 20-значный, и 41-значный, оба сильно простые, т.к. большие множители есть у (p+-1) и (q+-1),
время ECM-> 6.9119 seconds, и SIQS-> 17.7347 seconds ),

Как видим, если минимальный делитель порядка корня квадратного, то ECM примерно в 40 раз
медленнее чем SIQS.
Если минимальный делитель порядка корня кубического, то ECM примерно в 2,5 раза
быстрее чем SIQS.

Так что уже с делителями порядка корней кубических, SIQS может с треском проиграть методу ECM, не говоря уже про ещё меньшие делители.

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

(в этом плане ECM охватывает как бы максимальное подмножество случаев, в отличии от алгоритмов: Ферма,
P-1 Полларда, P+1 Вильямса и других, которые оптимальны наоборот, для ничтожно малого количества случаев).

-- Пт дек 05, 2025 22:00:33 --

Можно ли улучшить SIQS ? Вот что там ищут- два числа, квадраты которых сравнимы по модулю.
А есть ли смысл искать например, два числа, кубы которых сравнимы по модулю?
Есть формулы сокращенного умножения, и для кубов, аналогично тому как для квадратов,
$a^2 - b^2 = (a+b)(a-b)$$$ ,

Ещё интересно, где найти, наиболее понятным языком описанное улучшение SIQS, для общего алгоритма QS ?

[Dmitriy40]

Skipper в сообщении #1711783 писал(а):

у вас 8 потоков, если 4 физическиз ядра, и 8 логических

У меня 4 ядра и 4 потока. И я везде стараюсь указывать сколько потоков работало, особенно если больше одного.

Skipper в сообщении #1711783 писал(а):

Если минимальный делитель порядка корня кубического, то ECM примерно в 2,5 раза
быстрее чем SIQS.

Не вижу. Я же показал что время работы ECM сильно плавает и однократный запуск мало о чём говорит.
На этом числе 1403854865227606713189286434576929844650766524361718260983623 в один поток:
QS стабильно 2.8с;
ECM 2.5384с, 2.4319с, 3.5342с, 3.9504с, 1.3300с, 1.3200с, 6.0320с, 6.4570с, 0.8250с, 0.8970с, 7.5237с, 6.1596с, 1.9482с, 2.5533с, 3.8264с, 1.5002с, 1.4991с, 3.2983с, 3.8164с, 7.8337с, 2.6880с, 1.4690с, 0.8660с, 2.5770с, 10/24=42% раз дольше QS, 6/24=25% раз более чем вдвое дольше QS, 5/24=21% раз более чем вдвое быстрее QS. Т.е. примерно равновероятно что вдвое медленнее, что вдвое быстрее, и почти в половине случаев просто медленнее. Не вижу тут никакого стабильного выигрыша в 2.5 раза, может и втрое медленнее быть.

Skipper в сообщении #1711783 писал(а):

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

А ещё намного более вероятно что будут несколько малых делителей, которые не сильно уменьшат исходное число и его таки придётся разлагать. Вероятность произвольному числу иметь делитель скажем 101 равна примерно 1/101, а делитель 12345678923 всего лишь 1/12345678923, на 5 порядков меньше.
А вот вероятность случайному числу не иметь делителей до скажем $10^9$ составляет всего лишь $\prod\limits_{p\in P}^{10^9}\frac{p-1}{p}\approx2.7\%$, т.е. с вероятностью выше 97% случайное число будет иметь делитель до миллиарда и значит придётся разлагать число всего на 1-9 знаков короче, которое вполне может оказаться полупростым и мало чем легче разложения исходного. Именно поэтому так выгоден ECM для произвольных чисел: в огромном большинстве случаев он быстро найдёт все небольшие делители и оставит для QS лишь с 2-3 делителями. Но это не значит что он легко разложит любое длинное число как Вам почему-то кажется! Вероятность "трудных" чисел среди всех случайных очень и очень мала, но зато на них ECM заткнётся, а QS/GNFS найдут делители за разумное (по сравнению с ECM) время.
Возьмите миллион разных (случайных) чисел большой длины и посмотрите как они разлагаются. Для чисел 40-50 знаков мы буквально недавно проделали аналогичную работу, здесь начало, здесь продолжение, здесь ещё продолжение и здесь про наименьший делитель.
Вы как что-то подумали - так возьмите и проверьте. Очень пользительно, знаете ли.

-- 05.12.2025, 23:33 --

Skipper в сообщении #1711783 писал(а):

А есть ли смысл искать например, два числа, кубы которых сравнимы по модулю?

А зачем? Разность кубов не равна произведению трёх сомножителей.