Быстрая факторизация произведения двух близких чисел

[B@R5uk]

В связи с моими недавними попытками вычислить первые $\pi(2^N)$ простых чисел меня вдруг дико заинтересовал такой вопрос. Существует ли быстрый способ факторизации произведения двух близких сомножителей? Естественно, наиболее интересен случай, когда оба сомножителя — простые числа. Хотелось бы, чтобы факторизация была не перебором в лоб близких множителей, а что-то более осмысленное, типа вычисление рекуррентной последовательности, которая бы быстро сходилась к одному из сомножителей. Или это может быть система из двух последовательностей для каждого из сомножителей. То есть, если есть, например, число 929140878275708723, то можно ли за 10-20 итераций найти его делители?

Попытки нагуглить чего-нибудь ничего не дали. Я даже без понятия какие ключевые слова гуглить. Задаю вопрос именно в этом разделе, потому что не смотря на то, что гипотетический способ факторизации имеет самое непосредственно программное приложение, это всё-таки, на мой взгляд, математическая задача.

[vpb]

Решето Померанца погуглите.

[Dmitriy40]

Сами значения $\pi(2^n)$ есть в A007053, можно сверяться.
И для столь близких делителей метод факторизации Ферма может быть проще и быстрее.

[B@R5uk]

Dmitriy40, спасибо! Метод факторизации Ферма — это как раз то, про что я спрашивал. Кроме того, так или иначе он является прародителем большинства (если не всех) современных методов быстрой факторизации.

Если я правильно понял, метод Ферма заключается в следующем. Имеется нечётное число $N=ab$, являющееся произведение двух неизвестных сомножителей a и b. Чтобы их найти мы пытаемся представить это число в виде разности квадратов $N=x^2-y^2$ двух целых чисел, чтобы воспользоваться формулой разности квадратов. Для этого мы берём в качестве x число $R=\lceil\sqrt{N}\rceil$ и все следующие за ним ($x=R+k$, $k\ge 0$), поставляем в формулу и находим y, до тех пор, пока y не окажется целым числом.

Я тут поковырялся с формулами, и мне кажется их удобно привести к такому виду:
$R^2=N+r$
$0<r\le 2R-2$
$y^2=x^2-N=(R+k)^2-N=k^2+2Rk+r$
$y=\sqrt{k^2+2Rk+r}$
На каждой итерации приходится вычислять квадратный корень, но если искомые сомножители близки, то этих итераций будет, как показывает практика, очень мало.

Далее, меня заинтересовало, на каком приблизительно k закончится поиск в зависимости от величины N. Получились такие выкладки:
$y=\frac{b-a}{2}=\sqrt{{{k}^{2}}+2Rk+r}$
${{k}^{2}}+2Rk+r=\frac{{{\left( b-a \right)}^{2}}}{4}$
${{k}^{2}}+2\left\lceil \sqrt{ab} \right\rceil k+{{\left\lceil \sqrt{ab} \right\rceil }^{2}}-ab=\frac{{{\left( b-a \right)}^{2}}}{4}$
$k+\left\lceil \sqrt{ab} \right\rceil =\frac{a+b}{2}$
$\left\lceil \sqrt{ab} \right\rceil =\sqrt{ab}+\varepsilon$
$k=\frac{a+b}{2}-\sqrt{ab}-\varepsilon =\frac{{{\left( \sqrt{b}-\sqrt{a} \right)}^{2}}}{2}-\varepsilon$
$k=\left\lfloor \frac{{{\left( \sqrt{b}-\sqrt{a} \right)}^{2}}}{2} \right\rfloor$
Эта формула для $k$ точная. Однако, сомножители заранее неизвестны, поэтому приходится перебирать все возможные значения от нуля. Видно, так же, что если сомножители близки, то перебирать придётся значительно меньше вариантов. Чтобы понять на столько меньше положим, что $b/a=\gamma=1+\alpha$. Тогда:
$a=\sqrt{{N}/{\gamma }}$
$b=\sqrt{\gamma N}$
$k=\left\lfloor \frac{1}{2}{{\left( {{\gamma }^{{1}/{4}\;}}-{{\gamma }^{-{1}/{4}\;}} \right)}^{2}}\sqrt{N} \right\rfloor$
$k\approx \frac{{{\alpha }^{2}}}{8}\sqrt{N}$

Но что мне показалось особенно забавным в методе Ферма, так это оптимизация множителем! Если $\gamma$ сильно отличается от единицы, но его приблизительное значение известно, то можно подобрать такие два числа c и d, чтобы $c\gamma/d\approx 1$. Тогда домножив факторизуемое число N на произведение этих новых чисел получим: $Ncd=abcd=ad\cdot cb$, где $ad/(cb)\approx 1$. Разложение нового числа на новые множители за счёт их близости произойдёт гораздо быстрее, несмотря на его большую величину нового факторизуемого числа.

Например, если известно, что $\gamma\approx 2$ (при этом $k\approx 0,06\sqrt{N}$), то за счёт умножения исходного числа на $465=15\cdot 31$ получим $\gamma'\approx 2\cdot 15/31\approx 1-0,032$ и $k'\approx 0,003\sqrt{N}$, то есть ускорение в 20 раз. Сложность алгоритма, правда, остаётся всё той же: $O(\sqrt{N})$.

Если б только был волшебный способ оценить $\gamma$ по N не находя a и b!