Пробное деление

редактировать

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

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

Содержание

1 Метод
2 Скорость
3 Ссылки
4 Внешние ссылки

Метод

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

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

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

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

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

def trial_division (n: int) ->List [int]: a = while n% 2 == 0: a.append (2) n / = 2 f = 3 while f * f <= n: if n % f == 0: a.append(f) n /= f else: f += 2 if n != 1: a.append(n) # Only odd number is possible return a

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

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

шаблон вектор TrialDivision (U n) {vector v; Т ф; f = 2; в то время как (п% 2 == 0) {v.push_back (f); п / = 2; } f = 3; в то время как (п% 3 == 0) {v.push_back (f); п / = 3; } f = 5; T ac = 9, temp = 16; сделать {ac + = temp; // Предположим, что сложение не вызывает переполнения с типом U if (ac>n) break; если (п% f == 0) {v.push_back (f); n / = f; ac - = темп; } else {f + = 2; темп + = 8; }} while (1); если (n! = 1) v.push_back (n); вернуть v; }

Скорость

В худшем случае пробное разделение является трудоемким алгоритмом. Для числа a с основанием 2 n, если оно начинается с двух и работает только до квадратного корня из a, алгоритм требует

π (2 n / 2) ≈ 2 n / 2 (n 2) ln ⁡ 2 {\ displaystyle \ pi (2 ^ {n / 2}) \ приблизительно {2 ^ {n / 2} \ over \ left ({\ frac {n} {2}} \ right) \ ln 2}}

\ pi (2 ^ {n / 2}) \ приблизительно {2 ^ {n / 2} \ over \ left ({\ frac {n } {2}} \ right) \ ln 2}

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

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

2 ^ {{n / 2}}

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

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

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

Ссылки

Чайлдс, Линдси Н. (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
Trial Division на Java, C и JavaScript (на португальском языке)