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

[Skipper]

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

вдруг она не только для полупростых чисел вычисляется.

Может быть и так. Если включить и не только полупростые, то делители будут меньшей длины, а значит учитываться должны разложения с меньшим B1, и меньшим количеством кривых (то есть на предыдущих итерациях алгоритма).
Надо будет проверить только на полупростых, с другими длинами чисел, ну а тут- процентов 5 вижу пока.

[Dmitriy40]

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

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

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

[mathpath]

Выложил на гитхабе проект на гоу, о котором я тут раньше писал:
https://github.com/sbsoft-cmd/SIQS

[mathpath]

Dmitriy40 писал(а):

816961596487035153808521370726340812479135539732870244997478848571366454193709 = 902050502583221677542019905166933490831 * 905671682624736010363440819360298942339

SIQS разложил за 24 секунды.

Нашел на гитхабе проект на расте:
https://github.com/remyoudompheng/yamaquasi
У меня он разложил это число за минуту (SIQS)

[Dmitriy40]

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

Подкажите, по каким формулам тут считается "оптимальное" количество кривых?

Что-то про это есть в рувики:

рувики писал(а):

Порядок группы точек, лежащих на эллиптической кривой $|E|$ над $Z_p$, согласно теореме Хассе ограничен: $p + 1 - 2\sqrt{p} \leq |E| \leq p + 1 + 2\sqrt{p}$. Представляется важным исследовать [8] вероятность того, что в этом интервале может лежать некоторое гладкое число (в этом случае существуют кривые, порядок которых — гладкое число). Не существует доказательств того, что в интервале Хассе есть всегда некоторое гладкое число, однако использованием эвристических вероятностных методов, теоремы Канфилда-Эрдёша-Померанса(англ. Canfield–Erdős–Pomerance theorem)[9] и L-нотации получается оценка, что достаточно взять $L[\sqrt{2}/2, \sqrt{2}]$ кривых до получения гладкого порядка группы. Это эвристическая оценка хорошо применима на практике.

[mathpath]

Дипсик умеет создавать публичные ссылки
Например вот ссылка на краткое описание метода факторизации - квадратичного решета (Quadratic Sieve, QS):
https://chat.deepseek.com/share/gzv4ul15j3roma0b72
Почему при этом используются два типа полиномов:
https://chat.deepseek.com/share/suexth28p3q0y7nq68

[B@R5uk]

А вы с RSA Factoring Challenge числа не пробовали? Сам на эту штуку буквально только что наткнулся.

[mathpath]

B@R5uk в сообщении #1714742 писал(а):

А вы с RSA Factoring Challenge числа не пробовали? Сам на эту штуку буквально только что наткнулся.

Да, последняя версия на расте, которую я нашел на гитхабе, уже подходит для этого

[Dmitriy40]

А смысл? Там же вовсю GNFS (самый быстрый известный метод) применялся и то это заняло годы (и десятилетия) вычислений в расчёте на один поток.

-- 14.01.2026, 14:00 --

Причём рекламируемому тут ECM там вообще ничего не светит - числа полупростые и точно не имеют малых делителей.

-- 14.01.2026, 14:04 --

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

У меня он разложил это число за минуту (SIQS)

В один поток YAFU справилась за 80с, разницу с 1 минутой вполне можно списать на разницу в компах. Т.е. эта реализация не особо быстрее имеющейся YAFU.

[mathpath]

B@R5uk в сообщении #1714742 писал(а):

А вы с RSA Factoring Challenge числа не пробовали? Сам на эту штуку буквально только что наткнулся.

Я только что разложил RSA-100
На все про все ушло 6200 секунд
Программа на расте собирается в бинарник весом в 26 метров, и исполняемый файл называется ymqs
B1 = 3681761
B2 = 1067710690
Размер factor base - 130656
Исходников на расте там почти на мегабайт, но там все в кучу свалено - и ECM, и поллард, и SIQS

(Оффтоп)

