crypto-writeup-public

リュカ数列

フィボナッチ数列リュカ数 legendre記号

https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%A5%E3%82%AB%E6%95%B0%E5%88%97

definition

$x^2 - ax + b = 0$ という $a\ne0, b\ne0$ の2次方程式があって、2つの解を $\alpha, \beta$ とする

解の公式から

$\Delta = a^2 - 4b$ とおいて↓がなりたつ

$\alpha = \frac{a + \sqrt{\Delta}}{2}$

$\beta = \frac{a - \sqrt{\Delta}}{2}$

リュカ数列 $U_n(a,b), V_n(a, b)$ (2つある！）はそれぞれ↓で定義される数列である

$U_n(a, b) = \frac{\alpha^n - \beta^n}{\alpha - \beta}$

$V_n(a, b) = \alpha^n + \beta^n$

例

$U_n(1, -1) = {0, 1, 1, 2, 3, 5, 8, \dots }$ でありフィボナッチ数列

$V_n(1, -1) = {2,1,3,4,7,11,18,\dots}$ でありリュカ数の列

性質

$U_0(a, b) = 0$

$U_1(a, b) = 1$

$V_0 = 2$

$V_1 = a$

$U_n(a, b) = aU_{n-1} - bU_{n-2}$

$V_n(a, b) = aV_{n-1} - bV_{n-2}$

なんか計算するとそうなるやつ

$V_{2n} = V_n^2 - 2b^n$

$V_{2n-1} = V_nV_{n-1} - ab^{n-1}$

$V_{2n+1} = aV_n^2 - bV_nV_{n-1} - ab^n$

$V_n^2 = \Delta U_n^2 + 4b^n$

$2V_{n+m} = V_nV_m + \Delta U_n U_m$

$2b^m V_{n-m} = V_n V_m - \Delta U_n U_m$

$V_n(V_k(a, b), b^k) = V_{nk} (a, b)$

割り算関係

$m|n \to U_m | U_n$

$n = (2k + 1)m \to V_m | V_n$

$p$ が奇素数 → $U_p \equiv \left( \frac{\Delta}{p} \right), V_p \equiv a \mod p$ 。これはlegendre記号