Что делает эту простую факторизацию такой эффективной?

Я решал некоторые задачи Project Euler, чтобы изучить/попрактиковаться в Lua, и мой первоначальный быстрый и грязный способ нахождения наибольшего простого множителя n был довольно плохим, поэтому я посмотрел код, чтобы посмотреть, как это делают другие (в попытки понять различные методологии факторинга).

Я наткнулся на следующее (изначально на Python — это мой Lua):

function Main()
    local n = 102
    local i = 2
    while i^2 < n do
        while n%i==0 do n = n / i end
        i = i+1
    end
    print(n)
end

Это привело к огромному количеству пользователей за очень короткое время — почти мгновенно. Вещь, которую я заметил в алгоритме, которую я бы не угадал:

  • n = n / i

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

Кто-нибудь может объяснить?


algorithm prime-factoring
person galois    schedule 27.07.2015    source источник
comment
Попробуйте это с большим простым числом, таким как n = 10 ^ 18 + 3. Алгоритм по-прежнему O (sqrt (n)), когда доступны гораздо более эффективные алгоритмы факторизации.   -  person Niklas B.    schedule 27.07.2015
comment
Довольно простым является алгоритм Ро Полларда с ожидаемой сложностью O (n ^ (1/4))   -  person Niklas B.    schedule 27.07.2015

Ответы (3)


arrow_upward
3
arrow_downward

В этом случае i является кандидатом на первичный фактор. Учтите, что n состоит из следующих простых чисел:

n = p1^n1 * p2^n2 * p3^n3

Когда i достигает p1, оператор n = n / i = n / p1 удаляет одно вхождение p1:

n / p1 = p1^(n-1) * p2^n2 * p3^n3

Внутренний while повторяется до тех пор, пока в n есть p1. Таким образом, после завершения итерации (когда выполняется i = i + 1) все вхождения p1 удаляются и:

n' =  p2^n2 * p3^n3

Пропустим несколько итераций, пока i не достигнет p3. Оставшееся n тогда:

n'' = p3^n3

Здесь мы находим первую ошибку в коде. Если n3 равно 2, то внешнее условие не выполняется, и мы остаемся с p3^2. Должно быть while i^2 <= n.

Как и прежде, внутренний while удаляет все вхождения p3, оставляя нам n'''=1. Это вторая ошибка. Это должно быть while n%i==0 and n>i (не уверен в синтаксисе LUA), что сохраняет самое последнее вхождение.

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

person Nico Schertler    schedule 27.07.2015

arrow_upward
0
arrow_downward

Это устраняет все известные меньшие простые множители от n, так что n становится меньше, а sqrt(n) может быть достигнуто раньше. Это дает прирост производительности, так как вам больше не нужно запускать числа для квадратного корня из исходного N, скажем, если n равно миллиону, оно состоит из 2 и 5, и наивный запрос ко всем известным простым числам должен был бы проверяться против всех простых чисел. до 1000, а деление на 2 дает 15625, затем деление на 5 дает 1 (кстати, ваш алгоритм вернет 1! Чтобы исправить, если ваш цикл завершается с n=1, вместо этого верните i .) эффективное разложение большого числа на множители в два этапа. Но это допустимо только с «обычными» числами, которые имеют один высокий простой знаменатель и множество меньших, но разложение на множители числа n=p*q, где и p, и q являются простыми и близкими, не сможет извлечь выгоду из этого увеличения. .

Строка n=n/i работает, потому что, если вы ищете другое простое число, кроме i, вы в настоящее время найдены как делитель, результат также делится на это простое число по определению простых чисел. Читайте здесь: https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic. Кроме того, это работает только в вашем случае, потому что ваш i начинается с 2 и выше, так что вы сначала делите на простые числа, а затем на их составные части. В противном случае, если ваше число будет иметь 3 в качестве наибольшего простого числа, а также делится на 2, и вы сначала проверите против 6, вы испортите принцип деления только на простые числа (скажем, с 72, если вы сначала разделите на 6, вы получите 2, а ответ 3) путем случайного деления на составную часть наибольшего простого числа.

person Vesper    schedule 27.07.2015

arrow_upward
0
arrow_downward

Этот алгоритм (после исправления) требует O(max(p2,sqrt(p1))) шагов, чтобы найти разложение числа n на простые множители, где p1 — самый большой простой множитель, а p2 — второй по величине простой множитель. В случае повторяющегося наибольшего простого множителя p1=p2.

Кнут и Трэбб Пардо изучили поведение этой функции "Анализ простого алгоритма факторизации" Теоретическая информатика 3 (1976) 321-348. Они возражали против обычного анализа, такого как вычисление среднего количества шагов, предпринятых при факторизации целых чисел до n. Хотя несколько чисел с большими простыми множителями повышают среднее значение, в криптографическом контексте может быть более важным то, что некоторые процентили довольно низкие. Например, 44,7 % чисел удовлетворяют max(sqrt(p1),p2)<n^(1/3), а 1,2 % чисел удовлетворяют max(sqrt(p1),p2)<n^(1/5).

Простое улучшение состоит в том, чтобы проверить остаток на простоту после того, как вы найдете новый простой множитель. Очень быстро проверить, является ли число простым. Это сокращает время до O(p2), избегая пробных делений между p2 и sqrt(p1). Средний размер второго по величине простого числа составляет около n ^ 0,21. Это означает, что можно быстро (за несколько процессорных секунд) разложить на множители многие 45-значные числа, используя это улучшение пробного деления. Для сравнения, согласно одной модели, факторизация Полларда-ро произведения двух простых чисел занимает в среднем O(sqrt(p2)) шагов.

person Douglas Zare    schedule 27.07.2015