Вычисление наименьшего Фибоначчи, кратного данному модулю.

[Andrey A]

Обозначим точку золотого сечения $\Phi=\frac{1+\sqrt{5}}{2}$. Натуральное $m$ делит $ F_x$, причем $x$ - наименьшее из удовлетворяющих данному требованию, его и хочется найти. Идея простая: дробь $\dfrac{F_x}{F_{x-1}}$ является хорошим приближением $\Phi$, и существует вещественное $\alpha $ такое, что $\dfrac{m}{\alpha }=\Phi$, то есть $\Phi=\dfrac{m}{\alpha } \approx \dfrac{F_x}{F_{x-1}}$. Отсюда $ \alpha =\dfrac{m}{\Phi} \approx \dfrac{mF_{x-1}}{F_x}=\dfrac{F_{x-1}}{F_x/m}$. В знаменателе последней дроби целое число (обозначим его $q_m$ - число, "домножающее" $m$ до наименьшего Фибоначчи), сама дробь несократима, поскольку несократима $\dfrac{F_x}{F_{x-1}}$ и должна входить подходящей дробью в разложение $\alpha$. Тут требуется строгое доказательство, замечу только что $\dfrac{F_{x-1}}{q_m}$ - "самая точная" дробь указанной последовательности, т.е. стоящая перед наибольшим знаком. Уже по этому признаку можно бы вести разложение до $F_{x-1}$ в числителе, и задача решена. Однако, такой путь слишком затратен, гораздо проще вычислять $q_m$ и далее $x\approx \log (m\sqrt{5}\cdot q_m)_{\Phi}$, воспользовавшись формулой Бине. Дело не только в том что $F_{x-1}\gg q_m$. Важно что $F^2_{x-1}\equiv \pm 1 \mod F_x$ (из общих свойств Фибоначчи), а значит и по $\mod q_m$. Таким образом $q_m$ - палиндром, а для вычисления палиндрома достаточно полупериода (подробней об этом здесь, глава "Палиндромы"). Приведу пример для $m=912$:
$\dfrac{912}{\Phi}=563,1,1,1,4,1,55,1,4,1,1,1,2038,...$ вот эта симметричная структура, "зажатая" между двумя большими знаками, которые отбрасываем за ненадобностью и есть $q_m$. Вычисления в данном случае занимают $6$ шагов: $1,2,3,14,17,949;\ 17\cdot (14+949)=17\cdot 963=q_{912};$ $\log (\sqrt{5}\cdot 17\cdot 963\cdot 912)_{\Phi}\approx 36=x;\ F_{36}\vdots \ 912$.
Преобразуем теперь $\alpha =\dfrac{m}{\Phi}=\dfrac{2m}{1+\sqrt{5}}=\dfrac{m(\sqrt{5}-1)}{2}=\dfrac{-m+m\sqrt{5}}{2}$. Для практического применения удобна следующая схема в виде таблицы:

$$\begin{vmatrix} n\\ \\ a_n\\ b_n\\ z_n\\ \\ q_n \end{vmatrix}\left.\begin{matrix} 0 & 1 & 2 & ... & n+1\\ & & & & \\ - & \left \lfloor \alpha \right \rfloor & \left \lfloor 1/(\alpha-a_1) \right \rfloor & ... & \left \lfloor (-b_n+(-1)^n \cdot m\sqrt{5})/z_n \right \rfloor\\ m & 2a_1+m & a_2z_1+b_1 & ... & a_{n+1}z_n+b_n\\ 2 & 2(a_1^2+a_1m-m^2) & a_2(b_1+b_2)+z_0 & ... & a_{n+1}(b_n+b_{n+1})+z_{n-1}\\ & & & & \\ 0 & 1 & a_2 & ... & a_{n+1}q_n+q_{n-1} \end{matrix}\right|$$

