Эффективно простое факторизация целого числа с oracle

Question

Предположим, у вас есть программа one_factor(N), которая, учитывая двоичное число n -di git, N, возвращает один из главных факторов числа за Theta(n^2) время (обратите внимание, что я использовал строчная n в моей тета-записи.)

Используя этот алгоритм, я хочу найти эффективный алгоритм для деления двоичного числа n -di git на простые числа и вывода простых чисел. Кроме того, я хочу знать, насколько быстро алгоритм работает как функция n, и я также хочу вычислить приблизительное число раз, когда мой алгоритм использует one_factor(N) oracle в худшем случае как функцию n.

Предположим, что требуется Theta(n) время, чтобы сложить / разделить / умножить / вычесть два n -di git двоичных чисел.

---

Вот алгоритм, который работает :

• Звоните one_factor(N). Если функция возвращает N, то N является простым, и мы закончили. В противном случае разделите этот главный фактор и сохраните его где-нибудь. Повторяйте эту процедуру, пока мы не закончим.

Теперь у меня возникают проблемы с анализом времени выполнения этой процедуры как функции n. Для простоты, если N - это степень двойки, то n = log_2(N), но я не совсем уверен, как действовать дальше.

Я не понимаю, как найти число наихудших случаев, когда мы звоним one_factor, и у меня возникают проблемы с анализом времени выполнения наихудшего случая.

Answer 1

Во-первых, oracle замечательно, но медленно. Итак, вы хотите сначала попытаться выполнить пробное деление.

Из Арифметические c функции в Википедии , если вы используете деление Ньютона-Рафсона и алгоритм Харви-Хувена, проверяя, равномерно ли вы делится на простое число p, может быть сделано за время O(n log(n)). Вычисление простых чисел O(n / log(n)) до n выполнимо при сите с эратосфеновым временем, значительно меньшим O(n^2). Выполнение пробных делений можно сделать вовремя O(n^2). (Используя более практичные алгоритмы умножения, вы можете сделать это в несколько худшее время. Это не повлияет на общий результат.)

Теперь вы обращаетесь к вашему oracle. Каждый oracle занимает время O(n^2), и деление невелико по сравнению с этим. Уменьшает размер числа как минимум в n. Как деления нужны? O(log_n(2^n)) = O(log(2^n)/log(n)) = O(n/log(n)). И каждое деление равно O(n log(n)) по тому же алгоритму, что и выше.

Полученный алгоритм равен O(n^2 * (n * log(n)) * n/log(n)) = O(n^4). Обратите внимание, что /log(n) - это экономия от пробного деления до обращения к oracle.

Обратите внимание, что вы не можете улучшить это, выполнив большее количество пробных делений, потому что если вы попытаетесь go через все простые числа до n^2 вы потратили больше времени на пробное деление, чем ваш исходный алгоритм, а биг-О части oracle деления остается прежней.

Answer 2

Обратите внимание, что после деления ваш номер N становится N / 2 или меньше. Таким образом, вам потребуется максимум log2 (N) oracle вызовов. Это O (n). Каждый вызов занимает O (n²) времени или меньше («меньше» может быть необходимо упомянуть в зависимости от вашего определения O).

Если ваш N является степенью 2, он реализует наихудший случай числа вызовы. К счастью, он также понимает наихудший случай времени выполнения при каждом вызове, потому что в первой половине из них число достаточно велико - оно имеет не менее n / 2 цифр.