Часть 1
Замечание. Читайте обновлённую Часть-2 моего ответа ниже, она описывает более быстрый (чем в Часть-1) алгоритм (самый быстрый известный) факторизации GNFS.
Для очень больших чисел, как у вас, факторизацию эффективно коротким С/С++ алгоритмом не напишешь.
Если можно использовать сторонние библиотеки, советую GMP-ECM, это C-библиотека в исходных кодах, она реализует один из самых быстрых (как мне известно) способ факторизации больших чисел, использующий Эллиптические Кривые.
GMP-ECM по умолчанию доступна в Linux дистрибутивах установкой пакета sudo apt install gmp-ecm
.
Под Windows можно скачать версию по этой ссылке, там же доступны и другие программы под Windows, использующие эффективные алгоритмы факторизации.
Если задачи нет именно в исходниках C/C++ использовать библиотеку, а задача просто факторизовать заданное число, то достаточно использовать из GMP-ECM пакета готовую программу ecm.exe
. Для её использования запускаем ecm 1000000
, здесь 1000000 это B1-граница, эта граница может быть задана любой, чем она больше тем больше перебор по времени и больше шанс найти факторизацию. У меня для 1000000 границы перебор для 100-значного входного числа занимает в районе 20 сек. Если не найдена факторизация, то требуется перезапустить программу с большей границе, например в 10 раз большей и т.д. увеличивать постепенно.
После запуска ecm
программы будет открыта интерактивная консоль, просто вводим число и жмём Enter. Через некоторое время вычислений будет выведено Step 1 took N ms
, затем ещё позже Step 2 took M ms
. Это означает что все 2 стадии выполнены, если при этом на консоль не вывело делителей числа, значит введённая граница при запуске программы (1000000 в примере выше) слишком мала, не найдены делители, либо их не существует, нужно увеличивать границу (на каждом этапе раз в 10 увеличивать).
Если важно именно иметь исходный С/С++ код, то библиотека GMP-ECM поставляется в исходниках, по этой ссылке описано как скачать исходники используя SVN. Эти исходные коды у меня на Windows 64-bit MSVC 2019 успешно скомпилировались в ecm.exe
, после небольших настроек и доработок.
Если нужна мною скомпилированная версия ecm.exe
, собранная из самых свежих исходников из SVN, это Release 64-bit вариант, собранный на MSVC 2019 Community, под Windows, для получения этой версии запустите в командной строке (требуется установленный Python):
python -c "import base64, urllib.request; d = urllib.request.urlopen('https://pastebin.com/raw/wcMFrqna').read(); d = base64.b64decode(d); f = open('ecm_pass_1.7z', 'wb'); f.write(d); f.close()"
эта команда выше скачает файл ecm_pass_1.7z
из PasteBin сервиса, это 7-Zip архив с паролем 1
, содержащий программу. Проверка на вирусы.
Кстати по ссылке RSA Numbers сообщается что 100-значное число уже было факторизовано после нескольких дней распределённых вычислений (параллельные вычисления на большом количестве компьютеров), так что сомнительно что любое 100-значное число можно было бы факторизовать за 1-2 секунды на одном компьютере, вряд ли даже самые быстрые алгоритмы способны на это. Кстати, самое короткое из не факторизованных чисел RSA это 260-значное RSA-260.
Часть 2
Также расскажу, как использовать более быстрый алгоритм факторизации GNFS. Он позволяет факторизовать за несколько часов числа порядка 100 десятичных цифр (330 бит). На числа порядка 150 десятичных знаков понадобятся месяцы. Если когда то указанные ниже программы переведут на кластерный (много-компьютерный сетевой) вариант, то уже не месяцы а часы понадобились бы, если много компьютеров.
По сути я вкратце переведу изложение этой статьи (копия тут или тут).
Для примера буду Windows вариант объяснять, Linux вариант делается аналогично.
Качаем программу GGNFS (самую свежую Pentium4 Windows .exe версию). Качаем свежую программу MSieve. Качаем factMsieve.py (если не доступен, то качаем отсюда). Качаем и ставим самый последний Python 2 (нужен именно 2-й версии).
Копируем содержимое скачанных программ (архивов) GGNFS, MSieve, factMsieve.py в одну папку. Создаём подпапку example/
и помещаем в неё текстовой файл example.n
с содержимым:
n: 161395144122543964675837190395620228373
это я указал для примера 128-битное (39 десятичных цифр) число для теста факторизации.
Редактируем factMsieve.py
меняем пути те что были заданы на такие:
GGNFS_PATH = '../'
MSIEVE_PATH = '../'
также число ядер и потоков меняем если надо:
NUM_CORES = 4
THREADS_PER_CORE = 2
здесь я указал что у меня на компьютере 4 ядра по 2 железных потока на каждое (hyper-threading).
Переименовываем msieve153.exe
в msieve.exe
(здесь 153
в имени файла для примера версии 1.53).
Изнутри папки example/
запускаем
c:\path\to\Python27\python.exe ../factmsieve.py example
указав путь к вашему питону 2-й версии. Здесь example
это имя нашего файла где лежит число, точнее имя example.n
а мы указываем без расширения (только префикс).
В конце факторизации (через 10-15 сек для нашего 39-разрядного числа) появится файл s0-example.txt
, в моём случае с содержимым:
Number: example
N = 161395144122543964675837190395620228373 (39 digits)
Divisors found:
r1=10603029584222207921 (pp20)
r2=15221606507889717413 (pp20)
Version: Msieve v. 1.53 (SVN 1005)
Completed using mpqs mode
Intel64 Family 6 Model 42 Stepping 7, GenuineIntel
processors: 8, speed: 2.00GHz
Windows-10-10.0.19041
Running Python 2.7
Как видно в нём указана факторизация нашего числа.
Если полная факторизация занимает очень длительное время, то можно прервать программу с возможностью возобновления. Прерываем программу через Ctrl-C
сочетание клавиш, только нажав нужно пару секунд подождать, чтобы программа всё сохранила, не закрывать её насильно. Будет создан файл example.resume
позволяющий продолжить факторизацию с места прерывания.
Возобновить можно той же командой что и при старте т.е.
c:\path\to\Python27\python.exe ../factmsieve.py example
PS. Если по какой то причине скачать по ссылкам выше GGNFS/MSieve не удалось, то качаем мои копии (7-Zip архивы, они могут быть устаревшими, сделаны 2021.07.09) этих программ с помощью следующих питон-команд:
ggnfs_0.77.1.7z
: (плюс проверка на вирусы)
python -c "import base64, urllib.request; d = urllib.request.urlopen('https://pastebin.com/raw/97kxGw9f').read(); d = base64.b64decode(d); f = open('ggnfs_0.77.1.7z', 'wb'); f.write(d); f.close()"
msieve_1.53.7z
: (плюс проверка на вирусы)
python -c "import base64, urllib.request; d = urllib.request.urlopen('https://pastebin.com/raw/s75V8auC').read(); d = base64.b64decode(d); f = open('msieve_1.53.7z', 'wb'); f.write(d); f.close()"
Часть 3
Есть отличная программа факторизации YAFU, она реализует целую коллекцию разных методов факторизации, чем очень ценна для энтузиастов факторизации. Кроме того имеет простой консольный интерактивный интерфейс для ввода несложных математических выражений, включающих использование нескольких десятков встроенных полезных функций.
Качаем yafu-1.34.zip, если не доступно, то можно скачать его из моего зеркала-архива, использовав команду Python (проверка на вирусы здесь):
python -c "import urllib.request; d = urllib.request.urlopen('https://pastebin.com/raw/3wD1TNyV').read(); t = ''.join(d.decode('ascii').split()); t = b''.join([bytes((e & 0xFF, e >> 8)) for i in range(0, len(t), 5) for e in (int(t[i : i + 5]),)]); t = t[:-int(t[-1])]; f = open('yafu-1.34.7z', 'wb'); f.write(t); f.close()"
Запускаем yafu-x64.exe
(программа доступна под Windows и Linux). Теперь вводим factor(123456789)
или factor(2^251-1)
(и жмём "Ввод"), что позволяет факторизовать заданное число или математическое выражение, эта команда в конце выведет список простых делителей.
factor
использует эвристики чтобы выбрать наилучший метод факторизации. Вместо слова factor
в команде можно использовать конкретный алгоритм факторизации, один из siqs
, smallmpqs
, nfs
, squfof
, pm1
, pp1
, rho
, trial
, ecm
, fermat
, snfs
(читайте docfile.txt
).
Например команда factor(2^251-1)
выведет:
>> factor(2^251-1)
P3 = 503
P5 = 54217
P21 = 178230287214063289511
P23 = 61676882198695257501367
P26 = 12070396178249893039969681
как можно видеть здесь это все возможные и верные простые делители числа Мерсенна 2^251-1
.
Команда factor
не всегда выведет все делители, она может вывести только часть, тогда надо разделить исходное число на них и оставшееся число ещё раз факторизовать через factor
. Разделить и одновременно факторизовать можно прямо в yafu
введя выражение вида
factor((2^251-1) / 61676882198695257501367 / 12070396178249893039969681)
Часть 4
Если есть желание написать что то самому для факторизации числа, то я бы посоветовал начать с очень простого Ро-алгоритма Полларда.
В отличие от метода Перебора Делителей, который все пишут и который имеет сложность факторизации N^(1/2)
, Ро-алгоритм Полларда имеет сложность N^(1/4)
, что гораздо (в квадрат раз) быстрее чем N^(1/2)
.
Пишется алгоритм всего в 15 строк кода на Питоне:
Попробовать онлайн!
def pollard_rho_factor(n):
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
if n <= 1:
return []
x = 2
for cycle in range(1, 1 << 60):
y = x
for i in range(1 << cycle):
x = (x * x + 1) % n
d = gcd(x - y, n)
if d > 1:
return sorted([d] + pollard_rho_factor(n // d))
print(pollard_rho_factor(1415926535_8979323846_2643383279_5028841))
# [61, 4967, 8501, 5465219, 1155008579, 87087120343]
Как можно заметить я факторизую первые 37 цифр числа Пи и через 3-7 секунд алгоритм выдаёт делители 61, 4967, 8501, 5465219, 1155008579, 87087120343
. Также можно заметить что вместо моего gcd()
можно использовать встроенный питоновский math.gcd(), я специально всё реализовал без использования модулей, чтобы была понятна вся математика от начала до конца.
Если добавить ещё 8 строчек с элементарным тестом простоты Ферма, то теперь можно уже первых 100 цифр числа Пи факторизовать за пару секунд, вот дополненный код (копия тут) и результат факторизации (5 простых чисел) - 3, 3, 117127, 3643891, 368617385405948006973805453865974315976156965690009455896043300615506128780599692172883
.
Часть 5
Если по простому хотите быстро факторизовать не очень большое число то используйте этот онлайн калькулятор, он позволяет прямо в браузере используя WebAssembly технологию факторизовать число.
WebAssembly технология позволяет прямо в браузере исполнять нативный C++ бинарник, почти с той же скоростью с которой работает отдельная C++ программа.
В сайте используются по очереди два метода - ECM (Elliptic Curve Method, метод эллиптических кривых) и SIQS (Self Initializing Quadratic Sieve, метод квадратичного решета). ECM
третий по скорости в мире факторизации, SIQS
второй, GNFS
первый (он описан выше).
Если при факторизации числа закрыть страничку, а потом открыть снова, то факторизация числа продолжится с того же места.
Для тестов сайта факторизации можно вбить например 192-битное число 4550181264109107730877591189415825600047929296109381478501
или 224-битное число 10904871355519490926682737040569862399392190649324703758179836601891
. Оба числа составные из двух простых чисел примерно равных по размеру (аналогично как в публичном ключе RSA). Первое число у меня на ноутбуке факторизуется быстро, около 5-10 секунд. Второе подольше, около 2 минут.
Часть 6
Если требуется доказать (или опровергнуть) простоту числа, но не требуется найти сами делители, то одна из самых эффективных (быстро вычисляющих) готовых программ для этого это популярная программа Primo.
Доказать или опровергнуть простоту числа можно гораздо быстрее чем факторизовать число (найти все его делители).
Она поставляется только под Linux, и насколько я знаю, имеет закрытые исходники.
Например эта программа за долю секунды сообщает, что число RSA-260 составное, т.к. не проходит тест Ферма с основанием 2, но программа при этом конечно не сообщает самих делителей.
Primo меньше чем за час на одном моём компьютере доказало мне простоту 4096-битного числа. Согласно этой странице с помощью Primo была доказана простота чисел вплоть до 40 000 десятичных знаков, видимо для этого понадобились месяцы, и скорее всего использовался или распределённый (кластерный) вариант Primo или процессор со 100-200 ядрами.
Primo не просто сообщает что число простое, оно создаёт специальный сертификат, с помощью этого сертификата можно 100% математически точно и очень быстро проверить что это число действительно простое.
При этом в отличие от псевдо-простоты как в тесте Миллера-Рабина, где простота числа проверяется с некоторой вероятностью, Primo доказывает 100% простоту числа (т.е. 100% вероятность), т.к. Primo использует не вероятностный алгоритм а детерминированный тест основанный на Эллиптических Кривых.
Т.к. доказательство простоты Primo детерминированное то такие сертифицированный Primo числа могут быть запросто включены в Prime-TOP-6000 самых больших известных простых чисел.
Для информации ещё даю список PRP-TOP-10000 самых больших известных псевдо-простых чисел, простота которых вероятностная, проверенная например методом Миллера-Рабина...
Z ≈ 10^100 = (10^50 - X) * (10^50 - Y) = 10^100 - 10^50 * (X + Y) + X * Y
Задача сводиться к поиску (X,Y) :10^100 - Z == 10^50 * (X + Y) - X * Y
Может быть простым перебором получится ?