2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Факторизация
Сообщение08.05.2016, 16:44 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Некоторая последовательность строится по принципу $a_{n+1}\equiv a_n^2-2\mod m$, $\left| a_1\right|>2$. Под знаком $ тут понимается абсолютно наименьший вычет, т.е. $\left| a_n\right|<m/2$. По понятным причинам c некоторого момента члены такой последовательности образуют период из $k$ знаков.

1. Верно ли, что произведение $k$ членов периода всегда $\equiv -1\mod m$ или (в случае составного $m$) \equiv -1\mod m'>1\mid m$? Не знаю как доказать.

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$-петли содержится пара сравнимых по модулю нетривиальных квадратов, о чем упоминания не встречал. Как бы довести всё это до совершенства?

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


08/04/08
8556

(Оффтоп)

Andrey A в сообщении #1122038 писал(а):
$\left| a_1\right|>2$.
Видимо, $|a_j|>2$.

Я попробую переформулировать попонятнее (хотя бы для меня) то, что понял.

Пусть $m$ - модуль, $f(x)=x^2-2$ действует на кольце вычетов $\mathbb{Z}_m$. Итерируя $f$ получаем разложение $f^{\infty}(\mathbb{Z}^\times_m)$ на циклы вида $x\to f(x)\to ... \to f^{k-1}(x)\to x$. Часть циклов тривиальна: $\{-1\}; \{2\}$ - их не рассматриваем. Заметим, что у $0$ аттрактор - $2$, так что его тоже не рассматриваем. Необратимые элементы кольца вычетов тоже не рассматриваем (иначе произведение не получится). Тогда если $L$ - множество всех элементов нетривиального цикла длины $k$, $x$ - какой-то элемент цикла, то $\prod\limits_{j=0}^{k-1}f^j(x)\equiv\pm 1 \pmod m$.
Все "некрасивые" уточнения про абсолютную величину остатка относятся уже к точному определению знака - я их не рассматриваю.
В этом случае для вопроса
Andrey A в сообщении #1122038 писал(а):
1. Верно ли, что произведение $k$ членов периода всегда $\equiv -1\mod m$ или (в случае составного $m$) $\equiv -1\mod m'>1\mid m$? Не знаю как доказать.
поскольку $f$ переводит классы вычетов в классы вычетов, случай составного $m$ сводится к случаю простого $m$ просто потому что достаточно выбрать простой делитель $p|m$ у составного $m$ и тогда $\{a_j \pmod m \pmod p \equiv a_j \pmod p \equiv -1 \pmod p\}$ при условии истинности утверждения для простого $m$.
Если не брать абсолютно наименьший вычет, результат получается слабее - $\pm 1$, зато сводимость есть.

Как доказывать для простого $m$ указанное соотношение - пока не знаю.

