Факторизация

[Sonic86]

Andrey A в сообщении #1122038 писал(а):

2. Если для составного $m$ брать $a_1\equiv 2^t+\dfrac{1}{2^t}\mod m$, то при достаточно большом $t$ быстро находится $a_n\equiv a_1 \mod m'$ как в $\rho$-методе Полларда. Я глубоко не вникал, но там, кажется, функция $a^2-2$ как раз исключена. Хоть похож на Монте-Карло, только всё ж не Монте-Карло. При $t=\left \lceil \dfrac{\ln \ln m}{\ln 2}+0,5288 \right \rceil$ вроде бы $a_1$ всегда попадает в период. Количество проверок при таком подходе на порядок меньше, но находятся, конечно, "плохие числа", в частности квазипростые Мерсена.

Если же отслеживать начало периода при произвольном $a_1$, то появляются иные возможности. Для $m=2047=2^{11}-1$, к примеру, $2^{16}\mod 2047=32;\ \dfrac{1}{32}\mod 2047=64;\ 64+32=96$. Из периода $(96,-1021,516,144,264)$ информации о делимости $2047$ не извлечь, но при $a_1=3$ имеем $3,7,47,(160,-1013,620,-438,-576)$, откуда $(-576)^2-2\equiv 160\equiv 47^2-2$ и $576^2\equiv 47^2$. В узелке $\rho$-петли содержится пара сравнимых по модулю нетривиальных квадратов, о чем упоминания не встречал. Как бы довести всё это до совершенства?

Оценки асимптотики у Вас нет, правильно я понимаю?
Вообще, Вас все это интересует в плане эффективной факторизации, правильно?

Я тут почитал Вику (https://ru.wikipedia.org/wiki/%D0%A0%D0 ... 0%B4%D0%B0), Германа с Нестеренко и статью http://www.cs.cmu.edu/~avrim/451f11/lec ... ollard.pdf
Оценки там такие: если $p\mid m$, то $p=O(\sqrt{m})$ и вдобавок для последовательности $x_n$ длина предпериода $\lambda=O(\sqrt{p})$ и длина периода $\tau=O(\sqrt{p})$ тоже, что в итоге дает время работы $O(\sqrt{\sqrt{p}+\sqrt{p}+O(\ln ^k p)})=O(\sqrt[4]{m})$. С оценкой предпериода они не заморачиваются - видимо, проблема не в ней. Легко может оказаться, что предпериоды и так сильно короче.
Оценка $\tau=O(\sqrt{p})$ - вероятностная, похожая на оценку в парадоксе дня рождений (есть и в Нестеренко, и в Вики).
(причем по ссылка народу многочлен $x^2-2$ не нравится за впадание в цикл $[2]$ длины 1. Неясно, почему, например отображение $x\to x^2+1$ тоже порождает циклы длины 1 для $m=21$, например)
У Вас $\lambda = O(\ln\ln m)$. Если это верно, то это хорошо, но еще нужна оценка длины периода $\tau$. Если по-прежнему $\tau=O(\sqrt{p})$, то результат не сильно радует (а если длина предпериода реально мала, то совсем не радует).
Хотелось бы , конечно, обо всем этом спросить спецов, которые пытались улучшить ро-метод Полларда или читали о таких попытках (только если найти чье-нибудь мыло и написать ему). Нужно вообще знать статистику величины $\tau$ - насколько длины циклов разные, насколько можно отгадать цикл покороче по $f(x)$ и $x_0$, насколько это помогает факторизации. проверить последнее, видимо, сложно, пока можно без него - пособирать статистику $\tau$ для разных $m$ (интересно, помогает ли варьирование $f$). Поскольку отображение итеративно, теоретически анализировать все это будет сложно.
Если чисто статистически обнаружится, что оценка $\tau=O(\sqrt{p})$ не улучшаема, то увы. В Вики пишут, что факторизация на эллиптических кривых это мегакруто (субэкспоненциальная скорость - это, конечно, действительно круто). С другой стороны, для меня она, например, пока что запредельна.
Можно также посмотреть эмпирически оценку $\lambda$ для других отображений $f$ - может оказаться, что длины предпериода тоже на самом деле короткие.

Andrey A, Вы наверняка искали эмпирически. У Вас есть какая-нибудь статистика? Чтобы лишних вычислений не делать.

[Andrey A]

Sonic86 в сообщении #1123434 писал(а):

Вас все это интересует в плане эффективной факторизации, правильно?

Правильно, но вникать в теорию сложности алгоритмов уже ни мозгов ни времени не хватит. Асимптотики нет.

Sonic86 в сообщении #1123434 писал(а):

... народу многочлен $x^2-2$ не нравится за впадание в цикл $[2]$ длины 1. Неясно, почему, например отображение $x\to x^2+1$ тоже порождает циклы длины 1 для $m=21$, например)