Тут $a_n$ - знаки непрерывной дроби, $q_n$ - знаменатели соответствующих подходящих дробей, остальные переменные можно считать вспомогательными. Вычисления ведутся до состояния $b_{n-1}+b_n=0$ или $z_{n-1}+z_n=0$. В первом случае $q_m=q_{n-1}(q_{n-2}+q_n)$ как в примере (нечетный период), во втором $q_m=q^2_{n-1}+q^2_n$ (четный период), и $x\approx \log (m\sqrt{5}\cdot (q^2_{n-1}+q^2_n))_{\Phi}$. На этом можно бы и закончить, но хочется еще порассуждать. О существовании квазипростых относительно $F_{x}$ читать не приходилось, но и доказательства не встречал что $m \equiv \pm 1 \mod x$ свидетельствует о простоте $m$. Если есть инф. на русском языке, буду признателен. Так или иначе, если $m$ простое, данные дискретного логорифма и $F_{x}$ будут совпадать. Бывают ли квазипростые относительно разных алгоритмов - тоже интересный вопрос. Это всё к тому, что описанная процедура работает не только с рядом Фибоначчи, но и с другими последовательностями вида $1,c,...,f_{n+1}=c\cdot f_n+f_{n-1}$. Остановлюсь подробней на случае $c=2$ (начальные члены $1,2,5,12,29,70,...$). Отношение соседних членов стремится к точке $1+\sqrt{2}$, общий член $f_n=\dfrac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{\sqrt{8}}$ и по аналогии с Фибоначчи $f^2_{n-1}\equiv \pm 1 \mod f_n$, из $a\mid b$ следует $f_a\mid f_b$. Делимость на простые также по аналогии, только не по $\mod 5$, а по $\mod 8$, что важно: простое $p$ вида $8k \pm 1$ делит $f_{p-1}$, простое $p$ вида $8k \pm 3$ делит $f_{p+1}$. Для вычисления наименьшего члена, кратного данному модулю $m$ разлагаем $\beta =\dfrac{m}{1+\sqrt{2}}=-m+m\sqrt{2}$ в непрерывную дробь, и похожая таблица:

$$\begin{vmatrix} n\\ \\ a_n\\ b_n\\ z_n\\ \\ q_n \end{vmatrix}\left.\begin{matrix} 0 & 1 & 2 & ... & n+1\\ & & & & \\ - & \left \lfloor \beta \right \rfloor & \left \lfloor 1/(\beta -a_1) \right \rfloor & ... & \left \lfloor (-b_n+(-1)^n \cdot m\sqrt{2})/z_n \right \rfloor\\ m & a_1+m & a_2z_1+b_1 & ... & a_{n+1}z_n+b_n\\ 1 & a_1^2+2a_1m-m^2 & a_2(b_1+b_2)+z_0 & ... & a_{n+1}(b_n+b_{n+1})+z_{n-1}\\ & & & & \\ 0 & 1 & a_2 & ... & a_{n+1}q_n+q_{n-1} \end{matrix}\right|$$

Остальное без изменений, $x\approx \log (m\sqrt{8}\cdot q_m)_{(1+\sqrt{2})}$. Из четырех последовательностей таблицы единственная возрастающая и самая затратная для вычислений $q_n$ является функцией от $a_n$ и может вычисляться позже с остальных. Значит можно запустить объединенный алгоритм до наименьшего полупериода и только для него вычислять $q_n$. При тестировании на простоту отрицательного результата достаточно одного. Немного статистики. Расчет $F_x$ для $900<m<999 $ потребовал на каждое $m$ в среднем $72$ знака полупериода, при объединенном алгоритме - 47 знаков. При том что числа для вычисления $q_n$ понадобились значительно меньшие, а можно ведь запустить и тройной алгоритм, и более того :)
Вопрос факторизации $m$ в свете сказанного выложен отдельно https://dxdy.ru/post1335397.html#p1335397.

[maxal]

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

Обозначим точку золотого сечения $\Phi=\frac{1+\sqrt{5}}{2}$. Натуральное $m$ делит $ F_x$, причем $x$ - наименьшее из удовлетворяющих данному требованию, его и хочется найти.

См. A001602 и статью
http://www.fq.math.ca/Scanned/1-2/vinson.pdf

