Факторизация рекуррентным методом

[Побережный Александр]

Проблема факторизации составного числа на простые множители до сих пор остается сложной и до конца не решенной.
Предлагаемый способ факторизации на связан с перебором простых чисел.

Обозначения.
$n=[\sqrt{N}]$, где []- целая часть числа N.
$R=(n+1)^2-N$
$R'=N-n^2$, причем $R+R'=2n+1$.

Пусть задано составное число $ N=pq$, где $1<p<q$. Число $N$ равно произведению ТОЛЬКО двух простых чисел $p$ и $q$.
Но число $N$ можно представить и так:
$N=(n-a)(n+a+2b)$

Если известно число $a$, то число $b$ однозначно определяется по формуле $b=\frac{R'+a^2}{2(n-a)}$
Если известно число $b$, то однозначно определяется число $a$ по формуле
$a=\sqrt{(n+b)^2-N}-b$

В качестве $ a_1=[\sqrt{(n+1)^2-N}]=[\sqrt{R}], b_1=[\frac{R'+a_1^2}{2(n-a_1)}]+1$.

Если $p-a_1$ не является делителем числа $N$, то запускаем цикл:
$a_i=[\sqrt{(n+b_{i-1})^2-N}-b_{i-1}]+1, b_i=[\frac{R'+a_i^2}{2(n-a_i)}]+1$.

Пример.
$407=11\cdot37=(20-9)(20+9+2\cdot4)$

$n=20$, $R'=407-20^2=7$, $R=(20+1)^2-407=34$

$a_1=[\sqrt{(20+1)^2-407}]=5$, $407$ не делится на $(20-5)$
$b_1=\frac{7+a_1^2}{2(n-a_1)}=\frac{7+5^2}{2(20-5)}\approx1.9$. Это не натуральное, значит $b_1=2$

$a_2=\sqrt{(20+b_1)^2-407}-b_1=\sqrt{(20+2)^2-407}-2\approx6,8$. Это не натуральное, значит $a_2=7$

Цикл повторяется, пока не получатся натуральные $a$ и $b$.
$b_2=\frac{7+7^2}{2(20-7)}\approx3.2$, следовательно $b_2=4$

$a_3=\sqrt{(20+4)^2-407}-4=9$ натуральное.
$b_3=\frac{7+9^2}{2(20-9)}=4$ натуральное.

$N=407=(20-9)(20+9+2\cdot4)=11\cdot37$

Этот метод удобный тем, что не надо проверять на простоту числа.

[Someone]

А чем этот метод лучше хорошо известного метода Ферма? И не есть ли это просто метод Ферма, только немного замаскированный?

[Побережный Александр]

Это и есть метод Ферма, но оптимизированный. Не нужно перебирать подряд все значения. Проскакивая заведомо неприемлемые значения, останавливаемся и проверяем выполнение условий на определяющих числах.
Кстати, поскольку числа $a$ и $b$ должны одновременно оказаться натуральными, процесс факторизации можно свести к рекуррентной формуле вида $a_{i+1}=f(a_i)$, где функция $f(x)$ достаточно объемная в записи.

На счет эффективности у меня нет предположений, но мне кажется все же лучше простого метода Ферма.

[Someone]

Побережный Александр в сообщении #1400171 писал(а):

На счет эффективности у меня нет предположений, но мне кажется все же лучше простого метода Ферма.

Похоже, что лучше. Вы бы поэкспериментировали с числами. Не с трёхзначными, конечно, а так примерно десятизначными и больше. И посмотрите вот это: https://eprint.iacr.org/2009/318.pdf.

[Someone]

Побережный Александр
Прокрутите, пожалуйста, ваш алгоритм для числа $4\,299\,802\,453=65\,447\times 65\,699$. У меня не получилось. То ли в алгоритме ошибка, то ли я что-то не понял. Может быть, начальное значение не совсем правильно выбирается. Может быть, что-нибудь другое.

[Побережный Александр]

Побережный Александр в сообщении #1399635 писал(а):

Обозначения.
$n=[\sqrt{N}]$, где []- целая часть числа N.
$R=(n+1)^2-N$
$R'=N-n^2$, причем $R+R'=2n+1$.

Величина $R$ не должна быть полным квадратом. Иначе число $N$ можно сразу расписать как разность квадратов.
Я посчитал этот случай тривиальным. Но это надо было указать в условиях. Приношу свои извинения.

[Someone]

Побережный Александр
Чуть-чуть поэкспериментировал с вашим алгоритмом.
Пусть $N=9\,999\,128\,429\times 10\,000\,425\,181=99\,995\,535\,729\,424\,570\,649$.
Тогда $n=\bigl[\sqrt{N}\,\bigr]=9\,999\,776\,783$, $p=n-a=9\,999\,128\,429$, $q=n+a+2b=10\,000\,425\,181$, откуда $a=648\,354$ и $b=22$.
По вашим формулам определяем $R=(n+1)^2-N=400\,812\,007$, $R'=N-n^2=19\,598\,741\,560$, $a_1=\bigl[\sqrt{R}\,\bigr]=20\,020$, $b_1=\left[\frac{R'+a_1^2}{2(n-a_1)}\right]+1=2$.
Дальнейшие вычисления протекают так:
\begin{tabular}{r|r|r} $i$&$a_i$&$b_i$\\ \hline\hline $1$&$20\,020$&$2$\\ $2$&$142\,828$&$3$\\ $3$&$200\,995$&$4$\\ $4$&$245\,760$&$5$\\ $5$&$283\,543$&$6$\\ $6$&$316\,852$&$7$\\ $7$&$346\,978$&$8$\\ $8$&$374\,689$&$9$\\ $9$&$400\,488$&$10$\\ $10$&$424\,722$&$11$\\ $11$&$447\,646$&$12$\\ $12$&$469\,452$&$13$\\ $13$&$490\,289$&$14$\\ $14$&$510\,276$&$15$\\ $15$&$529\,508$&$16$\\ $16$&$548\,067$&$17$\\ $17$&$566\,017$&$18$\\ $18$&$583\,415$&$19$\\ $19$&$600\,309$&$20$\\ $20$&$616\,740$&$21$\\ $21$&$632\,745$&$22$\\ $22$&$648\,355$&$23$\\ $23$&$663\,597$&$24$ \end{tabular}
Как видите, правильные значения $a$ и $b$ "перепрыгиваются" на $22$-м шаге.

[Побережный Александр]

У вас на 22 шаге ошибка. $a_{22}=648354$.
Я пересчитал с 21 шага и у меня все красиво получилось.

[dmd]

У меня также на 22 шаге перепрыгивает. Но даже если добавить на выход из цикла соответствующую поправку, то для чуть большего N=99995535729424570673*77696531261762891394341 уже дождаться результата не возможно, а pari/gp его раскладывает за пол-секунды.

(код)

alp()=
{
 N= 99995535729424570673*77696531261762891394341;
\\ N= 9999128429*10000425181;
 n= sqrtint(N);
 R= (n+1)^2-N; Rs= N-n^2;
 a= sqrtint(R); b= floor((Rs+a^2)/(n-a)/2)+1;
 while(1,
  a= floor(sqrt((n+b)^2-N)-b)+1; p= n-a;
  b= floor((Rs+a^2)/p/2)+1;
  \\print(a"    "b);
  if(gcd(p,N)>1, print(p"    "N/p); break());
  if(gcd(p+1,N)>1, print(p+1"    "N/(p+1)); break());
  if(gcd(p-1,N)>1, print(p-1"    "N/(p-1)); break());
 );
 print(b)
};

[Someone]

Побережный Александр в сообщении #1401361 писал(а):

У вас на 22 шаге ошибка. $a_{22}=648354$.
Я пересчитал с 21 шага и у меня все красиво получилось.

Я, конечно, догадываюсь, что Вы считали "руками", вычислили корень, обрадовались, что он целый, да ещё имеет правильное значение, на радостях единицу прибавлять не стали, и получили, что хотели. Но в алгоритме у Вас написано, что прибавлять единицу надо. Поэтому "руками" Вы правильный результат получаете, а компьютер — нет. Я же Вам советовал поэкспериментировать с бо́льшими числами. У Вас что, никакой системы компьютерной математики нет? Excel не в счёт.
При этом с меньшими числами у меня всё хорошо было, и с этим тоже надо разобраться. Сейчас мне некогда, может быть, вечером выберу несколько часов.

Замечание. Вы используете функцию "целая часть", которая есть "округление вниз до ближайшего целого", а Вам, судя по всему, нужно "округление вверх до ближайшего целого", которое обозначается $\lceil x\rceil$.

[Dmitriy40]

Побережный Александр в сообщении #1401361 писал(а):

У вас на 22 шаге ошибка. $a_{22}=648354$.
Я пересчитал с 21 шага и у меня все красиво получилось.

Нет, ошибка у Вас в алгоритме/формулах: надо не брать целую часть от выражений и добавлять к ней единицу, а округлять вверх, вот тогда и получится $648354$ вместо $648355$.
Как это повлияет на $b_i$ не берусь судить, но думаю там возможна та же проблема.

dmd в сообщении #1401404 писал(а):

то для чуть большего N=99995535729424570673*77696531261762891394341 уже дождаться результата не возможно,

Потому что числа сильно отличаются от $\sqrt{N}$. Вообще когда $p \ll q$, то работать будет очень долго. Например даже для N=101*907 надо более 120 итераций.
Очень уж подозрительно выглядит почти линейное возрастание $b_i$, напрашивается какой-то метод более быстрого изменения $b_i$, с вычислением по ним $a_i$, нахождения максимального значения $a_i$ и потом его уточнение делением пополам (по $b_i$).

PS. Вместо gcd(p,N)>1 логичнее использовать N%p==0, думаю так быстрее.

-- 25.06.2019, 12:39 --

Dmitriy40 в сообщении #1401415 писал(а):

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

Собственно максимально возможное значение $a_i$ известно: $a_{max}=n-2$, соответственно $b_{max}=(R'+a_{max}^2)/4$. Вот в этих пределах и искать правильное значение $b_i$ и соответственно $a_i$.

-- 25.06.2019, 14:32 --

Судя по всему, при относительно близких $p$ и $q$ (даже при 20% различии), $b_i$ будет последовательными числами и метод ничем не лучше метода Ферма. При большом отличии сомножителей будет некоторое ускорение за счёт пропуска некоторых $b_i$, раза в 2-3-4, что при наличии других улучшений метода Ферма (см. хоть рувики) большого интереса не вызывает.

[Someone]

Задано натуральное число $N$, которое при делении на $4$ даёт остаток, отличный от $2$. Два следующих алгоритма находят натуральные числа $p$ и $q$, удовлетворяющие условиям $p\leq q$ и $N=pq$, с наименьшей возможной разностью $q-p$.
Количество шагов в методе Фурье равно $\frac{p+q}2-\bigl\lfloor\sqrt{N}\bigr\rfloor$. Модифицированный алгоритм может выполнять меньшее число шагов, но не обязательно будет быстрее, так как каждый шаг сложнее и требует больше времени.
Переменная $k$ является счётчиком шагов (фактическое число шагов равно $k+1$). Эта переменная полезна для досрочного окончания работы программы.

Обычно рекомендуется прогонять алгоритм не только для числа $N$, но и для ряда чисел вида $KN$, где значения $K$ выбираются так, чтобы остаток от деления $KN$ на $4$ отличался от $2$. Если удастся подобрать такое $K$, чтобы $KN$ было произведением двух достаточно близких множителей, то метод Фурье может найти их существенно быстрее.

Алгоритм метода Фурье.
1) Начальные значения: $k\leftarrow 0$, $s\leftarrow\bigl\lceil\sqrt{N}\,\bigr\rceil$.
2) Вычислить $x\leftarrow s+k$, $y=\sqrt{x^2-N}$, $k\leftarrow k+1$. Если число $y$ не целое, повторить пункт 2).
3) Вычислить $p\leftarrow x-y$, $q\leftarrow x+y$. Закончить работу.

