安定化手法に基づく計算履歴法とLLLアルゴリズムへの適用 (数式処理とその周辺分野の研究)

Abstract

LLLアルゴリズム(以下, アルゴリズムLLL)によりガウス既約基底を求めることは, 最短ベクトル問題への基本的なアプローチである. 最短ベクトル問題とは, n個の線形独立なベクトルai, . . . , a_{n}in mathrm{K}^{n}が与えられ, これらのベクトルで生成される格子の中で, ユークリッドノルムで0以外の最短なベクトルを求める問題である. また, ガウス既約基底はユークリッドの互除法に類似した操作で計算できる. しかし, その計算に浮動小数点近似を用いると, 不安定性の問題がしばしば生じる. すなわち, 入力行列の各係数の精度桁を上げても, その出力の行列は, 正確なガウス既約基底に収束するとは限らない. 本論文では, K. ShirayanagiとM Sweedlerが提案した安定化手法と安定化手法に基づく計算履歴法(以下, ISCZ法)をアルゴリズムLLLに適用し, ガウス既約基底を浮動小数点で計算するための安定なアルゴリズムを実現する. さらに, いくつかの例に対して計算機実験を行い, そのブルゴリズムの安定性を実証する. これによって, 安定化手法の有効性及びISCZ法の有効性を示す. また, 白柳を中心に従来のISCZ法に対するNew ideaを提案した. このNew ideaの有効性についても示す.