Оптимизация алгоритма факторизации простых чисел

Ниже приведен алгоритм, который находит простую факторизацию для заданного числа N. Мне интересно, есть ли способы сделать это быстрее, используя ОГРОМНЫЕ числа. Я говорю о 20-35-значных числах. Я хочу попытаться заставить их работать как можно быстрее. Любые идеи?

import time

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    divisor = 2        
    while n > 1:        
        while n % divisor == 0:
            factors.append(divisor)
            n /= divisor          
        divisor = divisor + 1
        if divisor*divisor > n:
            if n > 1: 
                factors.append(n)
            break
    return factors

#HUGE NUMBERS GO IN HERE!
start_time = time.time()
my_factors = prime_factors(15227063669158801)
end_time = time.time()
print my_factors
print "It took ", end_time-start_time, " seconds."

python optimization factorization
person Binka    schedule 03.04.2014    source источник
comment
Во сколько вы получаете указанный выше номер?   -  person sshashank124    schedule 03.04.2014
comment
Меньше секунды. Но для некоторых 20-значных чисел и выше это занимает более 30 секунд!   -  person Binka    schedule 03.04.2014
comment
вместо того, чтобы каждый раз увеличивать divisor на 1, вы можете вместо этого перебирать простые числа.   -  person desired login    schedule 03.04.2014
comment
stackoverflow.com/questions/12268526 /   -  person user1474424    schedule 03.04.2014
comment
Прежде всего, избегайте добавления. Это требует времени, потому что каждый раз, когда вы добавляете список, его приходится перераспределять в памяти, что требует времени. Это может быть решено путем предварительного выделения списка определенного размера (я полагаю, что сообщение выше касается этого) - вам нужно будет выяснить максимальные простые множители в числе. Кроме того, вместо увеличения делителя на единицу установите его на следующее простое число.   -  person Jacob Kudria    schedule 03.04.2014
comment
Хорошая идея, спасибо Яков.   -  person Binka    schedule 03.04.2014
comment
@JacobKudria: В большинстве случаев добавление к списку не требует изменения размера. Размер списка масштабируется таким образом, что добавление N элементов занимает общее время O(N). Предварительное выделение иногда может сэкономить время, но не сильно.   -  person user2357112 supports Monica    schedule 03.04.2014
comment
rosettacode.org/wiki/Prime_decomposition#Python   -  person Z boson    schedule 03.04.2014
comment
@ user2357112 Спасибо. Мне всегда говорили, что я должен предварительно выделить, но если это не сэкономит много времени, то...   -  person Jacob Kudria    schedule 03.04.2014

Ответы (4)


arrow_upward
1
arrow_downward

Ваш алгоритм представляет собой пробное деление, которое имеет временную сложность O (sqrt (n)). Вы можете улучшить свой алгоритм, используя только 2 и нечетные числа в качестве пробных делителей, или даже лучше, используя только простые числа в качестве пробных делителей, но временная сложность останется O(sqrt(n)).

Чтобы работать быстрее, вам нужен лучший алгоритм. Попробуй это:

def factor(n, c):
    f = lambda(x): (x*x+c) % n
    t, h, d = 2, 2, 1
    while d == 1:
        t = f(t); h = f(f(h)); d = gcd(t-h, n)
    if d == n:
        return factor(n, c+1)
    return d

Чтобы позвонить на свой номер, скажите

print factor(15227063669158801, 1)

Это возвращает (возможно, составной) коэффициент 2090327 практически мгновенно. Он использует алгоритм, называемый алгоритмом rho, изобретенным Джоном Поллардом в 1975 году. Алгоритм rho имеет временную сложность O(sqrt(sqrt(n))), поэтому он намного быстрее, чем пробное деление.

Существует множество других алгоритмов факторизации целых чисел. Для интересующих вас чисел в диапазоне от 20 до 35 цифр хорошо подходит алгоритм эллиптической кривой. Он должен факторизовать числа такого размера не более чем за несколько секунд. Другой алгоритм, который хорошо подходит для таких чисел, особенно полупростых (имеющих ровно два простых множителя), — это SQUFOF.

Если вас интересует программирование с использованием простых чисел, я скромно рекомендую это эссе в моем блоге. Когда вы закончите с этим, другие записи в моем блоге рассказывают о факторизации эллиптических кривых, SQUFOF и различных других, еще более мощных методах факторизации все больших целых чисел.

person user448810    schedule 04.04.2014
comment
Я думаю, что TD для простых чисел составляет ~ 2sqrt(n)/log(n). - person Will Ness; 06.04.2014
comment
Я думаю, вы правы, но в диапазоне n, где имеет смысл пробное деление, множитель log(n) не имеет большого значения, тем более, что вы получаете только половину от него, поэтому имеет смысл подумать о пробное деление как алгоритм O (sqrt (n)) независимо от того, как вы его реализуете (шансы, 2,3,5-колесо, простые числа). По крайней мере, я всегда так делаю. - person user448810; 07.04.2014
comment
эмпирически я получаю только половину от этой половины, но ускорение в 6,8 раз все еще заметно :) (TD-факторизация простых чисел против шансов, без учета генерации простых чисел). А для еще 1 цифры это 7,2x. Так что я думаю, что это немного лучше, чем sqrt(n). Гораздо лучше будет означать ускорение в тысячи или миллионы, конечно. Это означает, что я могу использовать TD еще примерно для двух цифр с простыми числами. -- (Кроме того, я попробовал ваш код с простым числом... :)) - person Will Ness; 07.04.2014
comment
@WIllNess: (относительно вашего комментария в скобках) Если вы попытаетесь разложить на множители простое число, вы заслуживаете того, что получите. - person user448810; 07.04.2014
comment
Но меня не предупредили!! :) :) - person Will Ness; 08.04.2014

arrow_upward
0
arrow_downward

Например, перечислите все простые факторизации для числа 100.

  • Проверьте, является ли 2 одной из факторизаций или нет. И тогда 2 ‹ 2*c ‹= 100 можно было бы удалить. Пр, 4, 6, 8, ... 98
  • Проверьте, является ли 3 одной из факторизаций или нет. И тогда 3 ‹ 2*d ‹= 100 можно было бы удалить. Пр, 9, 12, ... 99
  • 4 удален из возможного набора.
  • Отметьте 5, а затем 10, 15, 20, ..., 100 удаляются.
  • 6 удален.
  • Проверьте 7, .... ....
person AechoLiu    schedule 03.04.2014

arrow_upward
0
arrow_downward

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

person Lorientas    schedule 04.04.2014

arrow_upward
0
arrow_downward

Никакие оптимизации этого алгоритма не позволят вам факторизовать 35-значные числа, по крайней мере, в общем случае. Причина в том, что количество простых чисел до 35 цифр слишком велико, чтобы их можно было перечислить за разумное время, не говоря уже о попытке разделить на каждое из них. Даже если бы кто-то хотел попробовать, количество битов, необходимых для их хранения, также было бы слишком большим. В этом случае вам нужно выбрать другой алгоритм из списка алгоритмы факторизации общего назначения< /а>.

Однако, если все простые множители достаточно малы (скажем, меньше 10^12 или около того), вы можете использовать сегментированный Решето Эратосфена или просто найдите в Интернете список простых чисел до некоторого практического числа (скажем, 10^12 или около того) и используйте его вместо того, чтобы пытаться вычислить простые числа в надежде, что список достаточно велик.

person Nuclearman    schedule 04.04.2014