松田光司
格子点探索法における最近傍底点の周期性
Abstract:龍谷大学では3回生の必修科目として企業や研究所等で学外実習を行なっているが、この度筆者は1991年8月19日～9月13日までATR通信システム研究所（以下ATRという）においてこの学外実習を行なった。実習テーマは、格子点探索法と言われる素因数分解アルゴリズムの高速化に関するものである。
ATRでは従来より大きな値の合成数を素因数に高速分解する問題（素因数分解問題）の研究を行っている。この素因数分解問題は、公開鍵方式の一種であるRSA暗号に必要な鍵の長さの評価を行う為研究されており、鍵がどのくらい長ければ暗号は安全であるかという問題は、個々の素因数アルゴリズムに依存している。
ATRでも計算量の少ない新しい方式として、格子点探索法と呼ばれるアルゴリズムを提案している。しかしこの格子点探索法は現段階の基本的な方式では、世界レベルの計算量に追いつく事が出来なかった。そこでこの格子点探索法の計算量を更に減らす為に、最近傍底点と言う概念を新たに導入し、よりいっそうのアルゴリズムの高速化を計っている。
今回の実習では格子点探索法の解の探索を行う過程において、この最近傍底点が、周期性を持つかどうか確認する為の計算機実験を行い、更にそれをもとにした解析を行う。そして将来最近傍底点の概念を用いた格子点探索法のアルゴリズムを確立する為に基礎データを得る事を目的としている。