Бесконечность простых чисел-близнецов

[Skipper]

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

Какой из? Их много известно

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

Ну вот пример, перемножим 100-битное просто число на 1400-битное простое, получим 1500-битное полупростое число.
Какой алгоритм будет лучшим для факторизации?

PS То есть, очевидно, что существует множество чисел, которые можно разложить на множители ТОЛЬКО методом эллиптических кривых. Другого не дано.

[Dmitriy40]

Skipper
ECM хорошо работает когда минимальный (а не максимальный) делитель заметно меньше квадратного корня из числа, вот тогда есть большая вероятность что он его найдёт достаточно быстро.
Если же оба делителя примерно одинаковы по длине, то нет, ECM уже не лучший метод. Уже для чисел от 100..130 знаков лучшим будет метод общего числового поля GNFS (например потому что он работает не с длинной арифметикой, в отличие от ECM). И в той же вики об этом прямо сказано. Потому обычно методом ECM пытаются найти делить до кубического корня (или несколько меньше), если не получилось то запускают GNFS.

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

PS То есть, очевидно, что существует множество чисел, которые можно разложить на множители ТОЛЬКО методом эллиптических кривых. Другого не дано.

Это ни о чём не говорит: существуют несколько множеств чисел, которые реально можно разложить лишь одним из специальных методов. Например числа любой длины вида $pq, p<100$ великолепно раскладываются проверкой 25-ти простых делителей до 100. А числа любой длины вида $pq, |p-q|<10^6$ прекрасно раскладываются методом Ферма (и при достаточно большой длине не раскладываются за разумное время ни ECM, ни GNFS). И так далее.

[Skipper]

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

Это ни о чём не говорит: существуют несколько множеств чисел, которые реально можно разложить лишь одним из специальных методов

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

А числа любой длины вида $pq, |p-q|<10^6$ прекрасно раскладываются методом Ферма (и при достаточно большой длине не раскладываются за разумное время ни ECM, ни GNFS).

Ну да, значит наилучшая программа факторизации, это программа, которая содержит, множество таких, уникальных в своём роде алгоритмов, которые для чисел специального вида, раскладываются только этим алгоритмом.
Я пока вижу, таких три-
1) ECM, 2) GNFS, 3) метод Ферма. Может быть есть ещё какие-то.

Самое большое подмножество видимо, ECM охватывает: так как GNFS- оптимальный только для полупростых чисел у которых оба делителя примерно одинаковой длины (а таких от общего множества чисел небольшой процент), а метод Ферма- незаменим ничем, на ещё меньшем подмножестве чисел.

-- Пн ноя 24, 2025 20:37:12 --

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

Некоторые из них я 10 лет назад просчитал до 1.1e15 (и часть добавил в OEIS, что вспомнил), что потребовало всего недели три счёта в одном потоке.

Поразительно, как можно написать, чтобы до 1.1e15 за три недели программа посчитала..

[Dmitriy40]

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

Я пока вижу, таких три-
1) ECM, 2) GNFS, 3) метод Ферма. Может быть есть ещё какие-то.

Ещё два алгоритма Полларда (Р и Р-1), они могут находить делители намного быстрее ECM.

Вообще, умные люди уже подумали/посчитали как будет быстрее: запускают несколько сотен тысяч (или миллионов) итераций всех быстрых алгоритмов (делители, Ферма, Полларда, может ещё какие-то), потом ECM примерно до кубического корня (или до корня 4-й степени если числа велики, а если малы, то и до квадратного/упора), потом или QS (квадратичное решето, для чисел до примерно 100 знаков) или GNFS. Тесты перед ECM очень редко когда находят делители, обычно проверяемые числа не имеют малых делителей или не имеют нужной формы, но тесты занимают секунды и потому это не принципиально.

Имейте в виду, что есть готовые и программы и библиотеки с реализацией всех методов (для многих даже в (англо)вики есть готовый код) и есть онлайн факторизаторы (ECM+QS/GNFS). Так что если цель не научиться, а разложить, то самому писать не обязательно.

-- 24.11.2025, 22:14 --

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

Поразительно, как можно написать, чтобы до 1.1e15 за три недели программа посчитала..

Обычное решето Эратосфена, плохо реализованное и потому впятеро медленнее быстрейшего, которое около 1e15 перебирает примерно 1.5e9 чисел в секунду (т.е. до 1e15 считать дней 5, в начале скорость выше), а моё лишь 0.3e9/c (позже несколько ускорил, но проигрыш примерно втрое так и остался). Ну а после решета проверить список простых на заданные условия уже несложно.

[Skipper]

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

если цель не научиться, а разложить, то самому писать не обязательно.

На самом деле, и научиться хочу, то есть разобраться в сути ECM, со всеми его статистическими особенностями.

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

[Dmitriy40]

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

Но интересно, и разложить, подскажите, какой нибудь хороший онлайн факторизатор (ECM+QS/GNFS).