Алгоритм модифицированного метода Фурье, который предлагает Побережный Александр.
1) Присвоить $n\leftarrow\bigl\lfloor\sqrt{N}\bigr\rfloor$ и $k\leftarrow 0$. Если $n^2=N$, то присвоить $p\leftarrow q\leftarrow n$ и закончить работу.
2) Вычислить $R\leftarrow(n+1)^2-N$ и $R'\leftarrow N-n^2$.
3) Начальное значение: $a\leftarrow\bigl\lfloor\sqrt{R}\bigr\rfloor$; если $a^2=R$, то присвоить $a\leftarrow a-1$.
4) Начальное значение: $b\leftarrow\left\lceil\frac{R'+a^2}{2(n-a)}\right\rceil$.
5) Если число $\frac N{n-a}$ целое, перейти в пункт 7).
6) Вычислить $a\leftarrow\bigl\lceil\sqrt{(n+b)^2-N}-b\bigl\rceil$, $b\leftarrow\left\lceil\frac{R'+a^2}{2(n-a)}\right\rceil$, $k\leftarrow k+1$ и перейти в пункт 5).
7) Вычислить $p\leftarrow n-a$, $q\leftarrow n+a+2b$. Закончить работу.

Примеры. Windows 7. Wolfram Mathematica 9.0. Четырёхъядерный процессор Intel(R) Xeon(R) X3320 2.50GHz. Время работы — в секундах.
{\begin{tabular}{|r|r|r|r|r|r|r|r|} \hline \multicolumn{8}{|c|}{Метод Ферма}\\ \hline \multicolumn{1}{|c|}{\textnumero}&\multicolumn{1}{|c|}{$N$}&\multicolumn{1}{c|}{Шаги}&\multicolumn{1}{c|}{Время (с)}&\multicolumn{1}{c|}{$x$}&\multicolumn{1}{c|}{$y$}&\multicolumn{1}{c|}{$p$}&\multicolumn{1}{c|}{$q$}\\ \hline $1.$&$4\,294\,967\,317$&$605\,275$&$51{,}417\,930$&$670\,811$&$667\,602$&$3\,209$&$1\,338\,413$\\ $2.$&$4\,294\,967\,321$&$2\,864\,549$&$373{,}544\,395$&$2\,930\,085$&$2\,929\,352$&$733$&$5\,859\,437$\\ $3.$&$100\,895\,598\,169$&$187\,723$&$10{,}795\,269$&$505\,363$&$393\,060$&$112\,303$&$898\,423$\\ $4.$&$3\times 100\,895\,598\,169$&$67\,497$&$4{,}383\,628$&$617\,666$&$280\,757$&$336\,909$&$898\,423$\\ $5.$&$4\times 100\,895\,598\,169$&$375\,445$&$29{,}718\,190$&$1\,010\,726$&$786\,120$&$224\,606$&$1\,796\,846$\\ $6.$&$5\times 100\,895\,598\,169$&$19\,703$&$1{,}092\,007$&$729\,969$&$168\,454$&$561\,515$&$898\,423$\\ $7.$&$7\times 100\,895\,598\,169$&$1\,874$&$0{,}046\,800$&$842\,272$&$56\,151$&$786\,121$&$898\,423$\\ $8.$&$8\times 100\,895\,598\,169$&$224\,606$&$23{,}587\,351$&$1\,123\,029$&$673\,817$&$449\,212$&$1\,796\,846$\\ \hline\hline \multicolumn{8}{|c|}{Метод Побережного}\\ \hline \multicolumn{1}{|c|}{\textnumero}&\multicolumn{1}{|c|}{$N$}&\multicolumn{1}{c|}{Шаги}&\multicolumn{1}{c|}{Время (с)}&\multicolumn{1}{c|}{$a$}&\multicolumn{1}{c|}{$b$}&\multicolumn{1}{c|}{$p$}&\multicolumn{1}{c|}{$q$}\\ \hline $1.$&$4\,294\,967\,317$&$44\,766$&$5{,}241\,634$&$62\,327$&$605\,275$&$3\,209$&$1\,338\,413$\\ $2.$&$4\,294\,967\,321$&$47\,242$&$5{,}772\,037$&$64\,803$&$2\,864\,549$&$733$&$5\,859\,437$\\ $3.$&$100\,895\,598\,169$&$120\,226$&$15{,}147\,697$&$205\,337$&$187\,723$&$112\,303$&$898\,423$\\ $4.$&$3\times 100\,895\,598\,169$&$67\,497$&$8{,}486\,454$&$213\,260$&$67\,497$&$336\,909$&$898\,423$\\ $5.$&$4\times 100\,895\,598\,169$&$240\,452$&$35{,}318\,626$&$410\,675$&$375\,445$&$224\,606$&$1\,796\,846$\\ $6.$&$5\times 100\,895\,598\,169$&$19\,703$&$2{,}449\,216$&$148\,751$&$19\,703$&$561\,515$&$898\,423$\\ $7.$&$7\times 100\,895\,598\,169$&$1\,874$&$0{,}156\,001$&$54\,277$&$1\,874$&$786\,121$&$898\,423$\\ $8.$&$8\times 100\,895\,598\,169$&$208\,480$&$36{,}426\,234$&$449\,211$&$224\,606$&$449\,212$&$1\,796\,846$\\ \hline \end{tabular}}
Пример 9. В таблицу не влезает.
$N=99\,000\,000\,001\,999\,999\,999=9\,000\,000\,001\times 10\,999\,999\,999$
Число шагов в обоих алгоритмах одинаковое: $50\,125\,629$.
Метод Ферма: время работы равно $12\,326{,}200\,614$ с, $x=10\,000\,000\,000$, $y=999\,999\,999$.
Метод Побережного: время работы равно $15\,791{,}294\,826$ с, $a=949\,874\,370$, $b=50\,125\,629$.

