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

[Dmitriy40]

Альпетрон его же раскладывает за 4с в один поток.
А YAFU за 1.4с методом QS в один поток и за 283с методом ECM в один поток (30 кривая из 904).

[mathpath]

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

Альпетрон его же раскладывает за 4с в один поток.
А YAFU за 1.4с методом QS в один поток и за 283с методом ECM в один поток (30 кривая из 904).

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

Например, cado-nfs написан на си (питон там ипользуется как оболочка), в нем реализован алгоритм gnfs
gnfs состоит из нескольких этапов - формирование полинома, просеивание, формирование матрицы, извлечение квадратных корней
Если посмотреть в каталог исходников cado-nfs, там есть подкаталог polyselect, который только формируют полином, в котором лежат си-шные исходники размером в один мегабайт, который писали несколько человек в течение нескольких лет, и разобраться в этом просто нереально

[Dmitriy40]

Ну понятно что не любая программа удобна для учебных целей.

[Skipper]

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

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

QS разложило за 6с в 4 потока: 6944789012800024057080093442480380292657619004509430413362525412029247 = 71342486346736476376473647659696813 * 97344364745674576437645675688654619
QS за 0.5с в 4 потока: 1072656156935368954161128157526180397144973598635246980290921 = 977333845837713000229703630939 * 1097533009322880130146442393739
QS за 0.9с в 4 потока: 1403854865227606713189286434576929844650766524361718260983623 = 21382390948200010361622532465807104946387 * 65654718811779303229

ECM разложил эти числа в 4 потока за 87с (тут откровенно повезло, делитель нашёлся при проверке до 30-digits уже на curve=29 из 904, без такого везения работал 737с, да и то, делитель нашёлся на 126 из 2350 кривых, тоже можно считать небольшим везением, так то расчётное время больше часа), 2.6с, 1.5с.

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


-- Вт дек 23, 2025 09:13:30 --

Цитата:

делитель нашёлся при проверке до 30-digits уже на curve=29 из 904,

И да, делитель может найтись при проверке 30-digits , притом что сам он, как в данном случае- 35-digits..

-- Вт дек 23, 2025 09:09:25 --

mathpath в сообщении #1713176 писал(а):

Например, cado-nfs написан на си (питон там ипользуется как оболочка), в нем реализован алгоритм gnfs
gnfs состоит из нескольких этапов - формирование полинома, просеивание, формирование матрицы, извлечение квадратных корней
Если посмотреть в каталог исходников cado-nfs, там есть подкаталог polyselect, который только формируют полином, в котором лежат си-шные исходники размером в один мегабайт, который писали несколько человек в течение нескольких лет, и разобраться в этом просто нереально

Выходит, за метод gnfs лучше и не браться, это несколько человеко-лет работы (может даже и порядка 10 лет), чтобы запрограммировать,
и то скорее всего будет намного медленнее, чем cado-nfs ? Я писал достаточно сложные алгоритмические программы.

[Dmitriy40]

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

Вот тут бы разобраться, как выбирать, по какому принципу в ECM эллиптические кривые, не просто рандомно,
а чтобы увеличивалась вероятность подобных "везений".

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

[Skipper]

Выяснили что ECM в случае наличия делителей, до порядка корня кубического сравним с SIQS, а в случае одинаковой длины двух делителей, может проигрывать SIQS в 400 раз по времени.
Но в каком то смысле, ECM всё же универсальный. Что такое в 400 раз?

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

пример, перемножим 100-битное просто число на 1400-битное простое, получим 1500-битное полупростое число.

Тут ECM разложит на множители, и только этот единственный метод сработает. Ни SIQS ни gnfs его вообще не разложат, и разница по времени будет не в 400 раз, а в миллионы-миллиарды.
Вот, число RSA-768 (232 десятичных знака) разложили в 2009 году,
RSA-896 имеет 896 бит (270 десятичных знаков) и пока что не факторизовано. Хотя за успешную факторизацию был предложен денежный приз в 75 000 долларов.

