{"links":{},"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00106990","sets":["581:7397:7703"]},"path":["7703"],"owner":"11","recid":"106990","title":["An Accelerated Algorithm for Solving SVP Based on Statistical Analysis"],"pubdate":{"attribute_name":"公開日","attribute_value":"2014-11-15"},"_buckets":{"deposit":"90be10ce-8f8a-446b-95b5-7263e492c058"},"_deposit":{"id":"106990","pid":{"type":"depid","value":"106990","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"An Accelerated Algorithm for Solving SVP Based on Statistical Analysis","author_link":["14872","14873","14871","14874"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"An Accelerated Algorithm for Solving SVP Based on Statistical Analysis"},{"subitem_title":"An Accelerated Algorithm for Solving SVP Based on Statistical Analysis","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[一般論文] lattice, SVP, Gram-Schmidt orthogonalized vectors, RSR, normal distribution","subitem_subject_scheme":"Other"}]},"item_type_id":"2","publish_date":"2014-11-15","item_2_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Dokkyo University"},{"subitem_text_value":"Department of General Systems Studies, The University of Tokyo"}]},"item_2_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Dokkyo University","subitem_text_language":"en"},{"subitem_text_value":"Department of General Systems Studies, The University of Tokyo","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"publish_status":"0","weko_shared_id":11,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/106990/files/IPSJ-JNL5511018.pdf","label":"IPSJ-JNL5511018"},"date":[{"dateType":"Available","dateValue":"2016-11-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-JNL5511018.pdf","filesize":[{"value":"581.9 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"8"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"eaed75cd-7e08-4df7-88c0-8a78b2a821bd","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2014 by the Information Processing Society of Japan"}]},"item_2_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Masaharu, Fukase"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kenji, Kashiwabara"}],"nameIdentifiers":[{}]}]},"item_2_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Masaharu, Fukase","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kenji, Kashiwabara","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_2_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00116647","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_2_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7764","subitem_source_identifier_type":"ISSN"}]},"item_2_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"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.\n\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.23(2015) No.1 (online)\n------------------------------","subitem_description_type":"Other"}]},"item_2_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.\n\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.23(2015) No.1 (online)\n------------------------------","subitem_description_type":"Other"}]},"item_2_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2014-11-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"11","bibliographicVolumeNumber":"55"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"updated":"2025-01-20T06:45:07.160342+00:00","created":"2025-01-18T23:50:17.552560+00:00","id":106990}