Хороший вот этот: https://www.alpertron.com.ar/ECM.HTM - ввести число (или несколько), нажать кнопку Factor. Больше 100-120 цифр числа лучше не задавать, будет долго или очень долго (140+ цифр). Разумеется факторизация реально выполняется в браузере на локальном компе, так что выключить комп и зайти через неделю за результатом не получится.

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

Или программу, устанавливаемую на обычный домашний компьютер под Windows.

Процитирую недавнее:

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

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

Подробнее и как запускать с примерами написано там же двумя сообщениями ниже, тоже обязательно посмотрите.
Её можно заставить не использовать ECM (ключ -noecm) или не переключаться на QS/GNFS и долбить ECM до упора (не помню как, будет нужно поищу). Отключить предпроверки перед ECM у меня сегодня не получилось.

[Skipper]

Спасибо.
(будет с чем посоревноваться в скорости, когда я реализую свой ECM..)

-- Вт ноя 25, 2025 08:48:31 --

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

Хороший вот этот: https://www.alpertron.com.ar/ECM.HTM - ввести число (или несколько), нажать кнопку Factor.

Ну вот я задал этому онлайн-факторизатору, разложить на множители, следующее 70-значное число,

6944789012800024057080093442480380292657619004509430413362525412029247

Это число кстати, сложнее разложить на множители чем вычислить миллион цифр после запятой у числа пи.
Не осилив за 2 минуты способом ECM, он переключился на SIQS, с некими параметрами,
"SIQS parameters: 11797 primes, sieve limit: 54840
Multiplier: 23, factor base: 270001",
Какие там он ещё алгоритмы копал, не знаю, но разложил на множители он это число только почти за 14 минут.


А вот этот факторизатор,
https://ru.numberempire.com/numberfactorizer.php

раскладывает на множители это число за 12 секунд.. Почему такая разница?
Если дело в том, что этот не на моём компьютере "крутится", то всё равно разница поразительно большая.
То ли там какой-то суперкопьютер, то ли там всё же лучше алгоритмы?

Если дело в суперкомпьютере, значит и я, сколь бы не пытался, не смогу написав программу, на своём компе разложить это число быстрее чем за 14 минут?

[Dmitriy40]

Да, этот работает побыстрее. Но ограничен длиной 70 знаков, что маловато.

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

Какие там он ещё алгоритмы копал, не знаю, но разложил на множители он это число только почти за 14 минут.

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

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

То ли там какой-то суперкопьютер, то ли там всё же лучше алгоритмы?

Думаю оно просто умеет многопоточно локально считать (проверить пока не могу), как и YAFU, вон времена очень похожи. И возможно оптимизировано лучше однопоточного Альпетрона.

[Skipper]

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

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

Комп у меня конечно устаревший, но не настолько чтобы уж совсем..
Вы как-то выше сами писали,

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

Знаю что многие считают на компах и 10-летней давности, и 15-летней, а то и 20-летней. Или недавних, но недорогих и потому по скорости как хорошие 15-летние.

У меня 16-летней, но 3 ГГц процессор с 4-мя ядрами, и 8 ГБ оперативной памяти.
Тогда в те времена, такой компьютер был по мощности (производительности) примерно как терминальный сервер, который
на работе стоял.

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

[Dmitriy40]

Skipper
У меня комп 12 летней давности, 4 ядра на 3.5 ГГц. Практически как и Ваш, только видимо ещё и AVX2 поддерживает (правда вряд ли им пользуются факторизаторы).
Почему у Вас 14 минут я без понятия, но это точно не нормально. Может что-то с браузером ...

[Dmitriy40]

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

А вот этот факторизатор, https://ru.numberempire.com/numberfactorizer.php
раскладывает на множители это число за 12 секунд.. Почему такая разница?

Похоже тут код выполняется на стороне сервера, во всяком случае у меня проц оказался не загружен при факторизации. И тогда да, вполне вероятно что там сервер лучше наших компов. Видимо потому и ограничение в 70 цифр, чтобы не загружать сервер слишком надолго.

[wrest]

Телефон раскладывает локально в один поток (в pari/gp) за 20сек

[Dmitriy40]

Вот кстати да, PARI/GP же, у меня на компе за 61с.

[wrest]

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

Вот кстати да, PARI/GP же, у меня на компе за 61с.

factorint(n,4+2) - побыстрее немного будет.

[Dmitriy40]

Да, так за 53с.
И похоже делители находит не ECM, а MPQS (разновидность QS, квадратичного решета, которое само разновидность метода Ферма) - если его запретить, то за 4 минуты не может разложить, а с запрещённым ECM (8+4+2) раскладывает за те же 53с.
Да, в режиме отладки прямо видно что разложило именно MPQS.

-- 25.11.2025, 23:48 --

Skipper
Ну вот, а Вы ECM лучший, ECM ...