./ymqs 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
Input number 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
Testing small prime divisors
Attempting P-1 with B1=2000000 B2=4.8e9
Pollard P-1 failure in 0.388s
Attempting ECM with 100 curves B1=100000 B2=1.9e7
ECM failure after 9.918s
Selected multiplier 139 (score 9.12/10)
Smoothness bound B1=3681761
Factor base size 130656 ([2, 3, 5, 7, 11, 13, 17, 19, 23, 31])
Sieving interval size 512k
Generated 14700 values of A with 13 factors in 2579..3461 (4096 polynomials each, spread=0.91%)
Max large prime B2=1067710690 (290 B1)
Max double large prime 3931055577725090 (290 B1^2)
Sieved 2048M 4096 polys found 39 relations (~0.1% done, p=621 p12=1 pp=2790 cycles=[39, 0, 0, 0, 0, 0, 0, 0])
Sieved 8192M 16384 polys found 156 relations (~0.5% done, p=2483 p12=7 pp=11284 cycles=[155, 1, 0, 0, 0, 0, 0, 0])
Sieved 55296M 110592 polys found 988 relations (~3.0% done, p=16581 p12=518 pp=76667 cycles=[973, 15, 0, 0, 0, 0, 0, 0])
Sieved 110592M 221184 polys found 2041 relations (~7.4% done, p=33144 p12=2101 pp=153368 cycles=[1961, 70, 9, 1, 0, 0, 0, 0])
...
Sieved 1847296M 3694592 polys found 121979 relations (~97.4% done, p=552326 p12=1136307 pp=2564175 cycles=[33660, 21897, 18387, 14064, 10441, 7550, 5298, 10682])
Need 926 additional relations
Need 7 additional relations
Found enough relations
Sieved 1894651M 3789303 polys found 130112 relations (~99.8% done, p=566620 p12=1196594 pp=2629734 cycles=[34496, 22979, 19661, 15223, 11391, 8347, 5904, 12111])
...................... Время выполнения: 6238.894706 секунд
...................... Время выполнения: 6238.894705604 секунд
Input 130112 relations 130657 factors
Filtered 127961 relations 127880 factors
Build matrix 127880x127961 (56.8 entries/col, 25.4 in size 64 dense block)
[Lanczos] Selected block 1 with rank 64
[Lanczos] Space is exhausted after 2023 blocks of size 64
[Lanczos] found kernel subspace of rank <= 58
[Lanczos] final kernel rank <= 58
Found kernel of dimension 58 in 134.602s
2 divisors from 1 successful factorizations
37975227936943673922808872755445627854565536638199
40094690950920881030683735292761468389214899724061

[Dmitriy40]

YAFU в ~4 потока методом GNFS справилась за полчаса:

(Оффтоп)

