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

Question

Я занимаюсь проблемами 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

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

Может ли кто-нибудь объяснить?

Answer 1

В этом случае 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 итерации, пока есть p1 s в n.Таким образом, после завершения итерации (когда i = i + 1 выполняется), все вхождения p1 были удалены и:

n' = p2^n2 * p3^n3 

Давайте пропустить несколько итераций до тех пор, пока не достигнет ip3. Оставшийся 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, где наибольший простой коэффициент встречается только один раз, удаляя все остальные факторы. Для всех остальных номеров указанные исправления также должны заставить его работать.

Answer 2

Это устраняет все известные меньшие первичные коэффициенты от 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), случайно разделив на композицию с наибольшим простым.

Answer 3

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

Knuth and Trabb Pardo изучил поведение этой функции "Analysis of a Simple Factorization Algorithm" Теоретическая информатика 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)) в соответствии с одной моделью.