Распараллеливание фактора Полларда-Ро

Question

Я недавно наткнулся на статью о распараллеливании алгоритма Полларда Ро и дал свое конкретное применение, в дополнение к тому факту, что я не достиг требуемого уровняматематика, мне интересно, поможет ли этот конкретный метод распараллеливания моему конкретному случаю.

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

Это правда?Должен ли я использовать это распараллеливание или использовать что-то еще?Должен ли я даже использовать Rho Полларда, или есть лучшее распараллеливание другого алгоритма факторизации?

Answer 1

Статья в Википедии содержит два конкретных примера:

Number                Original code      Brent's modification
18446744073709551617  26 ms              5 ms
10023859281455311421  109 ms             31 ms

Прежде всего, запустите эти два с вашей программой и посмотрите на свое время. Если они похожи на это («жесткие» числа, рассчитанные в 4-6 раз дольше), спросите себя, можете ли вы жить с этим. Или, что еще лучше, используйте другие алгоритмы, такие как простая классическая факторизация "грубой силы", и посмотрите, сколько времени они дают. Я предполагаю, что у них может быть сложный коэффициент, близкий к 1, но худшие абсолютные времена, так что это простой компромисс.

Примечание: Конечно, параллелизация - это путь, который, я думаю, вы знаете, но я думаю, что важно подчеркнуть. Кроме того, это помогло бы в случае, если другой подход лежит между таймингами Полларда-Ро (например, Поллард-Ро 5-31 мс, другой подход 15-17 мс) - в этом случае рассмотрите возможность запуска 2 алгоритмы в отдельных потоках для «гонки факторизации».

Если у вас еще нет фактической реализации алгоритма, вот Реализации Python .

Answer 2

Основная идея в разложении больших целых чисел состоит в том, чтобы использовать различные методы, каждый из которых имеет свои плюсы и минусы. Обычный план состоит в том, чтобы начать с пробного деления на простые числа до 1000 или 10000, после чего следует несколько миллионов шагов Полларда; это должно дать вам факторы примерно до двенадцати цифр. На этом этапе несколько тестов в порядке: число является основной степенью или идеальной степенью (существуют простые тесты для этих свойств). Если вы все еще не учли число, вы знаете, что оно будет сложным, поэтому вам понадобятся сверхпрочные инструменты. Полезным следующим шагом является метод Полларда p-1, за которым следует его близкий родственник - метод эллиптической кривой. Через некоторое время, если это не сработает, остаются только методы с квадратичным ситом или числовым полем, которые по своей сути параллельны.

Метод параллельного rho, о котором вы спрашивали, сегодня широко не используется. Как вы предположили, Поллард Ро лучше подходит для поиска мелких факторов, чем крупных. Для полураспада лучше проводить параллельные циклы на одном из сит, чем на Поллард Ро.

Я рекомендую форум по факторингу на mersenneforum.org для получения дополнительной информации.