WEKO3
アイテム
An Accelerated Algorithm for Solving SVP Based on Statistical Analysis
https://ipsj.ixsq.nii.ac.jp/records/106990
https://ipsj.ixsq.nii.ac.jp/records/10699070aef2f5-78c0-4fd9-bfad-f6a5ef130427
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL5511018 (581.9 kB)
|
Copyright (c) 2014 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-11-15 | |||||||||
| タイトル | ||||||||||
| タイトル | An Accelerated Algorithm for Solving SVP Based on Statistical Analysis | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | An Accelerated Algorithm for Solving SVP Based on Statistical Analysis | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | [一般論文] lattice, SVP, Gram-Schmidt orthogonalized vectors, RSR, normal distribution | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| 著者所属 | ||||||||||
| Dokkyo University | ||||||||||
| 著者所属 | ||||||||||
| Department of General Systems Studies, The University of Tokyo | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Dokkyo University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Department of General Systems Studies, The University of Tokyo | ||||||||||
| 著者名 |
Masaharu, Fukase
× Masaharu, Fukase
× Kenji, Kashiwabara
|
|||||||||
| 著者名(英) |
Masaharu, Fukase
× Masaharu, Fukase
× Kenji, Kashiwabara
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | In this paper, we propose an accelerated algorithm for solving the shortest vector problem (SVP). We construct our algorithm by using two novel ideas, i.e., the choice of appropriate distributions of the natural number representation and the reduction of the sum of the squared lengths of the Gram-Schmidt orthogonalized vectors. These two ideas essentially depend on statistical analysis. The first technique is to generate lattice vectors expected to be short on a particular distribution of natural number representation. We determine the distribution so that more very short lattice vectors have a chance to be generated while lattice vectors that are unlikely to be very short are not generated. The second technique is to reduce the sum of the squared lengths of the Gram-Schmidt orthogonalized vectors. For that, we restrict the insertion index of a new lattice vector. We confirmed by theoretical and experimental analysis that the smaller the sum is, the more frequently a short lattice vector tends to be found. We solved an SVP instance in a higher dimension than ever, i.e., dimension 132 using our algorithm. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.23(2015) No.1 (online) ------------------------------ |
|||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | In this paper, we propose an accelerated algorithm for solving the shortest vector problem (SVP). We construct our algorithm by using two novel ideas, i.e., the choice of appropriate distributions of the natural number representation and the reduction of the sum of the squared lengths of the Gram-Schmidt orthogonalized vectors. These two ideas essentially depend on statistical analysis. The first technique is to generate lattice vectors expected to be short on a particular distribution of natural number representation. We determine the distribution so that more very short lattice vectors have a chance to be generated while lattice vectors that are unlikely to be very short are not generated. The second technique is to reduce the sum of the squared lengths of the Gram-Schmidt orthogonalized vectors. For that, we restrict the insertion index of a new lattice vector. We confirmed by theoretical and experimental analysis that the smaller the sum is, the more frequently a short lattice vector tends to be found. We solved an SVP instance in a higher dimension than ever, i.e., dimension 132 using our algorithm. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.23(2015) No.1 (online) ------------------------------ |
|||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN00116647 | |||||||||
| 書誌情報 |
情報処理学会論文誌 巻 55, 号 11, 発行日 2014-11-15 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 1882-7764 | |||||||||