Если первый член выбирается случайно, то может оказаться $a_1,0,-2,[2] \mod m$. Наверное, э́та неприятность имеется в виду. Но, оказываясь сразу в цикле, мы её избегаем (ноль не в цикле). Тут, вообще, надо поподробней. Теоретически сохраняется возможность получить первым ходом $a_1\equiv 2$ или $-1 \mod m$. Однако это видно с первого шага, и можно взять вариант $a_1$, увеличив $t$ на единицу, хотя накладно. Если быть дотошным: $x+\frac{1}{x}\equiv 2\ \Rightarrow x^2+1\equiv 2x;\ (x-1)^2 \equiv 0;\ x \equiv 1$ (при нечетном $m$). И, поскольку $x$ - некоторая не очень большая степень двойки, то опять результативно. Не помню чтобы на такое наткнулся. В остальных случаях для единичного цикла [a_n] верно $a_n \equiv 2$ и/или $\equiv -1 \mod m'$. Это уже проходили.

Sonic86 в сообщении #1123434 писал(а):

Легко может оказаться, что предпериоды и так сильно короче.

Это как раз тонкий момент. Я исхожу из $2^t> $\lambda$. Если оно верно, можно в каждой итерации проверять только $a_1\equiv a_n$. Выигрыш именно в этом, а также в дроблении периодов. В сравнении с $f(x)=x^2$ их больше и они короче. Какая нужна статистика - по периодам простых или по "выстрелившим" периодам в факторизации? И в каких диапазонах. Я думал Вы погоняли уже. Может легче таблицу с процессом вложить?

[Sonic86]

Andrey A в сообщении #1123486 писал(а):

Если первый член выбирается случайно, то может оказаться $a_1,0,-2,[2] \mod m$. Наверное, э́та неприятность имеется в виду.

Наверное. Мне кажется, что они преувеличивают.

Andrey A в сообщении #1123486 писал(а):

Я исхожу из $2^t> \lambda$. Если оно верно, можно в каждой итерации проверять только $a_1\equiv a_n$.

Я не проверял то, как они ищут цикл (там какой-то метод Флойда), но у Вас для $n$ итераций будет $n$ проверок, а искать цикл можно тупо сортировкой за $O(n \ln n)$, либо как в оригинальном варианте - считать $\gcd(x_{2j}-x_j,m)$ - для $j=1,n$ - тоже за $O(n)$. Т.е. тут я экономии не вижу, разве что в коэффициенте.

Andrey A в сообщении #1123486 писал(а):

Я думал Вы погоняли уже.

Нет, я только тождество доказывал. Времени нет.

Andrey A в сообщении #1123486 писал(а):

Какая нужна статистика - по периодам простых или по "выстрелившим" периодам в факторизации? И в каких диапазонах.

Стастистика всех предпериодов и периодов для всех $m$ от $1$ до $10^3$ например для $f(x):=x^2-2$.

[Andrey A]

Sonic86 в сообщении #1123490 писал(а):

Стастистика всех предпериодов и периодов для всех $m$ от $1$ до $10^3$ например для $f(x):=x^2-2$.

Оказывается, прикреплять файлы к сообщениям - такой почет надо еще заслужить. Это приводит меня в восторг. Но не настолько чтобы постить таблицу в тыщу строк. Ладно, там посмотрим. Приведу пока несколько периодов факторизации нечетных $>10^7$, опуская $3,5,7,11$ и т.д. по первому результату от расчетного $a_1$. Кстати, пусть лучше будет $a_0$, чтобы индекс $a_k$ отражал длину периода.

