Почему факторинг больших целых чисел считается трудным?

17

Я прочитал где - то , что наиболее эффективный алгоритм найден можно вычислить факторы в O(exp((64/9b)1/3(logb)2/3) время, но код я написал это или возможно зависимости от того, насколько быстры деление и модуль. Я почти уверен, что где-то что-то неправильно понял, но я не уверен, где. Вот что я написал в форме псевдокода.O ( n log n )O(n)O(nlogn)

function factor(number) -> list
    factors = new list
    if number < 0
        factors.append(-1)
        number = -number
    i = 2
    while i <= number
        while number % i == 0
            factors.append(i)
            number /= i
        i++
    return factors
EnderShadow
источник
3
Гугл "псевдополином".
Рафаэль
Этот алгоритм на самом деле очень медленный - если число является простым числом, цикл повторяется (число) раз. Существует очень простой аргумент, который позволяет вам избежать итераций sqrt (число).
gnasher729

Ответы:

26

Вы путаете число с количеством битов, необходимых для представления n . Здесь b = количество битов, необходимых для представления n (поэтому b lg n ). Это имеет огромное значение. О ( п ) -time алгоритм является O ( 2 б ) -time алгоритм - экспоненциально зависит от числа битов. Для сравнения, «эффективный» алгоритм, который вы нашли, имеет время работы, которое является субэкспоненциальным в b .nnb=nblgnO(n)O(2b)b

Пример: Рассмотрим (2 млн). Тогда b = 21 бит достаточно для представления числа n . Таким образом, алгоритм , который является O ( 2 б 1 / 3 ) будет гораздо быстрее , чем алгоритм , который является O ( 2 б ) . O ( п ) алгоритм относится к последней категории, то есть, очень медленно.n=2,000,000b=21nO(2b1/3)O(2b)O(n)

Смотрите https://en.wikipedia.org/wiki/Integer_factorization

DW
источник
1
Я знал, что это было что-то простое.
EnderShadow
3
@EnderShadow: Кроме того, типы чисел, факторинг которых считается сложным с использованием имеющегося в настоящее время оборудования и используемых, например, в шифровании RSA, имеют (т.е. n > 2 000 ) или около того. В качестве упражнения, предполагая, что ваш компьютер может запускать ваш алгоритм O ( n ) со скоростью, скажем, один миллиард итераций в секунду, подсчитайте, сколько лет потребуется, чтобы фактор n 2 000 . (Если ваша первоначальная реакция «это не может быть правильно!», Вы, вероятно, рассчитали это правильно.)b>1,000n>21,000O(n)n21,000
Ильмари Каронен
1

у вас есть примерно два вопроса, общий и конкретный о вашем коде. конкретный обрабатывается в другом ответе. общий вопрос в заголовке о сложности факторинга очень глубокий. к сожалению, нет убедительных научных доказательств того, что факторинг находится за пределами P, за исключением (в основном косвенных) «многих экспертов, которые пытались потерпеть неудачу», и некоторые эксперты предполагают, что он находится внутри P; это рассматривается как одна из главных (и очень трудно решаемых) открытых проблем теории сложности. после десятилетий «тяжелой атаки» лучшие алгоритмы экспоненциальны. сложность факторинга является одной из «немногих исключительных проблем», которые, как известно, лежат «между» P и NP завершенными, но до сих пор не классифицировались как ни одна.

Как указывалось, сложность не была большой проблемой, пока она не стала использоваться («примерно») в криптосистемах RSA в середине 1980-х годов, где криптографическая безопасность зависит от предположения. (две другие «не совсем обнадеживающие» связанные точки данных: алгоритм Шорса для квантового факторинга P-времени и тестирование простоты был доказан в P в начале 2000-х годов в знаменитом / знаменитом алгоритме AKS .) Возможный положительный результат будет состоять в том, что это в квазиполиномиальном времени , которое слабее, чем NP Complete (при условии, что P ≠ NP и NP complete имеет экспоненциальное время нижней границы ), но все еще технически "трудно".

до сих пор не нашли большой обзор по этому ключевому вопросу. Однако см. также

ВЗН
источник
Еще один возможный, на первый взгляд, «крайний случай» сценарий состоит в том, что факторинг может быть в P, но все еще нет выполнимого алгоритма. ака галактические алгоритмы
взн
Следует упомянуть, что RSA является факторингом произведения двух больших простых чисел (где кто-то знает простые числа и просто их умножил, а кому-то еще дают продукт и он должен найти простые числа). Вполне возможно, что может существовать алгоритм, который может учитывать произведения двух больших простых чисел, но не произведения более двух больших простых чисел. Точно так же, как факторные числа, которые являются большими простыми числами (но заранее неизвестно, что они являются большими простыми числами), можно выполнить за полиномиальное время.
gnasher729