ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

おLんLんLんどはじまるよ.ykm

これは 高専 Advent Calendar 2018 24日目の記事です. ところで来週は僕の誕生日です.

なにを書こう

来週は僕の誕生日なんですが実を言うと, こんなの書いてないで学会論文を書かないといけないんですよ.
でも登録したからには意地でも何か書いてやろうと, しかしネタがありません.

脳裏に浮かんだものを以下に挙げます.

  • 趣味
  • 高専の話
    • 5 + 1 年過ごした所感
      -> 人間が通えるところじゃない(立地と寮をどうにかしてくれ)
    • 留学
      -> 個人的に聞いてくれ
    • 今年したこと
      -> 生きた
    • 編入
      -> 学力を持ち合わせていないため書けない


タイトルにもあるように, "LLL Lattice Basis Reduction Algorithm" について書きます.
趣味の暗号と大学編入で勉強するであろう線形代数の話の融合ということで.

ただしここで書く内容はあくまで僕が理解したものなので正しいという保証はできません. 論文を読むなどしてください.


LLL Lattice Basis Reduction Algorithm

直訳すると LLL格子基底削減アルゴリズム です(以降LLLと略記).

LLLは格子の基底を小さいものに変換するアルゴリズム(直訳まま)で, これ自体は暗号ではありませんがLLLを応用して暗号の解読等に使用されます. Coppersmith's attackやBohne-Durfee attackが有名ですね.


Lattice

Lattice(格子)は基底ベクトル B = {b1, b2, ...} の線型結合によって表すことができるベクトルの集合です.

L := {Σxb : x ∈ Z, b ∈ B}

たとえば基底ベクトル b1 = (1, 0), b2 = (0, 1) の線型結合 s*b1 + t*b2 は格子です.

ここで重要なのは, 同じ格子を張る基底ベクトルの組み合わせは1つだけではないということです.
例として, B1 = { (1, 0), (0, 1) } と B2 = { (2, 1), (1, 1) } は同じ格子を張ります.

以下に格子の例を示します.

f:id:ushiromiya3:20181201194849j:plain

f:id:ushiromiya3:20181201194902j:plain

赤と青で示された基底ベクトルが同じ格子を張っています. まさか!と思う人は確認してみてください.

今考えている格子の基底ベクトルを, 同じ格子を張り且つ小さなものへ変換をLattice (Basis) Redcution と言い, LLLはその一種となります.
上の図で言うと, 青の基底ベクトルが与えられて赤の基底ベクトルを導出するような感じです.


線形独立

一次独立ともいい, 線形結合でそれぞれに0を掛けた場合にのみ0ベクトルを作ることができるとき線形独立であるといいます.

ベクトルb1, b2の線形結合で  
s*b1 + t*b2 = 0  
となるs,  tが0だけのときb1, b2は一次独立である

s, tが0以外で0ベクトルが作れたら線形独立ではないということです.
たとえば

3*b1 - 2*b2 = 0 
3*b1 = 2*b2
3/2 * b1 = b2

b1の定数倍によってb2が得られることがわかります. というわけで基底にはなり得ないわけです. 線型独立かどうかは基本変形行列式求めて確認しますよね.


LLL process

projectionという関数を定義します.

proj(u, v) := <u, v> / <u, u> * u ; <x, y> is dot-product with x and y

あとはGram-schmidtの直交化を応用していけばいいです. はい. Lenstra–Lenstra–Lovász lattice basis reduction algorithm - Wikipedia

基底が削減されているとする条件を満たしているか, とか満たしていなければswapしてまた直交化...みたいな感じでやっていきます.

全部マルチとスマブラが悪いので.. ちゃんと解説できなくてすまんという顔をしています.


最後に

時間が取れなくなりました. 悲しいね.

鋼の錬金術師 FULLMETAL ALCHEMIST(AmazonPrimeVideo)
54話の終わり方が好きです. EDの入り方がかっこよすぎる. 見てください.


Bibliography


あわせて読みたい


Mein Geburtstag ist bald

Für mich kaufen etwas bitte 翻訳使うな
Wunschzettel