48337297=131 $\cdot$ 368987 (6 итераций):
-1921101; -20248345; 20541230; 15586961; -4001554; -20275791; 4773916.

48337301=4523 $\cdot$ 10687 (18)

48337319=41 $\cdot$ 1178959 (2):
23276198; -2729172; -14353766.

48337321=1013 $\cdot$ 47717 (11)

48337327=479 $\cdot$ 100913 (119 итераций)

48337331=174503 $\cdot$ 277 (1):
18836817; -13969747

48337339=31 $\cdot$ 1559269 (2):
4000624; 16073084; -2772380

48337343=127 $\cdot$ 380609 (3):
7052461; 13703239; -24152189; -6266918.

48337357=211 $\cdot$ 229087 (12)

48337391=1303 $\cdot$ 37097 (30)

48337411=173 $\cdot$ 279407 (7)

48337429=1351 $\cdot$ 35779 (1):
-1942945; -438193

Множители не обязательно простые. Полная факторизация в последнем случае занимает еще 4 шага (3+1), но это конечно без проверки на простоту.

Sonic86 в сообщении #1123490 писал(а):

либо как в оригинальном варианте - считать $\gcd(x_{2j}-x_j,m)$ - для $j=1,n$ - тоже за $O(n)$. Т.е. тут я экономии не вижу, разве что в коэффициенте.

Ага, спасибо. Вы меня, кажется, вылечили. Мне казалось $J$ - переменная, пробегающая какие-то значения, но это бессмысленно Выигрыш есть, но ровно в два раза - там каждая проверка делается через два хода, зато можно не беспокоиться за $a_1$. Хотя нет, меньше чем в два раза. Ведь операция $x^2-2 \mod m$ в сравнении с проверкой $\gcd$ менее затратная. И остаются дробленые периоды, что может и существенно, но не на порядок. Надо просто погонять $x^2-2$ и $x^2-1$. На больших числах что-то должно быть видно и в Excel'е. Почему же $x^2-2$ не используется в оригинале?

[Sonic86]

Я понял такое:
Пусть $a_n := b^{2^n}+b^{-2^n}$. Тогда $f(a_n)=a_{n+1}$.
Пусть $L,T$ - предпериод и период соотв-но, $p:p\mid m$. Мы ищем минимальные $L,T: a_{L+T}\equiv a_L \pmod p$
$b^{2^{L+T}}+b^{-2^{L+T}}\equiv b^{2^L}+b^{-2^L} \pmod p$
При $\lambda = \mathrm{const}$ имеем квадратное уравнение в поле вычетов от переменной $b^{2^{L+T}}$, оно имеет только 2 очевидных корня: $b^{2^{L+T}}\equiv b^{\pm 2^L} \pmod p$, выберем знак плюс, решение для знака минус получается уменьшением $T$ на $1$.
$b^{2^{L+T}}\equiv b^{2^L} \pmod p$
В худшем случае, когда $b$ - образующая по модулю $p$, сравнение равносильно
$2^{L+T}\equiv 2^L \pmod {p-1}$
$p-1=2^wq, L:=w, \Rightarrow L\leqslant \log_2m$
$2^T\equiv 1 \pmod q$
В худшем случае, если $q$ простое, а $2$ - образующая по модулю $q$, получаем неулучшаемую оценку длины периода $T=q-1=\frac{p-1}{2}-1$ (простое Жермен).
Т.е., в итоге, если $m$ делится на простое Жермен, то поиск длины цикла по этому модулю будет требовать $O(p)$ операций. Можно попробовать протестировать: найти несколько больших простых Жермен, перемножить и запустить алгоритм - видимо, он там повесится.

Andrey A в сообщении #1123579 писал(а):

48337327=479 $\cdot$ 100913 (119 итераций)

А вот и пример: $479-1=2\cdot 239; 239-1=2\cdot 7\cdot 17 = 2\cdot 119$.
Это сильно хуже, чем оценка обычного метода Полларда, но эта оценка - детерминированная. Скорее всего, если детерминированно оценивать алгоритм Полларда, то там будет такая же оценка. М.б. Поллард на числах Жермен тоже тормозит. А как дать вероятностную оценку, я не знаю. По Вашей статистике видно, что такие длинные циклы - как раз редкость.
Надо статистику собирать.
Но $x^2-2$ явно исключительный в плане анализа.