01/14/26 18:12:48, ****************************
01/14/26 18:12:48, Starting factorization of 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
01/14/26 18:12:48, using pretesting plan: noecm
01/14/26 18:12:48, no tune info: using qs/gnfs crossover of 95 digits
01/14/26 18:12:48, no tune info: using qs/snfs crossover of 95 digits
01/14/26 18:12:48, ****************************
01/14/26 18:12:48, rho: x^2 + 3, starting 1000 iterations on C100
01/14/26 18:12:48, rho: x^2 + 2, starting 1000 iterations on C100
01/14/26 18:12:49, rho: x^2 + 1, starting 1000 iterations on C100
01/14/26 18:12:49, pm1: starting B1 = 150K, B2 = gmp-ecm default on C100
01/14/26 18:12:49, final ECM pretested depth: 0.000000
01/14/26 18:12:49, scheduler: switching to sieve method
01/14/26 18:12:49, nfs: commencing nfs on c100: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
01/14/26 18:12:49, nfs: commencing poly selection with 4 threads
01/14/26 18:12:49, nfs: setting deadline of 77 seconds
01/14/26 18:12:49, nfs: expecting degree 4 poly E from 1.15e-08 to > 1.32e-08
01/14/26 18:12:49, nfs: searching for avg quality poly E > 1.19e-08
01/14/26 18:14:06, nfs: completed 60 ranges of size 250 in 76.5695 seconds
01/14/26 18:14:06, nfs: best poly = # norm 1.173270e-13 alpha -4.510516 e 1.183e-08 rroots 2
01/14/26 18:14:06, nfs: commencing lattice sieving with 4 threads
01/14/26 18:15:10, nfs: found 298795 relations, need at least 4468504 (filtering ETA: 0h 14m), continuing with sieving ...
01/14/26 18:15:10, nfs: commencing lattice sieving with 4 threads
01/14/26 18:16:18, nfs: found 617715 relations, need at least 4468504 (filtering ETA: 0h 13m), continuing with sieving ...
01/14/26 18:16:18, nfs: commencing lattice sieving with 4 threads
01/14/26 18:17:52, nfs: found 932948 relations, need at least 4468504 (filtering ETA: 0h 17m), continuing with sieving ...
01/14/26 18:17:52, nfs: commencing lattice sieving with 4 threads
01/14/26 18:19:25, nfs: found 1244560 relations, need at least 4468504 (filtering ETA: 0h 16m), continuing with sieving ...
01/14/26 18:19:25, nfs: commencing lattice sieving with 4 threads
01/14/26 18:20:56, nfs: found 1525410 relations, need at least 4468504 (filtering ETA: 0h 15m), continuing with sieving ...
01/14/26 18:20:56, nfs: commencing lattice sieving with 4 threads
01/14/26 18:22:26, nfs: found 1829044 relations, need at least 4468504 (filtering ETA: 0h 12m), continuing with sieving ...
01/14/26 18:22:26, nfs: commencing lattice sieving with 4 threads
01/14/26 18:23:57, nfs: found 2133337 relations, need at least 4468504 (filtering ETA: 0h 11m), continuing with sieving ...
01/14/26 18:23:57, nfs: commencing lattice sieving with 4 threads
01/14/26 18:25:14, nfs: found 2427867 relations, need at least 4468504 (filtering ETA: 0h 8m), continuing with sieving ...
01/14/26 18:25:14, nfs: commencing lattice sieving with 4 threads
01/14/26 18:26:45, nfs: found 2736012 relations, need at least 4468504 (filtering ETA: 0h 8m), continuing with sieving ...
01/14/26 18:26:45, nfs: commencing lattice sieving with 4 threads
01/14/26 18:28:17, nfs: found 3046930 relations, need at least 4468504 (filtering ETA: 0h 7m), continuing with sieving ...
01/14/26 18:28:17, nfs: commencing lattice sieving with 4 threads
01/14/26 18:29:41, nfs: found 3350052 relations, need at least 4468504 (filtering ETA: 0h 5m), continuing with sieving ...
01/14/26 18:29:41, nfs: commencing lattice sieving with 4 threads
01/14/26 18:31:17, nfs: found 3677381 relations, need at least 4468504 (filtering ETA: 0h 3m), continuing with sieving ...
01/14/26 18:31:17, nfs: commencing lattice sieving with 4 threads
01/14/26 18:32:41, nfs: found 3966975 relations, need at least 4468504 (filtering ETA: 0h 2m), continuing with sieving ...
01/14/26 18:32:41, nfs: commencing lattice sieving with 4 threads
01/14/26 18:34:11, nfs: found 4296901 relations, need at least 4468504 (filtering ETA: 0h 0m), continuing with sieving ...
01/14/26 18:34:11, nfs: commencing lattice sieving with 4 threads
01/14/26 18:35:30, nfs: commencing msieve filtering
01/14/26 18:37:00, nfs: raising min_rels by 5.00 percent to 4847612
01/14/26 18:37:00, nfs: commencing lattice sieving with 4 threads
01/14/26 18:38:23, nfs: commencing msieve filtering
01/14/26 18:40:37, nfs: commencing msieve linear algebra
01/14/26 18:42:12, nfs: commencing msieve sqrt
01/14/26 18:43:34, prp50 = 40094690950920881030683735292761468389214899724061
01/14/26 18:43:34, prp50 = 37975227936943673922808872755445627854565536638199
01/14/26 18:43:34, NFS elapsed time = 1844.8632 seconds.
01/14/26 18:43:34, Total factoring time = 1845.5862 seconds

[mathpath]

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

YAFU в ~4 потока методом GNFS справилась за полчаса:

Глянул на исходники - минимальный набор без платформо-зависимых веток весит более 5 метров

[mathpath]

