Обсуждение факторизации больших чисел на factordb(dot)com

[ozheredov]

Kurkov_miroslav
922....951 не простое

[Dmitriy40]

ozheredov
Не давайте таких чисел, давайте только полупростые (два примерно сравнимых множителя, но минимум на десяток процентов по порядку (числу цифр) различающиеся чтобы не проходил метод Ферма).

-- 23.02.2026, 23:09 --

Kurkov_miroslav в сообщении #1718894 писал(а):

вру, полная факторизация:
5, 199, 4297, 198288001, 922550927427617391588545451158481186645922182249295573570234164150198501176789198289794570537508959184655951

Да, врёте, не полная: длинное число составное, т.е. не разложили.
"Разложить" - означает найти все простые делители (и в какой они степени), а не только несколько самых малых.

-- 23.02.2026, 23:10 --

Someone в сообщении #1718889 писал(а):

Возьмите моё $123$-значное число и разложите.

Там два делителя 53 и 71 знак. Числа в ЛС если Вам зачем-то они нужны. Хватило 33ч в пересчёте на один поток.

[ozheredov]

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

Не давайте таких чисел

Oops! , я думал чем рандомнее тем лучше. А за сколько времени моё раскладывается (если Вы пробовали)?

[Dmitriy40]

ozheredov
Рамдомнее конечно лучше, но не имеющее малых делителей, видите же что человек не хочет дальше раскладывать.
И хорошо бы не поддающееся быстро другим известным методам (Ферма, Полларда,ECM).
Ваше длиннющее не запускается (видимо программа не поддерживает столь длинные числа).
Ваше из 123 цифр (точнее из 108 для оставшегося составного числа) тоже не пробовал, но сейчас запустил, это где-то часа на полтора (~5ч в расчёте на один поток).

[Kurkov_miroslav]

Моя текущая реализация на Python ограничена по памяти и диапазону прямой (до 100 млн), поэтому мелкие факторы я вытаскиваю мгновенно. Чтобы доказать эффективность метода на больших полупростых числах, мне нужно адаптировать формулу под динамическое вычисление узлов прямой без хранения её в RAM. Дайте мне 3-4 числа, где множители лежат в диапазоне $10^{12} - 10^{15}$. Если я разложу их быстрее классического перебора на своем i3, это подтвердит линейность сложности $O(P)$

[Dmitriy40]

Kurkov_miroslav в сообщении #1718904 писал(а):

где множители лежат в диапазоне $10^{12} - 10^{15}$. Если я разложу их быстрее классического перебора на своем i3, это подтвердит линейность сложности O(P)

Во-первых, не подтвердит.
Во-вторых, такие делители ищутся методом ECM за доли секунды, а сравнивать такие малые времена бесполезно, там сторонних расходов больше чем самого вычисления.
В-третьих, ну вот Вам число 799901373267129308361020163753954166482974541224386517850121, в нём все делители меньше $10^{15}$, а разлагается оно менее чем за секунду.

-- 24.02.2026, 00:55 --

ozheredov в сообщении #1718898 писал(а):

А за сколько времени моё раскладывается (если Вы пробовали)?

Разложилось. В большом составном три делителя, 34, 36, 39 цифр (покажу их в ЛС). ECM их найти не смог, работало NFS. Справилось за 6ч в расчёте на один поток.

-- 24.02.2026, 01:09 --

ozheredov
Второй запуск только ECM в 4 потока, за 2.5м нашёлся делитель 36 цифр, потом за 4.5м нашёлся второй 39 цифр, всего потрачено 7м.
Вот поэтому и неинтересно сравнивать скорость на составных с более чем двумя делителями, слишком они легко раскладываются. А вот полупростые ...

[Someone]

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

В-третьих, ну вот Вам число 799901373267129308361020163753954166482974541224386517850121, в нём все делители меньше $10^{15}$, а разлагается оно менее чем за секунду.

Подтверждаю. Wolfram Mathematica разлагает на $4$ простых множителя за $\approx 0{,}889$ секунды.