Факторизация больших чисел

Question

В классе мы нашли эту проблему программирования, и в настоящее время мы не знаем, как ее решить.

Дано положительное целое число n. Известно, что n = p * q, где p и q - простые числа, p<=q и |q-k*p|<10^5 для некоторого заданного положительного целого числа k. Вы должны найти p и q.

Введите:

35 1
121 1
1000730021 9

Выход:

5 * 7
11 * 11
10007 * 100003

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

Answer 1

Я использовал метод ECM для вычисления большого целого числа. Это один из самых эффективных известных алгоритмов. Если вы хотите узнать, как работает алгоритм, вам нужно много читать, но если вы хотите использовать его для своих исследований, некоторые люди его реализовали. Например, вы можете получить эти пакеты с открытым исходным кодом: GMP-ECM для C / C ++ или Pyecm для Python.

$ python
>>> import math
>>> import pyecm
>>> n = 1000730021
>>> list(pyecm.factors(n, False, False, 2 * math.log(math.log(n)), 1.0))
[10007, 100003]

Answer 2

Для чисел, размер которых вы здесь говорите, самый быстрый метод факторинга (вероятно) - использовать сито Эратосфена для генерации простых чисел примерно до квадратного корня числа, а затем использовать пробное деление на те, чтобы найти один (ые) являются делителями.

Для больших чисел было изобретено несколько методов факторинга. Вы можете использовать Google для «метода факторинга Ферма», «Полларда Ро», «метода Брента», «эллиптической кривой Ленстры», «многочленного квадратичного сита» и «сита поля общего числа». Я перечислил их в (примерно) порядке возрастания сложности и способности учитывать большие числа. Не ясно, стоит ли мне упоминать общее сито в поле чисел или нет - хотя это самый эффективный метод, который в настоящее время известен для вычисления очень больших чисел, он полезен только на действительно больших компьютерах - с разрешением менее 110 цифр или около того, MPQS это быстрее, но для учета больших чисел, когда GNFS быстрее, вам нужно гораздо больше памяти, чем может поддерживать обычный рабочий стол или сервер (терабайт ОЗУ следует рассматривать как минимальную отправную точку, но, вероятно, больше).

Answer 3

n = p * q 
|q-k*p|<10^5

с n и k задается как ввод. Поэтому

q-k*p=a 

с

-10^5<=a<=10^5

Умножение q-k*p=a на q и замена p*q на n дает

q^2-a*q-k*n=0

Решите это квадратное уравнение для каждого a с помощью

-10^5<=a<=10^5` 

и проверьте, делит ли q n. Решение квадратного уравнения может быть сделано за полиномиальное время, и это верно для решения 2*10^5+1 уравнения. Есть лучшие алгоритмы для небольших значений n и k, а также для больших значений n и k, конечно.

Как упоминал ypercube, нужно только проверить уравнения, где

a^2+4*k*n

это квадрат.

Answer 4

n = p * q и | q-k * p | <10 ^ 5 с n и k в качестве входных данных. Следовательно, q-k * p = a, с -10 ^ 5 <= a <= 10 ^ 5 Умножение q-k * p = a на q и подстановку p * q на n дает д ^ 2-а * д-к * п = 0. Решите это квадратное уравнение для каждого a с -10 ^ 5 <= a <= 10 ^ 5 и проверьте, делит ли q n. Решение квадратного уравнения может быть сделано за полиномиальное время, и это верно для решения уравнения 2 * 10 ^ 5 + 1. Есть лучшие алгоритмы для малых значений n и k </p>

в интервале

[(sqrt(k*n+2500000000)-50000)/k,(sqrt(k*n+2500000000)+50000)/k]

, поэтому вы должны проверять только значения 10 ^ 5 / k для p. д находится в промежутке

[sqrt(k*n+2500000000)-50000,sqrt(k*n+2500000000)+50000]

, который всегда содержит около 10 ^ 5 целых чисел