fib循环节到底是咋回事？？？

· · 个人记录

要求广义fib数f_n=af_{n-1}+bf_{n-2}模素数p下的循环节长度，其实我们关心的无非是递推矩阵A=\displaystyle\begin{bmatrix}a&b\\1&0\end{bmatrix}的幂的循环节长度，也就是说最小的k满足A^k=I。A的特征多项式，容易算出它是z^2-az-b，如果它是最小多项式，我们就要求最小的k满足z^k\bmod{z^2-az-b}=1。如果它不是最小多项式，我们用求根公式进行因式分解，判断两个一次因式是否是最小多项式即可。需要扩域啊啊啊啊啊啊啊啊。

那么问题是如何求最小的k满足z^k\bmod{z^2-az-b}=1。我们可以分解后进行crt。

考虑如何求最小的k满足z^k\bmod{z-c}=1，其中c在该素域中存在。这其实是说求c的阶，它必然是p-1的因数，所以只需分解p-1，复杂度\tilde{O}(v^\frac{1}{5})，使用泼辣的肉则是O(v^\frac{1}{4})。

对于一般的情况，二次方程有两个解c_1,c_2=\frac{a+\sqrt{\Delta}}{2},\frac{a-\sqrt{\Delta}}{2}，这里根号可能开不出来，所以要麻烦一点。

Lemma 无论a,b是否存在，(a+b)^p\bmod{p}=a^p+b^p\bmod{p}。

Proof 二项式定理，然后注意到p\mid \binom{p}{k}，若1<k<p。

那么我们知道\left(\frac{a+\sqrt{\Delta}}{2}\right)^p=\frac{a}{2}+\Delta^{\frac{p-1}{2}}\frac{\sqrt{\Delta}}{2}。由于\Delta没有平方根，根据欧拉准则，\Delta^\frac{p-1}{2}=-1，所以也就是c_1^p=c_2。那么肯定也有c_2^p=c_1，所以c_1^{p^2}=c_1，c_1的阶就是p^2-1=(p+1)(p-1)的因数，分别分解这俩数再乘起来即可。

另一个观察是c_1^{p+1}=c_1c_2=-b，后一个等号是韦达定理。所以可以把上面的p-1改成-b的阶。如果b,p都是常数，这可能可以给出很小的循环节长度上界；或者b=1时，无论p是多少，循环节长度都是O(p)的。

然而也可能是重根，重根就没法crt了。问题是求最小的k满足z^k\bmod{(z-c)^2}=1，那么经典地先化简模数，改成满足(z+c)^k\bmod{z^2}=1。那么我们先找到一个能消去一次项的k_0，再对此时的常数项求阶即可。[z^1](z+c)^{k_0}=\binom{k_0}{1}=k_0，所以我们取k_0=p就取的很好，此时的常数项也不用算，根据上面的lemma它就是c=\frac{a}{2}。

总之我们就在\tilde{O}(v^\frac{1}{5})时间内求出了fib数模素数的循环节长度，非常好对吧！！！