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

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

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

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

Answer 2

Я использовал метод 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 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 на п дает

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

р в Intervall

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

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

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

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