Optimal DeepLLL系格子基底簡約の停止性の証明と計算量評価

小田川 拓利

（指導教員：縫田 光司 准教授／数理情報第1研究室）

研究概要

格子の基底の簡約のためにDeepLLLやそれをもとにしたアルゴリズムが用いられてきたが，入力の整数条件を除いた場合には，パラメータδが1の時の停止性が示されていなかった．本研究では，δ=1の場合の停止性を証明し計算量評価を行った．

証明の概略図

卒論の感想

既存研究を拡張することができたという実感で，達成感を得ることができました．大変お世話になった先生や研究室の方々に感謝申し上げます.