| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-07-20 14:20 近似GCD問題に対する改良アルゴリズム ○高安 敦・國廣 昇（東大）  ISEC2012-35 SITE2012-31 ICSS2012-37 EMM2012-27 |
|
| 抄録 | （和） | 本論文では，整数の倍数の近似値が複数個与えられたときにその公約数を求める多変数のapproximate common divisor problem(ACDP)の解析を行った． これまでに格子を用いたCoppersmithの理論に基づいてACDPの多項式時間アルゴリズムが提案されてきた． 2001年にHowgrave-Grahamは与えられる近似値が2つの場合に，誤差が小さいときのACDPの多項式時間アルゴリズムを提案した． ついで，2011年にCohn, Heningerはこの手法を一般に複数個の近似値が与えられた場合に拡張した． 本論文では部分問題として誤差のない厳密な倍数が1つ与えられるpartially approximate common divisor problem(PACDP)のみについて解析をしている． 我々は一般に複数個の近似値が与えられた場合のPACDPに対してCohn, Heningerのアルゴリズムを改良したアルゴリズムを提案する． PACDPでは，Cohn, Heningerは不等式$ (\alpha _1+\cdots+\alpha _n)/n<\beta^{(n+1)/n}$を満たすとき，多項式時間で解けることを示した． 我々はCohn, Heningerのアルゴリズムから格子の構成を変更することによってこの条件を$ \sqrt[n]{\alpha _1 \cdots \alpha _n}<\beta^{(n+1)/n}$に改善した． この不等式の左辺はCohn, Heningerが$ \alpha _1,\ldots,\alpha _n$の相加平均としたところを我々のアルゴリズムでは$ \alpha _1,\ldots,\alpha _n$の相乗平均となっており， 我々のアルゴリズムはより広いクラスの問題に適用可能である． さらにHowgrave-Grahamのアルゴリズムから多変数への拡張を考えたときに多項式時間で解けるべき条件を考えると，我々のアルゴリズムの条件のほうがCohn, Heningerのものより自然な条件となっている． |
| （英） | In this paper, we analyze multivariate approximate common divisor problem(ACDP), given approximate multiples of the integer and we recover the integer. So far, via lattice based Coppersmith's theorem, the polynomial time ACDP algorithms have been proposed. In 2001, Howgrave-Graham proposed the polynomial time algorithms for ACDP as long as the tolerated errors are sufficiently small, when given two approximate multiples. In 2011, Cohn and Heninger gave the multivariate generalization of Howgrave-Graham's algorithm, when given plural approximate multiples. In this paper, we analyze only partially approximate common divisor problem(PACDP) when given one exact multiple of the integer. We propose the improved polynomial time algorithm by Cohn and Heninger when given plural approximate multiples. Cohn and Heninger revealed that PACDP can be solved when $ (\alpha _1+\cdots+\alpha _n)/n<\beta^{(n+1)/n}$. We change the lattice construction by Cohn and Heninger's algorithm and improve the condition $ \sqrt[n]{\alpha _1 \cdots \alpha _n}<\beta^{(n+1)/n}$. In the left hand side of the inequality, where is the arithmetic mean of $ \alpha _1,\ldots,\alpha _n$ in Cohn and Heninger's condition become the geometric mean of $ \alpha _1,\ldots,\alpha _n$ in our condition. Our algorithm can be applied to broader context. Moreover, considering the multivariate generalization of Howgrave-Graham's algorithm, our condition is more natural than Cohn and Heninger's condition. |
|
| キーワード | （和） | 近似公約数 / 格子 / Coppersmith理論 / / / / / |
| （英） | approximate-GCD / lattice / Coppersmith's theorem / / / / / | |
| 文献情報 | 信学技報, vol. 112, no. 126, ISEC2012-35, pp. 189-194, 2012年7月. | |
| 資料番号 | ISEC2012-35 | |
| 発行日 | 2012-07-12 (ISEC, SITE, ICSS, EMM) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2012-35 SITE2012-31 ICSS2012-37 EMM2012-27 |
|
| 研究会情報 | |
| 研究会 | EMM ISEC SITE ICSS IPSJ-CSEC IPSJ-SPT |
| 開催期間 | 2012-07-19 - 2012-07-20 |
| 開催地（和） | 北海道工業大学 |
| 開催地（英） | |
| テーマ（和） | セキュリティ, 一般 |
| テーマ（英） | Security |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2012-07-EMM-ISEC-SITE-ICSS-CSEC-SPT |
| 本文の言語 | 日本語 |
| タイトル（和） | 近似GCD問題に対する改良アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An Improved Algorithm for Approximate GCD Problems |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 近似公約数 / approximate-GCD |
| キーワード(2)（和/英） | 格子 / lattice |
| キーワード(3)（和/英） | Coppersmith理論 / Coppersmith's theorem |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 高安 敦 / Atsushi Takayasu / タカヤス アツシ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： UT) |
| 第2著者 氏名（和/英/ヨミ） | 國廣 昇 / Noboru Kunihiro / クニヒロ ノボル |
| 第2著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： UT) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-07-20 14:20:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2012-35, SITE2012-31, ICSS2012-37, EMM2012-27 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.126(ISEC), no.127(SITE), no.128(ICSS), no.129(EMM) |
| ページ範囲 | pp.189-194 |
| ページ数 | 6 |
| 発行日 | 2012-07-12 (ISEC, SITE, ICSS, EMM) |
[研究会発表申込システムのトップページに戻る]