Алгоритм Ферма:
Если для числа n мы найдем такие x и y, что:
x² ≡ y² (mod n) (x и y сравнимы по модулю n)
и при этом
x ≠ y (mod n) и x ≠ -y (mod n)
Затем
x² - y² ≡ 0 (mod n)
То есть n делит разность квадратов, которая раскладывается:
x² - y² = (x + y)(x - y)
n | (x + y)(x - y)
Но
n ∤ (x - y) и n ∤ (x + y)
Следовательно, 1 < НОД(n, x ± y) < n
Эти НОД дают нетривиальные делители n

Все алгоритмы - и ECM, и SIQS, и GNFS - в конечном итоге находят x и y, удовлетворяющие условию Ферма, просто делают это разными путями.

Основная идея квадратичного решета в том, чтобы найти много чисел zᵢ, таких что zᵢ² mod n — гладкое число.
Затем комбинируют их, чтобы получить x² ≡ y² (mod n), и вычисляют нетривиальный НОД.

[Skipper]

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

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

Почитал книгу Ишмухаметова, и если я правильно понял, то там оптимальная степень полиномов $d$, вообще говоря, зависит от величины
факторизуемого числа $n$, определяется формулой, такой, если o малым от единицы можно пренебречь, страница 169:

$d = 3^{1/3} \cdot (\ln n / \ln \ln n) ^{1/3}$

Если $m$ - длина факторизуемого числа в битах , то считаем что $n = ~$ порядка $2^{m}$,
тогда

$d = (3 \cdot \ln 2^{m} / \ln \ln 2^{m} ) ^{1/3}$

Вообще говоря, автор в книге использует именно в этом месте, как и в других- символ $\log$ а не $\ln$ ,
и можно подумать что log - это не натуральный логарифм, а с другим основанием.
Тем более, что в других местах, используется именно $\ln$ .
Но прямо же на этой странице 169 немного ниже написано ,

таким образом, уменьшение значения показателя степени в наиболее
важном сомножителе $ \log n$ функции $L_n(a, c)$ от значения 1/2 в методе
квадратичного решета до 1/3 в методе решета числового поля дает тот
прогресс, который обеспечивает приоритет этого метода над методом
квадратичного решета

А выше, в книге при определении функции $L_n(a, c)$ используется именно символ $\ln$ а не $\log$ .
Значит, очевидно, автор использует оба этих варианта для определения одного и того же-
логарифма натурального. Вот зачем так делать?

Ладно, вернемся к определению оптимальной степени полиномов $d$,

$d = (3 \cdot \ln 2^{m} / \ln \ln 2^{m} ) ^ {1/3}$
$d = (3 \cdot 0.693 m / \ln (0.693 m ) ) ^ {1/3}$

округленно,
$d = (2 m / \ln (0.693 m ) ) ^ {1/3}$

где $m$ - длина в битах наших факторизуемых чисел.
Чтобы оптимальнее стало использовать степень полиномов уже не $2$ , а $3$, примем $d = 2.5$ ,
чтобы округленное в $ 3$ , считать $3$ оптимальным степенем полиномов.
А по формуле выше, $d$ достигает значения $2.5$ , при $m$ равным, 21 ,
а значит факторизацию чисел меньших $2^{21} $ что примерно равно 2 млн, оптимальнее проводить
со степенью полиномов $2$, то же самое происходит в методе квадратичного решета.
К тому же, в книге Ишмухаметодва написано что в методе решета числового поля, при степенях полиномов 2,
в любом случае (при факторизации любых сколь угодно больших числах) нет выигрыша по сравнению с методом квадратичного решета,
только проигрыш есть, из-за более сложной реализации алгоритма.
Значит, в GNFS, методе решета числового поля, трудоёмкость алгоритма, по сути становится $L_n(1/3, c)$
в принципе начиная от факторизуемых чисел 2 млн, и больших.

На практике же, аж вплоть до 365-битных чисел, что есть 110-значное число десятичной записи, метод квадратичного решета,
(не проверял) вроде, работает быстрее чем GNFS. Дальше GNFS выигрывает, а степень оптимальных полиномов, к примеру,
для факторизации 512-битного числа, что есть 155-значное число в десятичной записи, $d = 5.5$ округленно,
потому они при факторизации такого числа и использовали оптимальную степень полиномов $5$ .