А дальше моих телепатических способностей не хватает для понимания:
Andrey A в сообщении #1122038 писал(а):
Я глубоко не вникал, но там, кажется, функция $a^2-2$ как раз исключена. Хоть похож на Монте-Карло, только всё ж не Монте-Карло.
Вот что это значит?
Andrey A в сообщении #1122038 писал(а):
квазипростые Мерсена.
Что это? Составные вида $2^p-1$?
Хотя если этот текст убрать, то получается тоже осмысленно.
Дальше вообще ниасилил :-(

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


21/11/12
1870
Санкт-Петербург
В обратном порядке.
Sonic86 в сообщении #1122106 писал(а):
Что это? Составные вида $2^p-1$?

Да. И пример как раз с одним из них.
Sonic86 в сообщении #1122106 писал(а):
Вот что это значит?

Шучу неудачно. Песня такая была https://www.youtube.com/watch?v=Z5N58pnBKs8.
Из Вики:
В 1975 году Поллард опубликовал статью[6], в которой он, основываясь на алгоритме Флойда обнаружения циклов, изложил идею алгоритма факторизации чисел, работающего за время, пропорциональное $N^{1/4}$[6][1]. Автор алгоритма назвал его методом факторизации Монте-Карло, отражая кажущуюся случайность чисел, генерируемых в процессе вычисления. Однако позже метод всё-таки получил своё современное название — ρ-aлгоритм Полларда[7].
Sonic86 в сообщении #1122106 писал(а):
Если не брать абсолютно наименьший вычет, результат получается слабее - $\pm 1$, зато сводимость есть.

Это как раз роли не влияет. Мне кажется на практике все быстро проясняется, но за грамотное изложение спасибо.
Andrey A в сообщении #1122038 писал(а):
$\left| a_1\right|>2$. Видимо, $|a_j|>2$.

Нет, именно $\left| a_1\right|>2$, иначе по любому модулю последовательность состоит из двоек или единиц.

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


08/04/08
8556
Andrey A в сообщении #1122125 писал(а):
Нет, именно $\left| a_1\right|>2$, иначе по любому модулю последовательность состоит из двоек или единиц.
Пусть $m=17, a_1=5$. Тогда имеем цепочку $5\to 6\to 0 \to 2\to 2 \to...$, цикл $=\{2\}$, произведение $\equiv 2\not \equiv -1\pmod m$.

Про абсолютный вычет вот вроде как контрпример:
$m=19, a_1=4$: $4 \to -5 \to 4$, $|4|\cdot |-5|\equiv 20\equiv 1 \pmod {19}$. Или нет?
Если что: $m=13, a_1=7:$ $7 \to 8 \to 10 \to 7$, $7\cdot 8\cdot 10 \equiv 1\pmod{13}$, а с модулями $6\cdot 5\cdot 3 \equiv -1\pmod {13}$.

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


21/11/12
1870
Санкт-Петербург
Sonic86 в сообщении #1122184 писал(а):
...а с модулями $6\cdot 5\cdot 3 \equiv -1\pmod {13}$.

Э... с квадратичными вычетами поаккуратней надо бы: если $a$ - вычет, то $-a$ может быть невычетом. А могут быть оба вычетами, но при разных квадратах. В данном случае строго: $-5\cdot -3\cdot -6\equiv 1\mod 13$. Спасибо за контрпример. По $\mod 19:\ -5 \cdot4\equiv -1.$ Двойка может возникнуть после нуля в случае $m$ вида $p^2-2q^2$. В итоге либо $-1$, либо $1$, либо $2$, что все равно остается гипотезой. Думаю, в практических целях нет смысла вычислять произведение членов периода за исключением периода из одного члена $(a_1)$. Тут $a_n-a_1=0$, и по предположению должна оказаться результативной операция $\gcd (m,(a_1-2)(a_1^2-1))$, хотя для $m=119$, к примеру, имеем $(-15)$ и $\gcd (119,(-15-2)((-15)^2-1))=119$. Тоже надо поаккуратней.

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


08/04/08
8556
Andrey A, Вы знаете, я тут деградировал до уровня первокурсника, а из тестов простоты помню только тесты Люка и тесты для чисел Ферма и Мерсенна. Я не могу понять Ваш пост т.к. не помню контекста методов факторизации :-(.
Пишу пока, что понимаю - буду доказывать, что произведение равно $\pm 1$.

Похоже, что соотношение $P=\prod\limits_{j=0}^{k-1}f^{(j)}(x)=0$ в $\mathbb{Z}_m$ является общим алгебраическим соотношением, мало зависящим от поля, значит доказывать его надо соответствующим образом - независимо от полей вычетов. ($f^{(j)}(x)=(f\circ ...\circ f)(x)$ $j$ раз)
Пусть $f^{(n)}(x)=x$ для какого-то $x\in F$. Значит $x$ - это какой-то корень многочлена $g_n(x)=f^{(n)}(x)-x$.
$(\forall n)g_n(-1)=g_n(2)=0$
Доказательство могло бы выглядеть так: находим корни $\alpha$ многочлена $g_n(x)$ и вычисляем $P$ при $x=\alpha$ и получаем $\pm 1$. Получать мы должны что-то одно, поэтому знак у $\pm 1$ должен зависеть чисто от $n$ - вот эту зависимость можно поискать пока на примерах полей $\mathbb{Z}_p$, ну или $\mathbb{C},\mathbb{R}$.
Например, при $n=1,2$ $P=-1$.
$n=1: g_1(x)=x^2-x-2, x\in\{-1;2\}, f(x)=x$ и при $x\neq 2$ получаем знак $-1$.
$n=2: g_2(x)=(x^2-2)^2-2-x=(x-2)(x+1)(x^2+x-1)$, корни $2;-1$ исключаем, для оставшихся корней $x=\frac{-1\pm\sqrt{5}}{2}$ имеем $P=-1$.
Теперь можно поискать все поля вычетов, где такое имеет место: $\frac{-1\pm\sqrt{5}}{2}\in\mathbb{Z}_p\Leftrightarrow\left(\frac{5}{p}\right)=1\Leftrightarrow p\equiv \pm 1\pmod {5}$. И действительно: в полях $\mathbb{Z}_p$ при $p=11;19;29;...$ можно найти двучленные циклы, произведение элементов которых действительно равно $-1$.
А вот как решать в целом - неясно. Если бы $g_n(x)$ был бы неприводимым, то можно было бы заменить вычисление $P(\alpha)$ на вычисление $P(x)\pmod {g_n(x)}$, однако в общем случае даже $\frac{g_n(x)}{(x-2)(x+1)}$ приводим. Но как разложить его на множители? Ясно, что корни $g_{n}(x)$ являются корнями $g_{nd}(x)$, но это не помогает, т.к. $\deg g_n(x)=2^n$.
Например, $g_3(x)=(x-2)(x+1)(x^3-3x+1)(x^3+x^2-3x-1)$, корни последних двух множителей выражаются через $\sqrt[9]{1}$ (пруф http://www.wolframalpha.com/input/?i=solve+x%3D%28%28x^2-2%29^2-2%29^2-2). Кому-нибудь это помогает?

В общем, получили какую-то интересную чисто алгебраическую задачу.

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


21/11/12
1870
Санкт-Петербург
Sonic86 в сообщении #1122220 писал(а):
... не помню контекста методов факторизации

Давайте на примере. Возьмем $m=15403$.
При $t=4$ имеем $2^{2^4}=2^{16}\equiv 3924\mod 15403;$
$\dfrac{1}{3924}\equiv 5625;\ 3924+5625\equiv -5854=a_1.$
Далее.
$(-5854)^2-2\equiv -2361;\ \gcd [(-2361)-(-5854),15403]=1$
$(-2361)^2-2\equiv -1567;\ \gcd [(-1567)-(-5854),15403]=1$
$(-1567)^2-2\equiv 6410;\ \gcd [6410-(-5854),15403]=73$
$15403/73=211$
Три шага. Я бы не стал выкладывать, но уж больно резво работает. Почему $a_1$ вычисляется подобным образом - об этом позже, но смысл в том, чтобы по одному из простых модулей оно попало в цикл, тогда на некотором шаге проявит себя. В $\rho $-aлгоритме, если не ошибаюсь, для сравнения берется не только $a_1$, но и последующие. Оно конечно надежней, но...
Sonic86 в сообщении #1122220 писал(а):
... является общим алгебраическим соотношением, мало зависящим от поля

Это вряд ли. Возьмем хотя бы $f(x)=x^2-5$. По $\mod 19$ имеем $-8\cdot 2\cdot -1\cdot -4\equiv -7$
А если взять $f(x)=x^2$, то
$a_1^2\equiv a_2$
$a_2^2\equiv a_3$
...
$a_{n-1}^2\equiv a_n$
$a_n^2\equiv a_1$
Тут $(a_1a_2...a_{n-1}a_n)^2\equiv a_1a_2...a_{n-1}a_n$, и получаем строго единицу. Кроме того $a_i^2\equiv (a_{i-1}^2)^2\equiv a_{i-1}^4\equiv a_{i+1}$... и т.д. Для любого $a$ верно $a^{2^n}\equiv a$. Малую ТФ не напоминает? Я собственно с Этими циклами возился, там очень интересно получается. Для простых вида $4k+3$ - строгие замкнутые кольца кв. вычетов, хвостик $\rho $-петли может состоять только из одного невычета. Для простого вида $4k+1$ всё иначе выглядит. Там кольца с "притоками" (необратимые элементы из Вашего поста, суть все возможные хвостики $\rho $-петли для заданного цикла), причем притоки ветвятся. Это тоже вычеты, невычеты только в начале притоков (истоки). Какие соляристические структуры могут быть для составного числа с большим кол-вом делителей - даже не представить. Там ведь к одному вычету могут вести сколько угодно квадратов. То есть деревья. Где бы прогу такую заполучить? Потом бросилось в глаза то обстоятельство, что по заданному модулю "длина притоков" - величина постоянная. Даже для разных циклов, но это надо проверять. И далее. Если $a$ - вычет, то $b\equiv \dfrac{1}{a}$ - тоже вычет. Если $a$ и $b$ - члены одного цикла, то этот бублик можно есть с двух концов, т.е. строить две последовательности от обратных по модулю начальных членов, причем для всех $i$ будет выполняться $a_ib_i\equiv 1$. Запишем это для удобства дробями:
$$\frac{a_1}{b_1};\frac{a_2}{b_2};...;\frac{a_i}{b_i}$$
Если $a_i\equiv a_1$, то $\dfrac{1}{b_i}\equiv \dfrac{1}{b_1}$ и $b_i\equiv b_1\mod m'$ (вот тут вспомнилось о факторизации: экономия). Точно также из двух утверждений $b_i\equiv a_1$ и $a_i\equiv b_1$ можно проверять только одно, но последовательностей все-таки две. Как бы это объехать? Утверждение $b_i\equiv a_1$ равносилно $a_1a_i\equiv 1$ (замена $b_i\rightarrow \dfrac{1}{a_i}$). Соответственно $a_i\equiv a_1\Leftrightarrow a_1b_i\equiv 1$. Если верно одно из них, то $(a_1a_i-1)(a_1b_i-1)\equiv 0$.
$a_ib_ia_1^2-a_1(a_i+b_i)\equiv -1$
$a_1^2-a_1(a_i+b_i)\equiv -1$
$a_1-a_i-b_i\equiv \frac{-1}{a_1}\equiv -b_1$
$a_1+b_1\equiv a_i+b_i$
То есть для эффективного сравнения достаточно суммарной последовательности. Запишем теперь
$a_i^2 \equiv a_{i+1}$
$b_i^2 \equiv b_{i+1}$
$2a_ib_i \equiv 2$
В сумме получаем $(a_i+b_i)^2 \equiv a_{i+1}+b_{i+1}+2$ или
$$(a_i+b_i)^2-2 \equiv a_{i+1}+b_{i+1}$$
Отсюда и тема возникла. Расчет для 1-го члена - просто наименьшее число $>m$ вида $2^{2^t}$ (чтобы понадежней оказаться в цикле). Наверное я опять Вас запутал. Ну, из примера всё видно, нужно на практике попробовать.

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


08/04/08
8556
Andrey A в сообщении #1122361 писал(а):
Три шага.
выглядит мощно

Andrey A в сообщении #1122361 писал(а):
Это вряд ли. Возьмем хотя бы $f(x)=x^2-5$.
Нет:
Sonic86 в сообщении #1122106 писал(а):
$f(x)=x^2-2$
Это фиксированный многочлен. Надо разобраться, почему все работает для него, а потом искать другие многочлены с таким свойством.
Остальное пока ниасилил - надо спать.

Andrey A в сообщении #1122361 писал(а):
Для любого $a$ верно $a^{2^n}\equiv a$. Малую ТФ не напоминает?
Да. Я как раз еще вчера думал, что $(\forall f)f^{(n)}(x)-x \mid f^{(nk)}(x)-x$, что напоминает круговые многочлены.

Andrey A в сообщении #1122361 писал(а):
Где бы прогу такую заполучить?
Закодьте на C++ или еще на чем-нибудь (PARI/GP попробуйте или вообще Haskell). Можно даже руками в Excele (я в нем сегодня буду статистику циклов считать, прогу мне писать лень и времени нет).

Andrey A в сообщении #1122361 писал(а):
$$(a_i+b_i)^2-2 \equiv a_{i+1}+b_{i+1}$$
Т.е. $f(x)=x^2-2$ именно отсюда вылез?
Ну да, надо ручками считать - я еще с тождеством вожусь.

Andrey A в сообщении #1122361 писал(а):
А если взять $f(x)=x^2$, то
... Я собственно с Этими циклами возился, там очень интересно получается. Для простых вида $4k+3$ - строгие замкнутые кольца кв. вычетов, хвостик $\rho $-петли может состоять только из одного невычета. Для простого вида $4k+1$ всё иначе выглядит. Там кольца с "притоками" (необратимые элементы из Вашего поста, суть все возможные хвостики $\rho $-петли для заданного цикла), причем притоки ветвятся. Это тоже вычеты, невычеты только в начале притоков (истоки). Какие соляристические структуры могут быть для составного числа с большим кол-вом делителей - даже не представить. Там ведь к одному вычету могут вести сколько угодно квадратов. То есть деревья.
С возведением в квадрат в целом все понятно - возведение во 2-ю степень в мультипликативной группе вычетов $\mathbb{Z}_p^\times$ - это просто умножение на 2 в аддитивной группе $\mathbb{Z}_{p-1}^+$, и дальше все зависит от степени двойки в разложении $p-1$ на множители (для чисел Ферма получаем одно дерево без циклов, например). Если простое $p$ менять на составное $m$, то все сложнее, но в целом похоже - смотрите структуру группы $\mathbb{Z}_m^\times$.
Необратимые элементы у меня другие - это необратимые по умножению в $\mathbb{Z}_m^\times$, например $0,3,5,6,9,10,12$ в $\mathbb{Z}_{15}$.

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


08/04/08
8556
Sonic86 в сообщении #1122220 писал(а):
знак у $\pm 1$ должен зависеть чисто от $n$
К сожалению, нет: $g_n(x)$ не примитивный, разным его корням соответствуют разные знаки.

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


21/11/12
1870
Санкт-Петербург
А, ну значит я не понял.
Sonic86 в сообщении #1122384 писал(а):
... и дальше все зависит от степени двойки в разложении $p-1$ на множители
Это да. Квадратичные вычеты - они же степенные. Помогает это в описании циклов? В Excel'е это труднопредставимо, и вообще на плоскости.
Sonic86 в сообщении #1122384 писал(а):
Т.е. $f(x)=x^2-2$ именно отсюда вылез?

Именно. А по первому вопросу Ваших контрпримеров вполне достаточно. Проверять по трем параметрам - весь выигрыш растеряешь.

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


08/04/08
8556
Andrey A в сообщении #1122450 писал(а):
А по первому вопросу Ваших контрпримеров вполне достаточно.
Я работаю не с Вашей, а с модицированной формулировкой. Доказательство нашел:

Обозначения:
$f_0(x):=x$
$f_{j+1}(x):=f_j^2(x)-2$
В частности $f(x)=f_1(x)$
$P(x) := \prod\limits_{j=0}^{n-1}f_j(x)$
Гипотеза состоит в том, что для корня $\alpha\neq 2$ многочлена $f_n(x)-x$ в любом поле (или даже области целостности?) $F$ верно, что $P(\alpha)=\pm 1$.
Поскольку я так и не понял, какой справа знак, то будем возводить в квадрат.
Ясно, что если $\alpha$ - корень $P(x)\pm 1$, то $\alpha$ - не корень $P(x)\pm 1$ (иначе $\alpha$ был бы корнем $2$). Значит $P(\alpha)=\pm 1\Leftrightarrow P^2(\alpha)=1$.
Далее, предположим, что 2 - корень кратности 1 для $f_n(x)-x$. Тогда любой корень $f_n(x)-x$ является корнем $(x-2)(P^2(x)-1)$, т.е. попросту $(x-2)(P^2(x)-1)\equiv 0 \pmod{f_n(x)-x}$. Вот и докажем это.
Далее все преобразования равносильны, знак "$\Leftrightarrow$" не пишу.
$(x-2)(P^2(x)-1)\equiv 0 \pmod{f_n(x)-x}$
$(x-2)(\prod\limits_{j=0}^{n-1}f_j^2(x)-1)\equiv 0 \pmod{f_n(x)-x}$
$(x-2)(\prod\limits_{j=0}^{n-1}(f_{j+1}(x)+2)-1)\equiv 0 \pmod{f_n(x)-x}$
$(x-2)((f_n(x)+2)\prod\limits_{j=1}^{n-1}(f_j(x)+2)-1)\equiv 0 \pmod{f_n(x)-x}$
$(x-2)((x+2)\prod\limits_{j=1}^{n-1}(f_j(x)+2)-1)\equiv 0 \pmod{f_n(x)-x}$
$(x^2-4)\prod\limits_{j=1}^{n-1}(f_j(x)+2)-x+2\equiv 0 \pmod{f_n(x)-x}$
$(f_1(x)-2)\prod\limits_{j=1}^{n-1}(f_j(x)+2)-x+2\equiv 0 \pmod{f_n(x)-x}$
$(f_1(x)-2)(f_1(x)+2)\prod\limits_{j=2}^{n-1}(f_j(x)+2)-x+2\equiv 0 \pmod{f_n(x)-x}$
$(f_1^2(x)-4)\prod\limits_{j=2}^{n-1}(f_j(x)+2)-x+2\equiv 0 \pmod{f_n(x)-x}$
$(f_2(x)-2)\prod\limits_{j=2}^{n-1}(f_j(x)+2)-x+2\equiv 0 \pmod{f_n(x)-x}$
...
$(f_n(x)-2)-x+2\equiv 0 \pmod{f_n(x)-x}$
$x-2-x+2\equiv 0 \pmod{f_n(x)-x}$
Вин! :lol:
Отсюда следует истинность соотношения в полях вычетов по простому модулю, да и даже в кольцах вычетов по составному модулю.

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


21/11/12
1870
Санкт-Петербург
А что знак при единице может быть любой мы и так знаем. Я с Вашего позволения позже буду вникать, но все равно здорово. Вот что подумал: для тестирования на простоту алгоритм явно не годится. В простых вида $2p+1$ (Софи Жермен) похоже имеем $k=p-1$. Если даже это не верно, все равно для простых вида $4l+3 $ раньше $k=\left \lfloor m/4 \right \rfloor$ ничего точно утверждать нельзя. Для $4l+1 $ и тем более. Достоинства могут быть только в быстром поиске делителей, после чего для полного анализа нужно "запускать Циклопа". И тут важно знать до какого момента вести поиск. Усредненный параметр $m/k$ поначалу возрастает (ну и что?). Не знаю как решать такие задачи. Есть однако повод для оптимизма. Цепочку рассуждений, приводящую к $f(x)=x^2-2$ можно применить к готовому циклу, если он не дал результата по $\mod m'$. Такие случаи редки и легко различимы - период значительно меньше чем у "соседних" простых. По сути речь идет не о "плохих" составных, а о "плохих" сочетаниях с $a_1$, когда длина циклов у пары множителей совпадает, и мы попадаем туда, пардон, начальным членом. Можно пробовать варианты $a_1$ наобум, но есть шанс начать с невычета, и надо ловить тогда период не с первого знака, что есть ощутимая работа. Вот я попробовал менять $a_1$ не случайным образом, а по тому же принципу, помня, что $a+2$ - вычет. Вместо $a_1$ берем тогда $a'_1\equiv a_1+\dfrac{1}{a_1+2}-2\mod m$, и вроде неплохо получается.
В примере с $m=2047$ из первого поста цикл $(96,-1021,516,144,264)$ не дает результата. А с $a'=282$ получаем $(282,-311,510,129,263,-431)$ и $282\equiv -431\mod 23$. Во всех известных мне "плохих" случаях тоже сработало. Но если что можно брать $a''$ по той же формуле.

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


08/04/08
8556
Andrey A в сообщении #1122543 писал(а):
В простых вида $2p+1$ (Софи Жермен) похоже имеем $k=p-1$.
Да, именно так. Насколько я помню, у Кнута такие числа по подобным причинам обзывались сильно простыми. (это если Вы рассматриваете отображение $x\to x^2$. Если другое - то не ведаю).
Для составных $m$ немного посложнее, но картина похожая - в кольце $\mathbb{Z}_m$ $\varphi(m)$ элементов, а их порядок - функция Кармайкла $\lambda (m)$ - она лишь немножко меньше функции Эйлера.

Остальное буду позже разбирать. Но отпуск мой закончился, м.б. отвечу, м.б. вообще не смогу, увы.

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


21/11/12
1870
Санкт-Петербург
o.k.

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


21/11/12
1870
Санкт-Петербург
Sonic86 в сообщении #1122623 писал(а):
Sonic86 в сообщении #1122623 писал(а):
Andrey A в сообщении #1122543 писал(а):
В простых вида $2p+1$ (Софи Жермен) похоже имеем $k=p-1$.

Да, именно так. Насколько я помню, у Кнута такие числа по подобным причинам обзывались сильно простыми. (это если Вы рассматриваете отображение $x\to x^2$. Если другое - то не ведаю).

Upd
Да, именно $x\to x^2$. С $x^2-2$ всё вовсе не однозначно. И периоды короче конечно, что обнадеживает.

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

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



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

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


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

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