2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Вычисление наименьшего Фибоначчи, кратного данному модулю.
Сообщение31.08.2018, 16:48 
Заслуженный участник
Аватара пользователя


21/11/12
1370
Санкт-Петербург
Обозначим точку золотого сечения $\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.

 Профиль  
                  
 
 Re: Вычисление наименьшего Фибоначчи, кратного данному модулю.
Сообщение01.09.2018, 05:49 
Модератор
Аватара пользователя


11/01/06
5560
Andrey A в сообщении #1335809 писал(а):
Обозначим точку золотого сечения $\Phi=\frac{1+\sqrt{5}}{2}$. Натуральное $m$ делит $ F_x$, причем $x$ - наименьшее из удовлетворяющих данному требованию, его и хочется найти.

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

 Профиль  
                  
 
 Re: Вычисление наименьшего Фибоначчи, кратного данному модулю.
Сообщение01.09.2018, 13:25 
Заслуженный участник
Аватара пользователя


21/11/12
1370
Санкт-Петербург
maxal, спасибо за ссылки. Нужно время.

 Профиль  
                  
 
 Re: Вычисление наименьшего Фибоначчи, кратного данному модулю.
Сообщение04.09.2018, 13:15 
Заслуженный участник
Аватара пользователя


21/11/12
1370
Санкт-Петербург
По поводу статьи 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 - да, знакомая.

 Профиль  
                  
 
 Re: Вычисление наименьшего Фибоначчи, кратного данному модулю.
Сообщение04.09.2018, 17:10 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вычисление наименьшего Фибоначчи, кратного данному модулю.
Сообщение28.09.2018, 11:11 
Заслуженный участник
Аватара пользователя


21/11/12
1370
Санкт-Петербург
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) пока не дают хороших результатов кроме прямого подсчета. Предложения приветствуются.

 Профиль  
                  
 
 Re: Вычисление наименьшего Фибоначчи, кратного данному модулю.
Сообщение02.02.2019, 01:04 
Заслуженный участник
Аватара пользователя


21/11/12
1370
Санкт-Петербург
Andrey A в сообщении #1335809 писал(а):
Вопрос факторизации $m$ ... выложен отдельно

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

 Профиль  
                  
 
 Re: Вычисление наименьшего Фибоначчи, кратного данному модулю.
Сообщение02.02.2019, 02:12 
Заслуженный участник
Аватара пользователя


21/11/12
1370
Санкт-Петербург
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}))$. Вопрос затратности.

 Профиль  
                  
 
 Re: Вычисление наименьшего Фибоначчи, кратного данному модулю.
Сообщение09.10.2020, 14:45 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

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



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

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


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

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