Babaiのアルゴリズムは失敗することがある

【 Babaiのアルゴリズムは失敗することがある 】

ラティスには、「ラティス問題」と言われるものがあります。

このセッションでは、Shortest vector problem (SVP)とClosest vector problem (CVP)と呼ばれる、二つの「ラティス問題」を紹介します。

Shortest vector problem (SVP)は、ラティスの基底が与えられた時、その基底で張られるラティスで、最も距離が近い格子点を求めよという問題です。

Closest vector problem (CVP)は、ラティスの張る平面上に、ある点を放り込んだ時、その点に一番近い格子点を求めよという問題です。

正規直交基底のように、格子点が縦横に一コマずつ動いてラティスを作るのなら、この問題を解くのは、直観的には簡単です。ただ、基底ベクトルの整数倍の和がジグザグに動いて、ラティスが作られるのなら、見通しは悪くなります。その上、ラティスの次元n が大きなものになると、この問題を解くのは、急に難しくなります。

ここでは、二次元のラティスで、Closest vector problem (CVP)を考えてみましょう。

ラティスの基底を a, b 、格子点に近い点をx とし、それぞれの成分を(a1,a2),  (b1,b2), (x1,x2)としましょう。

ここで、

　　m(a1, a2) + n(b1, b2) = (x1, x2)

という関係が成り立っているとします。

　　m・a1 + n・b1 = x1

　　m・a2 + n・b2 = x2

ですので、これを m, n について解くことができます。

ただ、これを解いても、m, n が整数になる保証はありません。そこで、この解 m, n に一番近い整数を M, N とします。

この時、M, N は整数で、a, b は基底ですので、

　　M(a1, a2) + N(b1, b2) 

は格子点になります。これが点(x1, x2)に一番近い格子点です。

こうしたアプローチを「Babaiのアルゴリズム」と言います。

残念ながら、このアルゴリズム、失敗するんです。うまくいくときもあるんですが。

整数とは限らない m, n から、整数 M, N を作ったあたりが、怪しいですね。

−−−−−−−−-----

動画 「ラティス問題」を公開しました。 https://youtu.be/RF3qZPLw6Mo?list=PLQIrJ0f9gMcMOiLc6py4lKrk3xAG_g0FH

この動画のスライドのpdf https://drive.google.com/file/d/1RbZ9_TEAGjeyVhwO4NS-Tp9WcaOp88be/view?usp=sharing 関連blog 「Babaiのアルゴリズムは失敗することがある」 https://maruyama097.blogspot.com/2022/08/babai.html このセミナー「暗号技術の現在」のまとめページ https://www.marulabo.net/docs/cipher2/ セミナーの申し込み https://cipher2.peatix.com/view