[Sonic86]

Еще нашел упоминание многочлена $x^2-2$ и его решения у Кнута Искусство программирования том 2, страница 421 в моей книге (у него вообще страниц нету). Пункт Алгоритм В. Не нравится он им по обеспечению случайности. Видимо, имеется ввиду как раз эта проблема с простыми Жермен.
$x_{n+1}=x_n^2-2 \Leftrightarrow x_n=r^{2^n}+r^{-2^n}$.
Хоть бы кто-нибудь написал нормально

Кнут писал(а):

Количество итераций $m(p)$... . Экспериментальным путем установлено, что среднее значение $m(p)$ примерно равно $2\sqrt{p}$ и никогда не превышает $12\sqrt{p}$, когда $p<10^6$

А у нас $O(p)$, если $p$ - простое Жермен.
Видимо, вопрос исчерпан Даже без статистики обошлись.

[Andrey A]

Sonic86 в сообщении #1123652 писал(а):

М.б. Поллард на числах Жермен тоже тормозит.

Там картинка отличается по первому впечатлению. Для $m=23$ по $f(x)=x^2-1$ единственный период $[0,-1]$, по $x^2+1$ - $[9,-10]$. Всё остальное уходит в предпериоды (хвостики $\rho $-петли), максимальные из которых соответственно $9$ и $6$ знаков. Для $m=29$ картина похожая, хотя не знаю чем оно особенное. Тут плюс в том, что по различным простым модулям при прочих равных срабатывает тот, к периоду которого $a_0$ оказалось ближе. Т.е. тот случай, когда скорость эскадры определяется по самому быстрому кораблю, а не наоборот. Если так, можно ожидать более равномерной статистики, без рывков $1/119$. Достоинство? Скорее для исследователя.

Sonic86 в сообщении #1123652 писал(а):

$T=q-1=\frac{p-1}{2}$ (простое Жермен).

Или $\frac{p-3}{2}$ ?

Sonic86 в сообщении #1123652 писал(а):

$2^T\equiv 1 \pmod q$

Это следует уже из $b^{2^T}\equiv b$. При вз. простом $b$ имеем $b^{2^T-1}\equiv 1$. Для общего случая можно брать $q=\gcd (p-1,2^T-1)$ если я Вас правильно понял.

Подозрение, что $x^2-2$ отдельный случай у меня тоже не улетучивается. Кстати, по поводу $\gcd(x_{2j}-x_j,m)$... бессмыслено Если нет уверенности что $j$ в периоде, то проверки

$$2j\equiv j+1;\ 2j\equiv j+2;...\ 2j\equiv 2j-1$$

не бессмыслены. На этом и подорвался.

Sonic86 в сообщении #1123663 писал(а):

Не нравится он им по обеспечению случайности.
$x_{n+1}=x_n^2-2 \Leftrightarrow x_n=r^{2^n}+r^{-2^n}$.
Хоть бы кто-нибудь написал нормально

Этот вывод не такой уж тривиальный. Ну, мне таковым не кажется, а особенно связь с $f(r)\equiv r^2$.

Sonic86 в сообщении #1123663 писал(а):

... исчерпан

Соберу статистику по вышеприведенным модулям и посмотрим.

[Sonic86]

Andrey A в сообщении #1123666 писал(а):

Или $\frac{p-3}{2}$ ?

Ой, поправил

Andrey A в сообщении #1123666 писал(а):

Для общего случая можно брать $q=\gcd (p-1,2^T-1)$ если я Вас правильно понял.

Почему можно? У нас $p$ - искомый простой делитель, так что мы при вычислении $q$ брать никак не можем.

Andrey A в сообщении #1123666 писал(а):

Кстати, по поводу $\gcd(x_{2j}-x_j,m)$... бессмыслено Если нет уверенности что $j$ в периоде, то проверки

$$2j\equiv j+1;\ 2j\equiv j+2;...\ 2j\equiv 2j-1$$