Это с 2009 года, прошло уже 16 лет, и никто до 2025 года, не может добиться прогресса в факторизации чисел от 232 десятичных знаков, до 270 !
Так что просто смешно читать, некоторые статьи, в которых пишут, типа таких: что якобы до 2070 года,
до RSA-2048 доберутся..
Прогнозы они такие прогнозы.. :)

Насчёт квантовых компьютеров, и алгоритма Шора. Я читал, не получается там так просто наращивать
количество кубитов: потому что их мощность потребления растёт с экспоненциальной зависимостью
от количества кубитов.

[Dmitriy40]

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

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

Нет не выяснили: это зависит и от величины чисел.

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

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

пример, перемножим 100-битное просто число на 1400-битное простое, получим 1500-битное полупростое число.

Тут ECM разложит на множители, и только этот единственный метод сработает. Ни SIQS ни gnfs его вообще не разложат, и разница по времени будет не в 400 раз, а в миллионы-миллиарды.

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

[DemISdx]

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

(Оффтоп)

Вообще есть даже сайт, где народ этим занимается совместно:
https://yafu.myfirewall.org/yafu/
Результаты вроде здесь:
https://yafu.myfirewall.org/yafu/downlo ... ences.html

[mathpath]

В этой ветке уже упоминался метод факторизации SIQS - Self-Initializing Quadratic Sieve.
Это уже довольно близко к GNFS, здесь практически те же самые базовые алгоритмы - полиномы, просеивание, поиск квадратов.
Одно из отличий в том, что здесь используются полиномы 2-й степени, а в gnfs - начиная с 5-й и выше.

Я сейчас смотрю питоновский код, который лежит вот тут:
https://github.com/skollmann/PyFactorise
Его автор Stephan Kollmann
Алгоритм начинается с формирования базы факторизации.
Берутся простые числа до определенной границы, но не все, а примерно половина, которая должна отвечать критерию Эйлера:
выражение
N^{(p-1)/2} \mod p
должно являться квадратичным вычетом.

Для каждого такого простого числа вычисляется дополнительно квадратный корень по модулю простого числа (для дальнейшего просеивания):
x² ≡ N mod p
Здесь оказывается, что все простые можно разделить на три категории:
p ≡ 3, 7( \mod 8)
p ≡ 5 (\mod 8)
p ≡ 1 (\mod 8)
В зависимости от используется либо малая теорема Ферма, либо алгоритм Аткина, либо алгоритм Тонелли-Шенкса

Вопрос: почему именно по модулю 8 ?

[Skipper]

mathpath в сообщении #1713243 писал(а):

В этой ветке уже упоминался метод факторизации SIQS - Self-Initializing Quadratic Sieve.
Это уже довольно близко к GNFS, здесь практически те же самые базовые алгоритмы - полиномы, просеивание, поиск квадратов.
Одно из отличий в том, что здесь используются полиномы 2-й степени, а в gnfs - начиная с 5-й и выше.

А что, для того чтобы добиться сложности алгоритмов как в GNFS,
$( O(C \cdot (\ln N ) ^ {1/3} \cdot (\ln \ln N) ^ {2/3} ) )$
нужны именно полиномы более 2-й (или не менее 5-й степени)?

Откуда берётся показатель степени для логарифма $1/3$ ? при полиномах 2-й степени он значит $1/2$, а для всех остальных начиная с 3-й, становится $1/3$, и неважно, 5-й степени мы берём полиномы, или ещё большей степени? Странно как то получается, почему от степени полиномов это не зависит

Может и улучшенный SIQS можно довести до трудоёмкости алгоритма, с показателем степени как в GNFS,
$( O(C \cdot (\ln N ) ^ {1/3} \cdot (\ln \ln N) ^ {2/3} ) )$
Вот это было бы большим прорывом, т.к. не надо было бы городить такую сложность как в GNFS,
с 10-ю "человеко-лет" работой реализации,

[wrest]

mathpath в сообщении #1713176 писал(а):

Непонятно как альпетрон собрать в виде командной строки,

См. https://github.com/alpertron/calculators

Цитата:

You can use Makefile to generate standalone executables. Just run make clean and then make. If you want to build only one of the calculators, you can run make calculator, where calculator is one of the following words: