黄金比 ― 塩田研一覚書帳 ―
フィボナッチ数列
漸化式 an+2=an+1+an(n=0,1,2,...),a0=a1=1 で定められる数列 {an} をフィボナッチ数列と呼びます。 始めの数項は 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 で与えられ、自然現象のいろいろな場面に現れる有名な数列です。黄金比
n が十分大きければフィボナッチ数列の第 n 項は an ≒ 1√5{(1+√52)n+1} となりますので、n→∞ のとき隣接2項の比 (an+1/an) は (1+√5)/2 に収束します。正五角形の対角線
一辺の長さが 1 の正五角形の対角線の長さは黄金比 α=(1+√5)/2 になります。計算してみましょう。正二十面体の頂点座標
正多面体は5種類あります。正四面体、立方体、正八面体、正十二面体、正二十面体の5つです。 何か計算しようというときに、頂点座標が上手に与えられていると嬉しいものです。 正四面体の頂点は (0,0,0),(0,1,1),(1,0,1),(1,1,0) が使い易いです。立方体はいいとして、正八面体の頂点は (±1,0,0),(0,±1,0),(0,0,±1) が対称的で綺麗です。正二十面体の頂点は黄金比 α=(1+√5)/2 を使うと綺麗に書けるそうです: (0,±1,±α),(±α,0,±1),(±1,±α,0) ( 参考: Weblog on mebius.tokaichiba.jp 「正20面体の頂点座標の求め方」)正十二面体の頂点座標
正四面体の各面の重心を、隣り合う面の重心と結ぶと再び正四面体ができます。 正四面体は自己双対(そうつい)である、と言います。ユークリッドの互除法とフィボナッチ数列
フィボナッチ数列の隣接する2項を、 大きい方からユークリッドの互除法 ( division.html 参照 ) の入力にしてみましょう: r0=an,r1=an-1 すると rk=an-k ( k=0,1,2,⋯,n ) が成り立ちますので gcd(an,an-1)=1 ということも分かりますし、ユークリッドの互除法のループ回数は n ≒ logα(an) であることも分かります。加法連鎖
公開鍵暗号では、べき乗剰余や楕円曲線のスカラー倍などの計算が必要ですが、 このとき「反復2乗法」や「反復2倍法」というアルゴリズムを用いると、 サイド・チャンネル攻撃と呼ばれる攻撃を受ける恐れがあります。 CPU の発する電磁波を測定すると「2乗」や「2倍」のタイミングが読み取れるので、 そこから秘密鍵を読み取れる、という攻撃法です。黄金比と Hecke 作用素
保型形式の数値計算をしていると、Hecke 作用素の固有値としてよく黄金比に出会います。 重さ 2, 素数レベルの一変数保型形式の例を少し挙げておきましょう:参考: 定数係数線形漸化式
一般に、隣接 k+1 項の定数係数線形漸化式 an+k=ck-1an+k-1+...+c1an+1+c0an(n=0,1,2,...) の解は線形空間を成します。 ( {an}, {bn} が共に解であれば、 その一次結合 {san+tbn} も同じ漸化式を満たす、ということです。) 最初の k 項を決めれば数列が唯一とおりに決まりますので、 解の自由度は k、 すなわち、解の成す線形空間の次元は k です。