Пробный отдел - Trial division

Эта статья о математическом алгоритме. О судебной палате Международного уголовного суда см. Судьи Международного уголовного суда.

Пробный отдел самый трудоемкий, но самый простой для понимания целочисленная факторизация алгоритмы. Основная идея тестов пробного деления, чтобы увидеть, п, целое число, подлежащее факторизации, можно разделить по очереди на каждое число, которое меньше п. Например, для целого числа п = 12, единственные числа, которые делят его: 1, 2, 3, 4, 6, 12. Выбираем только самые большие степени простых чисел в этом списке указано, что 12 = 3 × 4 = 3 × 2².

Пробное деление впервые было описано Фибоначчи в его книге Liber Abaci (1202).^[1]

Метод

Учитывая целое число п (п относится к «целому числу, подлежащему факторизации»), пробное деление состоит из систематической проверки того, п делится на любое меньшее число. Ясно, что имеет смысл тестировать факторы-кандидаты меньше, чем п, и в порядке от двух вверх, поскольку произвольный п чаще делится на два, чем на три, и так далее. При таком порядке нет смысла проверять делимость на четыре, если число уже определено, что оно не делится на два, и так далее для трех и любого числа, кратного трем, и т. Д. Следовательно, усилия можно уменьшить, выбрав только простые числа в качестве возможных факторов. Кроме того, факторы испытания не должны идти дальше, чем ${\displaystyle \scriptstyle {\sqrt {n}}}$ потому что, если п делится на некоторое число п, тогда п = p × q и если q были меньше, чем п, п был бы обнаружен ранее как делимый на q или простым фактором q.

Возможна определенная оценка простых множителей. Предполагать п_я это яое простое, так что п₁ = 2, п₂ = 3, п₃ = 5 и т. Д. Тогда последнее простое число, которое стоит проверить как возможный множитель п является п_я куда п²_я + 1 > п; равенство здесь означало бы, что п_я + 1 фактор. Таким образом, тестирования с 2, 3 и 5 достаточно до п = 48, а не просто 25, потому что квадрат следующего простого числа равен 49 и меньше п = 25 достаточно 2 и 3. Если квадратный корень из п быть целым, то это фактор и п это идеальный квадрат.

Пример алгоритма пробного деления, использующего последовательные целые числа в качестве пробных факторов, выглядит следующим образом (в Python ):

def trial_division(п: int) -> Список[int]:    "" "Возвращает список простых множителей натурального числа." ""    а = []               # Подготовить пустой список.    ж = 2                # Первый возможный фактор.     пока п > 1:         # Пока у n есть оставшиеся факторы ...        если п % ж == 0:   # Остаток от деления n на f может быть равен нулю.             а.добавить(ж)  # Если да, то делит n. Добавьте f в список.            п /= ж       # Разделите этот множитель на n.        еще:            # Но если f не является фактором n,            ж += 1       # Добавьте единицу к f и попробуйте снова.    возвращаться а             # Простые множители могут повторяться: от 12 множителей до 2,2,3.

Или в 2 раза эффективнее:

def trial_division(п: int) -> Список[int]:    а = []    пока п % 2 == 0:        а.добавить(2)        п /= 2    ж = 3    пока ж * ж <= п:        если п % ж == 0:            а.добавить(ж)            п /= ж        еще:            ж += 2    если п != 1: а.добавить(п)    # Возможно только нечетное число    возвращаться а

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

Ниже версия C ++ (без квадрата f)