В общем, обсуждаемый метод может быть существенно эффективнее первоначального метода Фурье, если числа $p$ и $q$ сильно различаются, и хватит терпения дождаться результата. Может быть, автору следует подумать над тем, чтобы запустить метод в обратном направлении. В поиске сильно различающихся делителей он может быть эффективным.
Насколько этот метод новый — понятия не имею.

[Побережный Александр]

Уважаемый Someone, спасибо за замечательный анализ метода рекуррентной факторизации!
Ваша идея запустить метод в обратном направлении неожиданная для меня, на задумывался об этом. Сейчас попробую поразмышлять и в таком варианте.
Для близких $p$ и $q$ алгоритм можно ускорить, как мне кажется. Все-таки по сравнению с методом Ферма алгоритм достаточно громоздкий. За счет этого и времени уходит больше при одинаковом количестве шагов.

[Dmitriy40]

Вот бы сделать несколько тысяч итераций методом Ферма, а потом продолжить этим ... Конкретный порог переключения можно поискать, главное чтобы получилось продолжить.

[Побережный Александр]

Dmitriy40, это можно всегда сделать, если иметь в виду, что
$x=n+b$,
$y=a+b$.
Начинаем методом Ферма, останавливаемся на определенном шаге с известными $x$ и $y$.
Далее вычисляем соответственно $a$ и $b$, которые будут начальными значениями в рекуррентном методе и продолжаем вычислять уже рекуррентным методом.
Можно и обратно перейти соответственно.
Только мне кажется метод Ферма оптимально применять тогда, когда $b$ меняется с шагом 1.