2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Факторизация
Сообщение13.05.2016, 20:46 
Заслуженный участник


08/04/08
8556
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, Вы наверняка искали эмпирически. У Вас есть какая-нибудь статистика? Чтобы лишних вычислений не делать.

 Профиль  
                  
 
 Re: Факторизация
Сообщение14.05.2016, 04:20 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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$ их больше и они короче. Какая нужна статистика - по периодам простых или по "выстрелившим" периодам в факторизации? И в каких диапазонах. Я думал Вы погоняли уже. Может легче таблицу с процессом вложить?

 Профиль  
                  
 
 Re: Факторизация
Сообщение14.05.2016, 08:27 
Заслуженный участник


08/04/08
8556
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$.

 Профиль  
                  
 
 Re: Факторизация
Сообщение14.05.2016, 20:05 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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$ - переменная, пробегающая какие-то значения, но это бессмысленно :oops: Выигрыш есть, но ровно в два раза - там каждая проверка делается через два хода, зато можно не беспокоиться за $a_1$. Хотя нет, меньше чем в два раза. Ведь операция $x^2-2 \mod m$ в сравнении с проверкой $\gcd$ менее затратная. И остаются дробленые периоды, что может и существенно, но не на порядок. Надо просто погонять $x^2-2$ и $x^2-1$. На больших числах что-то должно быть видно и в Excel'е. Почему же $x^2-2$ не используется в оригинале?

 Профиль  
                  
 
 Re: Факторизация
Сообщение15.05.2016, 09:25 
Заслуженный участник


08/04/08
8556
Я понял такое:
Пусть $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$ явно исключительный в плане анализа.

 Профиль  
                  
 
 Re: Факторизация
Сообщение15.05.2016, 11:27 
Заслуженный участник


08/04/08
8556
Еще нашел упоминание многочлена $x^2-2$ и его решения у Кнута Искусство программирования том 2, страница 421 в моей книге (у него вообще страниц нету). Пункт Алгоритм В. Не нравится он им по обеспечению случайности. Видимо, имеется ввиду как раз эта проблема с простыми Жермен.
$x_{n+1}=x_n^2-2 \Leftrightarrow x_n=r^{2^n}+r^{-2^n}$.
Хоть бы кто-нибудь написал нормально :roll:
Кнут писал(а):
Количество итераций $m(p)$... . Экспериментальным путем установлено, что среднее значение $m(p)$ примерно равно $2\sqrt{p}$ и никогда не превышает $12\sqrt{p}$, когда $p<10^6$
А у нас $O(p)$, если $p$ - простое Жермен.
Видимо, вопрос исчерпан :roll: Даже без статистики обошлись.

 Профиль  
                  
 
 Re: Факторизация
Сообщение15.05.2016, 11:55 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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)$... бессмыслено :oops: Если нет уверенности что $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}$.
Хоть бы кто-нибудь написал нормально :roll:

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

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

 Профиль  
                  
 
 Re: Факторизация
Сообщение15.05.2016, 14:27 
Заслуженный участник


08/04/08
8556
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)$... бессмыслено :oops: Если нет уверенности что $j$ в периоде, то проверки $$2j\equiv j+1;\ 2j\equiv j+2;...\ 2j\equiv 2j-1$$ не бессмыслены. На этом и подорвался.
Честно говоря, ничего не понял :-(

Andrey A в сообщении #1123666 писал(а):
Соберу статистику по вышеприведенным модулям и посмотрим.
Если время будет, тоже попробую. Интересно все-таки.

 Профиль  
                  
 
 Re: Факторизация
Сообщение15.05.2016, 16:11 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Sonic86 в сообщении #1123694 писал(а):
Почему можно?

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

А и не нужно.

(Оффтоп)

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

 Профиль  
                  
 
 Re: Факторизация
Сообщение15.05.2016, 20:18 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Ну, в общем да, шило на мыло:

$\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$ случайно набрести на большое "плохое число" - даже не помню... Хотя, это уже не важно.

 Профиль  
                  
 
 Re: Факторизация
Сообщение17.05.2016, 14:22 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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}$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group