2026-03-14T00:06:48Z https://glim-re.repo.nii.ac.jp/oai

oai:glim-re.repo.nii.ac.jp:00005398 2023-10-27T00:23:16Z 1253:135:136:1409

滑らかな整数の個数を近似するアルゴリズム ナメラカナ　セイスウ　ノ　コスウ　オ　キンジ　スル　アルゴリズム Algorithms for approximating the number of smooth integers 鈴木, 耕二 47872 スズキ, コウジ Suzuki, Koji 学習院大学 Gakushuin University 博士（理学） Doctor of Science 小さな素因数のみを持つ正の整数を滑らかな整数と呼ぶ。滑らかな整数の研究はRamanujanの時代から続く深淵な数学的主題であると共に、素因数分解問題を主要な応用として持つことで広く知られる。本論文では滑らかな整数の個数を近似するアルゴリズムについて述べる。本論文の構成は以下の通りである。 　まず第1章において、近代的な素因数分解アルゴリズムを概観し、滑らかな整数の性質に関する既存研究について述べる。二次ふるい法、数体ふるい法など、最新の素因数分解アルゴリズムの計算効率は滑らかな整数の発生頻度によって決まる。このため、滑らかな整数の個数を近似する手法は素因数分解アルゴリズムの計算量推定、並びに素因数分解の困難さに安全性の根拠を置くRSA暗号の堅牢性評価において主要な役割を担う。滑らかな整数の個数を近似する手法の研究は、RamanujanがHardyに宛てた有名な手紙の中で言及して以来、100年を優に超える歴史を持つが、第1章では既存研究の中でも唯一高精度な推定値を与えることが可能なHildebrand-Tenenbaumの第一近似式を主に取り上げる。また、この第一近似式を滑らかな関数で近似した第二近似式についても言及する。 　次に第2章では、上記Hildebrand-Tenenbaumの第一近似式を改良することにより、従来手法よりも高速に計算可能な滑らかな整数の個数を近似するアルゴリズムを与える。このアルゴリズムの漸近的計算量は従来手法のものと同一ではあるが、数値計算の際に実質的な高速性を与えることが出来る。Hildebrand等の第一近似式を用いて滑らかな整数の個数の推定値を得るには、小さな素数の全列挙とこれらの素数に関連する複雑な方程式を数値的に解く必要がある。同章ではこの小さな素数の列挙無しに、この方程式の解を効率的かつ高精度に近似する新しい手法を与える。これにより、Hildebrand等の第一近似式を用いて推定値を算出する際の計算量を大幅に削減することが可能となる。同章では、従来手法と比較して新しいアルゴリズムは約4倍高速であることを示す数値実験結果を与える。 　更に第3章では、Hildebrand-Tenenbaumの第二近似式を改良することにより、多項式時間計算量を有する近似アルゴリズムを与える。Hildebrand等の第二近似式を利用して滑らかな整数の個数を推定する場合、数値積分を含む複雑な計算が必要となる。このため、近似精度に関わる顕著な問題が生じることが理由で、滑らかな整数の個数推定に上記第二近似式を利用することはこれまで行われて来なかった。第3章では、第2章で与えた近似手法の中間結果と、積分自体の計算に中点法を利用することにより、上記第二近似式の精度に関わる問題を解決する。Hildebrand等の第二近似式を利用することで大幅な計算量の削減が可能となり、第3章で与えるアルゴリズムの計算量は多項式時間計算量となる。この計算量評価は発見的な推定によるものではなく、理論的に確定的なものである。Hildebrand等の第一近似式を利用して推定値を計算する従来アルゴリズムの計算量は指数時間計算量であるため、新しいアルゴリズムの計算量は著しく小さなものと言える。 　また、第4章では擬似滑らかな整数の性質について述べる。限定された個数の比較的大きな素因数を持ち、それ以外は小さな素因数のみで構成される正の整数を擬似滑らかな整数と呼ぶ。擬似滑らかな整数は数体ふるい法などの高速化テクニックに利用され、その分布に関する研究は最新の素因数分解アルゴリズムの解析に必須なものと言える。ここでは、擬似滑らかな整数と滑らかな整数の比率に関する推定式を与える。この推定式に第2章および第3章で与えた近似アルゴリズムを併用することにより、高精度かつ高速に擬似滑らかな整数の個数を推定することが可能となる。 　最終章である第5章において、本論文の成果に関する結論を述べる。第2章および第3章で与えた滑らかな整数の個数を推定するアルゴリズム、および第4章で与えた擬似滑らかな整数と滑らかな整数の比率に関する推定式を利用することにより、二次ふるい法、数体ふるい法など、最新の素因数分解アルゴリズムの計算量、並びにそれらに高速化テクニックを併用した場合の計算量を高精度で推定することが可能となった。このことは現代の情報化社会の根幹を支えるRSA暗号の安全性評価に対して大きな意義を持つ。また、素因数分解問題とは独立に、滑らかな整数の研究はRamanujanの時代から続く主要な数学的主題であり、本論文の成果はこの研究に対して計算論的な側面から貢献を与えるものと言える。 application/pdf doctoral thesis 2022-03-09 VoR application/pdf application/pdf 32606乙第179号 https://glim-re.repo.nii.ac.jp/record/5398/files/abstract_O179.pdf https://glim-re.repo.nii.ac.jp/record/5398/files/ref_abstract_O179.pdf http://hdl.handle.net/10959/00005387 https://glim-re.repo.nii.ac.jp/records/5398 jpn open access