RSA-896 имеет 896 бит (270 десятичных знаков) и пока что не факторизовано. За успешную факторизацию был предложен денежный приз в 75 000 долларов.
Думаю, что по причине известности такого числа, оно очередное на очереди, и прямо сейчас его пытаются факторизовать.
Интересно сколько лет ещё это займёт. Для такого числа, $d = 6.53$ округленно, и видимо, оптимальная степень
полиномов будет ужё то ли $6$ , то ли $7$.

RSA-1024 имеет 1024 бита (309 десятичных знаков) и пока что не факторизовано. За факторизацию был объявлен денежный приз в
100 000 долларов.
Успешная факторизация RSA-1024 имеет важное значение для многих пользователей алгоритма RSA-аутентификации с открытым ключом,
так как наиболее часто используемая длина ключа — 1024 бита.
Для такого числа, $d = 6.78$ округленно, тут уже очевидно, оптимальная степень
полиномов будет точно $7$.

RSA-1536 имеет 1536 бит (463 десятичных знака) и пока что не факторизовано. Ранее за успешную факторизацию было предложено
150 000 долларов.
Для такого числа, $d = 7.61$ округленно, тут уже очевидно, оптимальная степень
полиномов будет точно $8$.

В книге Ишмухаметова написано, что если выбрать степени полиномов больше чем $7$, то самым трудоёмким
этапом в алгоритме GNFS становится уже не просевание, а извлечение корня.
Вот подобное становится уже неизбежным, при оптимальной факторизации RSA-1536 .
Хотя наверное, такое число чтобы факторизовать то надо запустить на такую задачу все суперкомпьютеры в мире,
и то сотня лет понадобится.

Вот удобная формула,
d = ( (2 * 1536 ) / ( ln (0.693 * 1536 ) ) ) ^ (1/3)
для вычисления оптимальных степеней полиномов в онлайн-калькуляторе https://web2.0calc.ru/

[Skipper]

Цитата:

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

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

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

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

Вот, цитата,

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

Алгоритм Ферма:
Если для числа n мы найдем такие x и y, что:
x² = y² (mod n) (x и y сравнимы по модулю n)
и при этом
x ≠ y (mod n) и x ≠ -y (mod n)
Затем
x² - y² ≡ 0 (mod n)
То есть n делит разность квадратов, которая раскладывается:
x² - y² = (x + y)(x - y)
n | (x + y)(x - y)
Но
n ∤ (x - y) и n ∤ (x + y)
Следовательно, 1 < НОД(n, x ± y) < n
Эти НОД дают нетривиальные делители n

И для кубов то же самое, аналогично.
Это разность квадратов раскладывается, а сумма квадратов не раскладывается.
В случае с кубами же, раскладывается как разность кубов, так и сумма кубов.
Например с разностью кубов, аналогичное:

Алгоритм Ферма:
Если для числа n мы найдем такие x и y, что:
$x^3 \equiv y^3 (\mod n ) $ (x и y сравнимы по модулю n)
и при этом
x ≠ -y (mod n)
Затем
$x^3 - y^3 \equiv 0 (\mod n )$
То есть разность кубов делится на n , которая раскладывается:
$x^3 - y^3 = (x - y)(x^2 + xy + y^2)$
$(x + y)(x^2 + xy + y^2) $ делится на n ,
Но
$(x + y)$ не делится на n , а с какой то вероятностью, и $(x^2 + xy + y^2)$, не делится на n,
(с какой то вероятностью, может делиться на n) ,
значит, если в случае, когда оба не делятся, то с какой то вероятностью получим,
1 < НОД(n, x + y) < n ,
Тогда, этот НОД , даст первый нетривиальный делитель n , а второй, если подставить трехчлен,

Или я что-то тут неправильно понял?
Программно не проверял, какая тут вероятность, но в случае, если
найти такие два куба которых сравнимы по модулю, легче чем найти два квадрата,
то тем самым окажется, что принципиально новая возможность факторизации будет
работать быстрее чем все известные ECM , SIQS, GNFS .
Искал, но нигде не видет каких доказательств, что с кубами дело обстоит хуже чем с квадратами.

PS mathpath , как вы набираете символ-число возведения в степень, иначем чем в
LaTeX с помощью ^{..} ? Ваш текст если скопировать то явно удобнее читать,
не переключаясь каждый раз на предпросмотр, без всяких тэгов, спецсимволов и прочего,
прямо в набираемом тексте.