このブラウザは、JavaScript が無効になっています。JavaScriptを有効にして再度、お越しください。
ログイン
リポジトリトップ
リポジトリについて
登録手続き
よくある質問
検索
トップ
ランキング
詳細検索
全文検索
キーワード検索
タイトル
著者名 OR 著者ID
抄録・内容記述
アイテムタイプ
資源タイプ
出版年
インデックス
WEKO著者ID
AND
タイトル
著者名 OR 著者ID
抄録・内容記述
アイテムタイプ
資源タイプ
出版年
インデックス
WEKO著者ID
AND
タイトル
著者名 OR 著者ID
抄録・内容記述
アイテムタイプ
資源タイプ
出版年
インデックス
WEKO著者ID
AND
タイトル
著者名 OR 著者ID
抄録・内容記述
アイテムタイプ
資源タイプ
出版年
インデックス
WEKO著者ID
AND
タイトル
著者名 OR 著者ID
抄録・内容記述
アイテムタイプ
資源タイプ
出版年
インデックス
WEKO著者ID
AND
タイトル
著者名 OR 著者ID
抄録・内容記述
アイテムタイプ
資源タイプ
出版年
インデックス
WEKO著者ID
AND
タイトル
著者名 OR 著者ID
抄録・内容記述
アイテムタイプ
資源タイプ
出版年
インデックス
WEKO著者ID
AND
タイトル
著者名 OR 著者ID
抄録・内容記述
アイテムタイプ
資源タイプ
出版年
インデックス
WEKO著者ID
検索条件を追加
検索条件を追加
NIIsubject
NDC
NDLC
BSH
NDLSH
MeSH
DDC
LCC
UDC
LCSH
テスト
紀要論文 / Departmental Bulletin Paper【学内限定】
学位論文 / Thesis or Dissertation【学内限定】
報告書 / Research Paper【学内限定】
紀要論文 / Departmental Bulletin Paper_02
紀要論文 / Departmental Bulletin Paper_test
紀要論文 / Departmental Bulletin Paper_tes
紀要論文 / Departmental Bulletin Paper_03
学術雑誌論文 / Journal Article
紀要論文 / Departmental Bulletin Paper
会議発表論文 / Conference Paper
一般雑誌記事 / Article
会議発表用資料 / Presentation
学位論文 / Thesis or Dissertation
報告書 / Research Paper
図書 / Book
図書の一部 / Book
その他 / Others
DublinCore
Journal Article
Thesis or Dissertation
Departmental Bulletin Paper
Conference Paper
Presentation
Book
Technical Report
Research Paper
Article
Preprint
Learning Material
Data or Dataset
Software
Others
Learning Object Metadata
LIDO
Journal Article
Thesis or Dissertation
Departmental Bulletin Paper
Conference Paper
Presentation
Book
Technical Report
Research Paper
Article
Preprint
Learning Material
Data or Dataset
Software
Others
identifier
URI
fullTextURL
selfDOI
ISBN
ISSN
NCID
pmid
doi
NAID
ichushi
日本語
英語
フランス語
イタリア語
ドイツ語
スペイン語
中国語
ロシア語
ラテン語
マレー語
エスペラント語
アラビア語
ギリシャ語
朝鮮語
その他の言語
CC BY
CC BY-SA
CC BY-ND
CC BY-NC
CC BY-NC-SA
CC BY-NC-ND
自由記述
author
publisher
ETD
none
Language
日本語
English
インデックスツリー
インデックス
学習院大学
学位論文
博士(理学)
2021年度
Permalink : http://hdl.handle.net/10959/00005387
滑らかな整数の個数を近似するアルゴリズム
利用統計を見る
File / Name
License
abstract_O179.pdf
abstract_O179.pdf (108.18KB)
[ 25 downloads ]
ref_abstract_O179.pdf
ref_abstract_O179.pdf (115KB)
[ 14 downloads ]
タイトル(英)
Algorithms for approximating the number of smooth integers
アイテムタイプ
学位論文 / Thesis or Dissertation
言語
日本語
タイトル ヨミ
ナメラカナ セイスウ ノ コスウ オ キンジ スル アルゴリズム
著者
鈴木 耕二
/ スズキ コウジ
著者(英)
Koji Suzuki
抄録
小さな素因数のみを持つ正の整数を滑らかな整数と呼ぶ。滑らかな整数の研究は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
著者版フラグ
none
学位名
博士(理学)
学位名(英)
Doctor of Science
学位授与機関
学習院大学
学位授与機関(英)
Gakushuin University
学位授与年月日
2022-03-09
学位授与番号
32606乙第179号
コンテンツの利用について
・学習院大学学術成果リポジトリに登録されているコンテンツの著作権は、著者に帰属します。
・コンテンツの利用については、著作権法に規定されている私的使用や引用などの範囲内で行ってください。
日本語 |
English
新着情報
2023/1/19
『
学習院大学史料館紀要(25)
』(一部)を登録しました。
『
学習院大学史料館紀要(24)
』(一部)を登録しました。
『
学習院大学史料館紀要(23)
』(一部)を登録しました。
2023/1/17
『
學習院大學經濟論集59(3)
』
を登録しました。
『
學習院大學經濟論集59(2)
』
を登録しました。
2022/12/20
『
学習院大学史料館紀要(28)
』(一部)を登録しました。
『
学習院大学史料館紀要(27)
』(一部)を登録しました。
2022/12/1
『
学習院大学法学会雑誌58(1)
』(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(28)
』(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(26)
』(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(25)
』(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(22)
』(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(20-21)
』(一部)を登録しました。
2022/11/25
学位論文(法学)を登録しました。
・『
明治中期の民法教育・民法学習の展開についての実証的研究
』
2022/11/22
学位論文(史学)を登録しました。
・『
文化事業を通じた満洲経営の宣伝
』
2022/11/21
『
国際センター研究年報(8)
』を登録しました。
2022/11/18
『
言語 文化 社会(20)
』を登録しました。
2022/9/15
『
学習院大学史料館紀要(25)
』(一部)を登録しました。
学位論文(法学)を登録しました。
・『
差止裁判例に見る受忍限度の2つの機能 : 差止めの効果に関する覚書
』
2022/7/28
『
The Gakushuin Journal of International Studies(8)
』を登録しました。
2022/7/23
『
身体表象(5)
』
(一部)を登録しました。
『
学習院史学(25)
』(一部)を登録しました。
『
学習院史学(29)
』(一部)を登録しました。
2022/7/19
『
身体表象(5)
』
(一部)を登録しました。
『
身体表象(4)
』
(一部)を登録しました。
『
身体表象(3)
』
(一部)を登録しました。
『
身体表象(2)
』
(一部)を登録しました。
『
身体表象(1)
』
(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(29)
』(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(28)
』(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(25)
』(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(23)
』(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(22)
』(一部)を登録しました。
『
学習院大学大学院法学研究科法学論集(20-21)
』(一部)を登録しました。
2022/7/5
『
研究年報
(68)
』を登録しました。
『
学習院大学人文科学論集(30)
』を登録しました。
2022/7/1
『
学習院大学史料館紀要(28)
』(一部)を登録しました。
『
学習院大学史料館所蔵資料目録
』(一部)を登録しました。
『
学習院大学史料館叢書
』(一部)を登録しました。
『
百聞ハ一見ニ如カズ : 旧制学習院歴史地理標本室移管資料利用
』を登録しました。
2022/6/21
『
學習院大學經濟論集59(1)
』
を登録しました。
『
學習院大學經濟論集58(4)
』を登録しました。
『
學習院大學經濟論集58(3)
』を登録しました。
『
學習院大學經濟論集58(2)
』(一部)を登録しました。
『
学習院大学ドイツ文学会研究論集(26)
』を登録しました。
『
学習院大学ドイツ文学会研究論集(25)
』を登録しました。
2022/6/20
『
学習院大学教育学・教育実践論叢(7),(5)
』(一部)を登録しました。
学位論文(理学)を登録しました。
・『
滑らかな整数の個数を近似するアルゴリズム
』
・『
光反応を利用したFischer型銅 : カルベン錯体の新規調製法とこれを基盤とする触媒的分子変換手法の開発
』
・『
フェムト秒時間分解近赤外吸収分光法で研究した溶液中における芳香族化合物の光イオン化機構
』
・『
高安定フーリエ変換限界ピコ秒時間分解ラマン分光計の製作と金属ナノ粒子近傍の過渡分子種の時間分解分光研究
』
お知らせ
・学校法人学習院のリポジトリサイトです。平成29年6月より、JAIRO Cloud環境で公開となりました。(
2017.06.12 正式公開)
・
学習院大学学術成果リポジトリ規程
を制定しました(2022.4.1)
関連リンク
検索
■学習院大学関係
学習院大学図書館
学習院大学デジタルライブラリー
学習院大学東アジア学バーチャルミュージアム
学習院大学史料館の収蔵資料について
学習院大学研究者情報
researchmap
■リポジトリ関係
JAIRO Cloudとは
オープンアクセスリポジトリ推進協会
COUNTER
Powered by
WEKO