[Andrey A]

maxal, спасибо за ссылки. Нужно время.

[Andrey A]

По поводу статьи http://www.fq.math.ca/Scanned/1-2/vinson.pdf Индекс наименьшего Фибоначчи $(u_n)$ кратного $m$ определяется в ней как функция $f(m)$, и рассматривается период последовательности остатков деления $u_0,u_1,u_2,u_3,... \mod m$. Длина периода $s(m)$ оказывается кратна $f(m)$, то есть существует целое $t(m)=\dfrac{s(m)}{f(m)}$. Исследованию $t(m)$ и посвящена статья, а также следствиям из известного факта: $u^2_{f(m)-1}\equiv \pm 1 \mod u_{f(m)}$. Наблюдение само по себе ценное, но я не понял к сожалению пристального внимания автора к $t(m)$ и какие взять оттуда содержательные выводы. Функция $t(m)$ принимает три значения: $1,2,4.$ Если выписывать не остатки $u_n\mod m$, а абсолютно наименьшие вычеты и фиксировать период, не обращая внимания на знаки, то для любого $m$ он оказывается равен ровно $f(m)$, причем в "зеркальном" движении: $0 \rightarrow 0 \leftarrow 0 \rightarrow 0 \leftarrow 0\ ... $ правильнее всё-таки называть это полупериодом. Подобная нечувствительность к знакам наводит на мысль о том, что рассматривать следовало бы расстояния не между Фибоначчи, а между квадратами Фибоначчи. Тогда находим: $u^2_{f(m)+n} \equiv u^2_n\cdot (-1)^{f(m)} \mod m$ для любого $n$ и, как следствие: если $a+b=f(m)$, то $u^2_a \equiv u^2_b\cdot (-1)^{f(m)} \mod m.$ Вместо $f(m)$ можно брать везде $kf(m)$, поскольку период ничем не хуже. Последовательность $u^2_0,u^2_1,u^2_2,u^2_3,... \mod m$ имеет, кстати, ту же длину периода. О том, как вычислить $f(m)$ или $s(m)$ в статье не сообщается, да и цели такой автор перед собой не ставил. Если не считать, конечно, последовательное вычисление остатков по $\mod m$ до первого встречного нуля, где количество итераций равно самому результату (правильнее будет сказать тогда не "вычислить", а "посчитать" $f(m)$ :) В алгоритме из темы отношение $n/f(m)$ убывает с ростом $m$. Последовательность A001602 - да, знакомая.

[Andrey A]

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

и, как следствие: если $a+b=f(m)$, то...

Upd лучше не так.
$a \equiv b \mod f(m) \Rightarrow u^2_a \equiv u^2_b \cdot (-1)^{a-b} \mod m.$
Обратное неверно: $u^2_{47} \equiv u^2_{17} \mod 77$, но $f(77)=40$ и $47\not\equiv \pm 17 \mod 40.$

[Andrey A]

Upd 28.09

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

В алгоритме из темы отношение $n/f(m)$ убывает с ростом $m$.

