ルーカス数列の完全ガイド：定義・性質・高速計算アルゴリズムと素数判定・暗号応用

2025年11月25日 最終更新日時 : 2025年11月25日 エバープレイ編集部

イントロダクション — ルーカス数列とは何か

ルーカス数列（Lucas numbers）は、フィボナッチ数列と密接に関係する整数列の一つで、次のように定義されます。

  • L0 = 2, L1 = 1
  • 任意の n ≥ 2 に対して Ln = Ln−1 + Ln−2

最初の数項は 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123 … です。見てわかる通り、構造自体はフィボナッチ数列と同じ再帰ですが、初期値が異なるため得られる値がずれてきます。

解析的な表現と基本的性質

ルーカス数列はフィボナッチ同様に二次方程式 x2 − x − 1 = 0 の解 α, β（α = (1+√5)/2、β = (1−√5)/2）を用いて閉形式で表せます：

Ln = αn + βn

これに対してフィボナッチ数 Fn はビネの公式 Fn = (αn − βn)/√5 で与えられます。ルーカス数列とフィボナッチ数列の関係としてよく使われる等式に次があります：

  • Ln = Fn−1 + Fn+1
  • または Ln = 2·Fn+1 − Fn（Fn−1 = Fn+1 − Fn を代入）

行列の観点では、フィボナッチのQ行列 A = [[1,1],[1,0]] の n 乗の跡（trace）は αn + βn に等しく、つまり Ln = tr(An) になります。これにより線形代数的な解釈が可能です。

代表的な恒等式（よく使われるもの）

  • 二倍角型：L2n = Ln2 − 2(−1)n
  • 遺伝則的性質：Ln+m = LnLm − (−1)mLn−m（一般形の一つ）

上の等式はいくつかのアルゴリズム上での高速計算や合同式の解析に役立ちます。

計算方法とアルゴリズム（IT視点での実装）

ルーカス数 Ln を直接再帰で計算すると指数時間かかります。実務的には以下の高速化手法がよく使われます。

  • 行列累乗（指数べき乗法）: Q = [[1,1],[1,0]] に対して Qn を二分累乗（指数の二進法）で求めれば O(log n) の行列乗算回数で得られます。行列の各要素は定数個の乗算で更新されるため、複雑度は乗算コストに依存します。
  • 高速ダブリング法（fast doubling）: フィボナッチの高速ダブリングを用い、(Fn, Fn+1) を O(log n) の再帰で求め、そこから Ln = 2·Fn+1 − Fn によりルーカス数を得る方法。整数論や合同計算においては非常に実用的です。
  • 合同演算での計算: Ln mod m の形で計算する場合、全ての乗算・加算を mod m によって行えば、桁あふれを防ぎ性能も向上します。大きな n に対しては O(log n) のモジュラー乗算回数で済みます。

実装上の注意点として、得られる値の桁数は n に対して指数的（おおよそ αn）に増えるため、大きな n を精算するには任意精度整数ライブラリ（BigInt、GMP 等）が必要です。モジュラー演算であれば結果は m に制約されるため効率的です。

計算量（概観）

  • 単純な整数演算モデルで、乗算コストを M(b)（b はビット長）とすると、n 番目のルーカス数そのもの（完全な整数）を求めるには O(M(b) log n) の時間が一般的です（行列高速累乗／ダブリングを用いた場合）。
  • 合同演算 Ln (mod m) を求めるならば O(log n) 個のモジュラー乗算で済み、各乗算のコストは O(M(log m)) です。

暗号・数論・IT分野での応用例

ルーカス数列や一般化されたルーカス列（Lucas sequences Un(P,Q), Vn(P,Q)）は数論的性質を活かして様々な応用があります。主なものを挙げます。

  • 素数判定: Lucas 系列を用いたルーカス判定（Lucas probable prime tests）は Miller–Rabin 等と組み合わせて使われます。Baillie–PSW テストは Miller–Rabin と強ルーカス確率的素数判定（strong Lucas probable prime）を組合わせたもので、これまで知られている範囲では反例が発見されていません（ただし証明はされていない）。
  • ルーカス＝レマー（Lucas–Lehmer）テスト: メルセンヌ数 Mp = 2p − 1（p は素数）に対する高速な判定法で、シーケンス s0 = 4、sk+1 = sk2 − 2（mod Mp）を用います。Mp が素数であることの必要十分条件は sp−2 ≡ 0 (mod Mp) である、という有名な結果です。これは現在の大きなメルセンヌ素数探索で使われています。
  • 擬似乱数・ハッシュ: 厳密な意味でルーカス数列が一般的な暗号的擬似乱数生成器（CSPRNG）として用いられることは少ないですが、再帰列の周期性や合同算術の性質はハッシュ関数研究や検査アルゴリズムの設計を考える際の理論的素材になります。
  • アルゴリズム解析・生成器: 再帰系の解析や行列累乗の練習問題、教科的なサンプルとして情報工学の授業や競技プログラミングで頻繁に登場します。モジュラー算術での高速計算は実装上の良い練習になります。

実装の実例（擬似コード）

ここではフィボナッチの高速ダブリングを用いてルーカス数を求める簡単な擬似コードを示します（すべての演算を必要に応じて mod m で行えます）。

function fib_pair(n):
  if n == 0:
    return (0, 1)  // (F0, F1)
  (a, b) = fib_pair(floor(n/2))
  c = a * (2*b - a)        // F_{2k}
  d = a*a + b*b            // F_{2k+1}
  if n % 2 == 0:
    return (c, d)
  else:
    return (d, c + d)

function lucas(n):
  (Fn, Fnp1) = fib_pair(n)
  // L_n = 2*F_{n+1} - F_n
  return 2*Fnp1 - Fn

この方法は O(log n) の再帰深さで動作し、各ステップは定数個の乗算と加算で済みます。mod m を使えば実用的に非常に高速です。

実装上の注意点と落とし穴

  • 大きな n を扱う場合、満杯の整数ではオーバーフローするため BigInt/GMP 等が必須です。言語組込みの大整数型（Java の BigInteger、Python の int など）を利用してください。
  • 符号管理: Ln = 2·Fn+1 − Fn のような式を使う際、モジュラー演算下では差が負になる可能性があります。負数を正しい合同代表に直す処理（(x % m + m) % m）を忘れないでください。
  • 素数判定用途では、Baillie–PSW 等の複合テストを用いること。単独のルーカス確率判定だけで素数と断定すると擬似素数（疑似素数）に騙される可能性があります。

まとめ

ルーカス数列はフィボナッチ数列と同様の単純な再帰で定義されながら、数論的に興味深い性質を多く持ち、行列的・解析的表現も可能です。IT分野では特に高速計算アルゴリズム（行列累乗、ダブリング法）や素数判定アルゴリズム（Lucas 系列を利用した判定、Lucas–Lehmer）において実用的な役割を果たします。実装時は大きさ管理（大整数）やモジュラー演算の取り扱いに注意することが重要です。

参考文献

カテゴリー
IT
前の記事
宅録完全ガイド：初心者〜中級者のための機材選び・録音テクニック・ミックス・マスタリング・配信までNew!!
2025年11月25日
次の記事
ボーナストラックの全貌：歴史・種類・市場戦略とデジタル時代の展望New!!
2025年11月25日