抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
著者らは,λ_1(L)が最短非零格子ベクトルの長さであり,det(L)が格子決定子である,大部分のO(√n)min→π_1(L),det(L) ̄1/n}においてノルムを有する格子L⊂R ̄nにおいて(非零)ベクトルを見つける2 ̄n/2+o(n)時間アルゴリズムを示した。Minkowskiは,λ_1(L)|ndet(L) ̄1/n,およびλ_1(L)≧Ω(√n)det(L) ̄1/nの格子が存在することを示し,このアルゴリズムは,決定要素(多対数因子まで)に対してできるだけ短いベクトルを見つける。この結果の背後にある主な技術的寄与は,arXiv:1412.7994からのアルゴリズムの新しい解析であり,これはより有用な問題を解決することが以前に知られている。これを達成するために,著者らは,λ_1(L)|ndet(L) ̄1/nの事実への部分的逆位として考えられる,(Dadush arXiv:1606.06913によって証明され,arXiv:1611.05979)によって証明される,ΔΨ逆Minkowski定理に決定的に依存する。以前に,そのようなベクトルを見つけるための最速の既知アルゴリズムは,[Liu,Wang,Xu,およびZheng,2011]による2 ̄.802n+o(n)時間アルゴリズムであり,それは実際に長さO(1)λ_1(L)を有する非ゼロ格子ベクトルを見つけた。時間2 ̄n/2+o(n)でこの長さを持つ格子ベクトルを見つける方法を示さないが,著者らは,このアルゴリズムがそのようなアルゴリズムの最も重要な応用(基底縮小)に対して十分であることを示した。特に,GamaとNguyenのスライド低減アルゴリズム[GamaとNguyen,STOC 2008]の修正版を示し,これは,暗号に関連する領域を含む,ほぼすべての領域における最短ベクトルアルゴリズムに対する時間長トレードオフを改善するために,上記のアルゴリズムと組み合わせることができる。【JST・京大機械翻訳】