шаблон <учебный класс Т, учебный класс U>вектор<Т> TrialDivision(U п){    вектор<Т> v; Т ж;    ж = 2;    пока (п % 2 == 0) { v.отталкивать(ж); п /= 2; }    ж = 3;    пока (п % 3 == 0) { v.отталкивать(ж); п /= 3; }    ж = 5;    Т ac = 9, темп = 16;    делать {        ac += темп; // Предположим, что добавление не вызывает переполнения с типом U        если (ac > п) перемена;         если (п % ж == 0) {            v.отталкивать(ж);            п /= ж;            ac -= темп;        }        еще {             ж += 2;            темп += 8;        }    } пока (1);    если (п != 1) v.отталкивать(п);    возвращаться v;}

Скорость

в худший случай, пробное деление - трудоемкий алгоритм. Для базы-2 п цифровой номер а, если он начинается с двух и работает только до квадратного корня из а, алгоритм требует

${\displaystyle \pi (2^{n/2})\approx {2^{n/2} \over \left({\frac {n}{2}}\right)\ln 2}}$

судебные подразделения, где ${\displaystyle \scriptstyle \pi (x)}$ обозначает функция подсчета простых чисел, количество простых чисел меньше Икс. Это не учитывает накладные расходы проверка на простоту чтобы получить простые числа в качестве возможных множителей. Полезная таблица не обязательно должна быть большой: P (3512) = 32749, последнее простое число, которое умещается в шестнадцатибитовое целое число со знаком, и P (6542) = 65521 для беззнаковых шестнадцатиразрядных целых чисел. Этого было бы достаточно, чтобы проверить простоту чисел до 65537² = 4 295 098 369. Подготовка такой таблицы (обычно через Сито Эратосфена ) будет иметь смысл только в том случае, если будет проверено много чисел. Если вместо этого используется вариант без проверки на простоту, а просто деление на каждое нечетное число меньше квадратного корня, основание-2 п цифровой номер а, премьер или нет, это может занять до:

${\displaystyle 2^{n/2}}$

В обоих случаях необходимое время растет экспоненциально с разрядами числа.

Тем не менее, это вполне удовлетворительный метод, учитывая, что даже самые известные алгоритмы имеют экспоненциальный рост во времени. За а выбранных равномерно случайным образом из целых чисел заданной длины, существует 50% -ная вероятность того, что 2 является фактором а и вероятность 33%, что 3 является фактором а, и так далее. Можно показать, что 88% всех положительных целых чисел имеют множитель меньше 100 и 92% имеют множитель меньше 1000. Таким образом, при столкновении с произвольно большим а, имеет смысл проверить делимость на малые простые числа, так как для ${\displaystyle a=1000}$, в базе-2 ${\displaystyle n=10}$.

Однако для многозначных чисел, не имеющих делителей в малых простых числах, могут потребоваться дни или месяцы, чтобы учесть пробное деление. В таких случаях используются другие методы, такие как квадратное сито и общее числовое поле сито (GNFS). Поскольку эти методы также имеют суперполиномиальное время роста, практический предел п цифр достигается очень быстро. По этой причине в криптография с открытым ключом, значения для а выбраны так, чтобы они имели большие простые множители одинакового размера, чтобы их нельзя было разложить на множители каким-либо общеизвестным методом за полезный период времени в любой доступной компьютерной системе или компьютерном кластере, таком как суперкомпьютеры и компьютерные сети. Наибольшее учтенное значение степени криптографии - РСА-250, 250-значное число, использующее GNFS и ресурсы нескольких суперкомпьютеров. Срок эксплуатации - 2700 основных лет.

Рекомендации

1. Моллин, Ричард А. (2002). «Краткая история факторинга и тестирования на простоту Б.С. (до компьютеров)». Математический журнал. 75 (1): 18–29. Дои:10.2307/3219180. МИСТЕР  2107288.

• Чайлдс, Линдси Н. (2009). Конкретное введение в высшую алгебру. Тексты для бакалавриата по математике (3-е изд.). Нью-Йорк, штат Нью-Йорк: Springer-Verlag. ISBN  978-0-387-74527-5. Zbl  1165.00002.
• Крэндалл, Ричард; Померанс, Карл (2005). Простые числа. Вычислительная перспектива (2-е изд.). Нью-Йорк, штат Нью-Йорк: Springer-Verlag. ISBN  0-387-25282-7. Zbl  1088.11001.

внешняя ссылка

• Быстрый калькулятор основного коэффициента JavaScript с использованием пробного деления. Может обрабатывать числа до 2⁵³
• Пробный отдел по Java, C и JavaScript (на португальском)