Может это и неверно. В грубом приближении итераций раз в $5-6$ меньше в сравнении с прямым подсчетом за исключением граничных случаев. Плюс затраты на вычисление $q_m$. Жаль. Несколько слов по поводу сравнения $u_X^2\equiv 1 \mod m$ (1). Оставим терминологию из статьи: $u_n$ -- $n$-ый член ряда Фибоначчи, $f(m)$ -- номер наименьшего ненулевого Фибоначчи, кратного $m$. Тривиальные решения $X=1,-1,2,-2$ верны для любого $m$, а значит и по $\mod f(m)$ если оно четно, или в противном случае по $\mod 2f(m)$, что следует из вышесказанного. Таким образом для простых $m$ наименьшее $X=f(m)-2$ или $2f(m)-2$, но для составных модулей могут быть меньшие решения. Положим $m=m_1m_2,\ m_1 \mid u_A, m_2 \mid u_B$, где $A,B$ - наименьшие четные индексы, отвечающие заданным условиям, $(m_1, m_2)$ взаимно просты. То есть $A=f(m_1)$ или $2f(m_1)$ если последнее нечетно, то же для $B$. Для четных аргументов выполняется тождество $u_Au_B=u^2_{\frac{A+B}{2}}-u^2_{\frac{A-B}{2}}$ (2). Если $\left | A-B \right |=2$ или $4$, то решение сравнения (1) уже содержится в тождестве (2): $X=\frac{A+B}{2}$. Если $\left | A-B \right |>4$, и разрешимо хотя бы одно из уравнений $Ax-By=\pm 2$ (3), $Ax-By=\pm 4$ (4), то, подставляя в тождество (2) $A\rightarrow Ax,\ B\rightarrow By$, получаем $X=\frac{Ax+By}{2}$. Условия разрешимости уравнений (3),(4) известны: $\gcd (A,B)=2,4$. При наличии других общих делителей наименьшим решением, как и для простых m, по-прежнему остается $X=f(m)-2$ или $2f(m)-2$. Из взаимной простоты $(m_1, m_2)$ еще не следует того же для пары $\left ( f(m_1), f(m_2) \right )$, важно об этом помнить. Дельный совет для быстрого поиска наименьших решений уравнений (3),(4). Если $A=4a,\ B=4b$, то решение уравнения $ax-by=\pm 1$ следует из разложения дроби $a/b$ без последнего знака, тут всё как обычно, $X$ четно. Если $A=2a,\ B=2b$ при вз. простых $(a,b)$, следует различать два случая в зависимости от величины $a_n$ (последнего знака дроби $a/b$):
1) $a_n>2$. Так же берется дробь без последнего знака, $X$ нечетно.
2) $a_n=2$. Берется дробь без двух последних знаков, $X$ четно. Пример для $m=574663=1103\cdot 521$. $f(1103)=48=2\cdot 24;\ f(521)=26=2 \cdot 13$. $24/13=1,1,5,2$. Отбрасывая два знака, получаем $1,1=2/1;\ (48\cdot 1+26\cdot2)/2=50$. $u^2_{50}\equiv 1 \mod 574663$ наименьшее решение. Отсюда видно что, получив неким способом пару квадратов одной четности $u^2_p\equiv u^2_q \mod m$, в целях факторизации следует проверять не только $\gcd (m,u_p-u_q)$, но и $\gcd (m,u_{p-q})$. В данном случае $u_{50}+1=574663 \cdot 21902$, но $\gcd(574663,u_{48})=1103;\ \gcd(574663,u_{52})=521$. Единица в этом смысле вдвойне информативна, поскольку дружит как с четными так и с нечетными Фибоначчи.
Сравнение $u_X^2\equiv -1 \mod m$ разрешимо не для любых модулей. Тут $A,B$ нечетны, вместо разностей имеем суммы квадратов. Остальное по аналогии. Попытки получить алгоритмически некоторое решение сравнения (1) пока не дают хороших результатов кроме прямого подсчета. Предложения приветствуются.

[Andrey A]

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

Вопрос факторизации $m$ ... выложен отдельно

P.S. Искать делители $m$ выше описанным способом не очень целесообразно, это понятно. Неожиданно хороший результат, однако, дает пошаговое вычисление $\gcd (m,(b_n+z_n),(b_n+b_{n-1}))$ в объединенном варианте алгоритма — подобно тому, как это делается в $\rho$-алгоритме Полларда. О причинах догадываюсь смутно, но не думаю что это иллюзия хотя бы потому что такая факторизация всегда результативна. Тестирование приветствуется.

[Andrey A]

PS PS. Всё-таки так: $\gcd (m,(b_n+z_n))$, $\gcd (m,(b_n+b_{n-1}))$ или $\gcd (m,(b_n+z_n)(b_n+b_{n-1}))$. Вопрос затратности.

[Andrey A]

Табличка Excel для вычисления наименьшего Фибоначчи, кратного заданному $m$. Поле ввода помечено красным.