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

[Andrey A]

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

[Sonic86]

(Оффтоп)

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

[Andrey A]

В обратном порядке.

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$, иначе по любому модулю последовательность состоит из двоек или единиц.

[Sonic86]

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}$.

[Andrey A]

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$. Тоже надо поаккуратней.

[Sonic86]

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). Кому-нибудь это помогает?

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

[Andrey A]

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}$ (чтобы понадежней оказаться в цикле). Наверное я опять Вас запутал. Ну, из примера всё видно, нужно на практике попробовать.

[Sonic86]

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}$.

[Sonic86]

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

знак у $\pm 1$ должен зависеть чисто от $n$

К сожалению, нет: $g_n(x)$ не примитивный, разным его корням соответствуют разные знаки.

[Andrey A]

А, ну значит я не понял.

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

... и дальше все зависит от степени двойки в разложении $p-1$ на множители

Это да. Квадратичные вычеты - они же степенные. Помогает это в описании циклов? В Excel'е это труднопредставимо, и вообще на плоскости.

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

Т.е. $f(x)=x^2-2$ именно отсюда вылез?

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

[Sonic86]

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}$
Вин!
Отсюда следует истинность соотношения в полях вычетов по простому модулю, да и даже в кольцах вычетов по составному модулю.

[Andrey A]

А что знак при единице может быть любой мы и так знаем. Я с Вашего позволения позже буду вникать, но все равно здорово. Вот что подумал: для тестирования на простоту алгоритм явно не годится. В простых вида $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''$ по той же формуле.

[Sonic86]

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

В простых вида $2p+1$ (Софи Жермен) похоже имеем $k=p-1$.

Да, именно так. Насколько я помню, у Кнута такие числа по подобным причинам обзывались сильно простыми. (это если Вы рассматриваете отображение $x\to x^2$. Если другое - то не ведаю).
Для составных $m$ немного посложнее, но картина похожая - в кольце $\mathbb{Z}_m$ $\varphi(m)$ элементов, а их порядок - функция Кармайкла $\lambda (m)$ - она лишь немножко меньше функции Эйлера.

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

[Andrey A]

o.k.

[Andrey A]

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

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

Andrey A в сообщении #1122543 писал(а):
В простых вида $2p+1$ (Софи Жермен) похоже имеем $k=p-1$.

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

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