縦か横か？
【 縦か横か？ 】
基底 b1, b2, ... , bn から作られるラティスを、次のように表します。
L = L(b1, b2, ... , bn)
ラティス𝐿は、複数の基底を持ちます。 もう一つの基底を b1', b2', ... , bn' とすれば、
L = L(b1, b2, ... , bn) = L(b1', b2', ... , bn')
この時、基底 (b1, b2, ... , bn )と基底 (b1', b2', ... , bn')は、𝐿について「等価」であると呼んで、次のように表しましょう。
(b1, b2, ... , bn ) ⇔ (b1', b2', ... , bn')
ラティスの基底が等価であることを、行列を使って表現することもできます。
基底を構成するそれぞれのベクトル b1, b2, ... , bnを列ベクトルで表し、それを並べて行列を作ります。ラティスの基底は、𝑛×𝑛の行列Bで表現されます。
L = L(B)
この時、行列Bに次のような操作を加えて新しい行列を作ります。
1. 元の行列Bの列v_iをv_jと交換したものをB1とします。
2, 元の行列Bの一列v_iに−1に掛けたものをB2 とします。
3. 元の行列Bの一列v_iをv_i + k・v_jにかえたものをB3とします。
この時、
L(B) = L(B1) = L(B2) = L(B3)
であることがわかります。
要するに、B1もB2もB3もラティスLの基底になっています。先の行列への操作によって、ラティスの基底としての等価性は保たれています。
この操作、見たことありませんか？
「掃き出し法」とか「ガウスの消去法」というのと、基本的に同じものです。
僕が気になったのは、別のことです。
前に、「Babaiのアルゴリズム」を紹介した時、ラティスの基底を「行ベクトル」の集まりとして扱ってきました、ただ、今回は、ラティスの基底を「列ベクトル」の集まりとして扱っています。
縦と横、ベクトルの向き、どっちがいいんでしょう？
どっちでもいいんです。
−−−−−−−−-----
動画 「同じラティスを生成する複数の基底」を公開しました。
この動画のスライドのpdf
関連blog 「縦か横か？」
このセミナー「暗号技術の現在」のまとめページ
セミナーの申し込み
コメント
コメントを投稿