не бессмыслены. На этом и подорвался.

Честно говоря, ничего не понял

Andrey A в сообщении #1123666 писал(а):

Соберу статистику по вышеприведенным модулям и посмотрим.

Если время будет, тоже попробую. Интересно все-таки.

[Andrey A]

Sonic86 в сообщении #1123694 писал(а):

Почему можно?

В случае Софи Жермен это простое $q$, а в общем - имелся в виду вообще дискретный логарифм по основанию $b$. При вычислении, понятно, p не известно.

Sonic86 в сообщении #1123694 писал(а):

... не понял

А и не нужно.

(Оффтоп)

Всё оправдываюсь. Нога-то небось уже не вырастет.

[Andrey A]

Ну, в общем да, шило на мыло:

$\begin{matrix} m & k(x^2-2) & k(x^2-1) & k(x^2+1)\\ 48337297=71\cdot 131\cdot 5197 & 6 & 5,3 & 6,7\\ 48337301=4523\cdot 10687 & 18 & 52,3 & 35,2\\ 48337319=41\cdot 1178959 & 2 & 3,9 & 7\\ 48337321=1013\cdot 47717 & 11 & 25,2 & 40,8\\ 48337327=479\cdot 100913 & 119 & 12,6 & 15,7\\ 48337331=7\cdot 97\cdot 257\cdot 277 & 1 & 2,4 & 1,5\\ 48337339=31^2\cdot 179\cdot 281 & 2 & 4 & 3\\ 48337343=59\cdot 127\cdot 6451 & 3 & 5,5 & 5,2\\ 48337357=107\cdot 211\cdot 2141 & 12 & 11,5 & 8,5\\ 48337391=1303\cdot 37097 & 30 & 24,2 & 44\\ 48337411=173\cdot 279407 & 7 & 11,4 & 10,8\\ 48337429=7\cdot 37\cdot 193\cdot 967 & 1 & 2,2 & 1,8 \end{matrix}$

Данные 1-го и 2-го столбцов взяты из поста выше, 3-го и 4-го - усредненные по результатам десяти опытов со случайными $a_0 $ стандартного
$\rho $-алгоритма. Случай $k=119$ доедает последние иллюзии. Интересно другое, проверьте: $m=48337391,\ a_0=23505425.$ По $f(x)=x^2+1$
$\rho $-алгоритм выдает результат $1\cdot 48337391$. Значит там тоже имеется проблема "плохих сочетаний"? Тогда я понимаю почему "они боятся случайностей". Я ведь $k$ записывал, на единицу в делителях случайно обратил внимание, а по $x^2-2$ случайно набрести на большое "плохое число" - даже не помню... Хотя, это уже не важно.

[Andrey A]

upd

Andrey A в сообщении #1124124 писал(а):

... $m=48337391,\ a_0=23505425.$ По $f(x)=x^2+1$ $\rho $-алгоритм выдает результат $1\cdot 48337391$. Значит там тоже имеется проблема "плохих сочетаний"? Тогда я понимаю почему "они боятся случайностей".

Нет, тут другое. Тот случай, когда цикл длиной $k=j$ находится раньше по $\mod m$, чем по $\mod m'$, т.е. $a_{2j}=a_{j}$. Он, вообще говоря, результативный, поскольку функции от последнего члена предпериода и последнего члена периода сравнимы с первым членом периода и, значит, сравнимы между собой, причем не равны друг другу. Сами члены сравнимы тогда только по $\mod m'$ (пример в первом посте). То есть по установлении $a_{2j}=a_{j}$ нужно еще решить малозатратную задачу нахождения наименьшего $i$ такого, что $a_{2j-i}\neq a_{j-i}$. В приведенном примере при $k=32$ находится $i=7$, при котором $a_{57}\neq a_{25}$ и $\gcd (a_{57}-a_{25}, 48337391)=1303$. Вот если окажется $i=j$ и $a_{2j}=a_{j}=\pm a_0$, что можно проверить первым делом, тогда имеем замкнутый цикл и нерезультативный опыт, т.к. простоты $m$ это еще не доказывает. Кроме того возможен нерезультативный случай $a_{2j-i}=-a_{j-i}$.