電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2006-07-21 10:20
巡回セールスマン問題とトリボナッチ数列
小林邦勝国分清一郎山形大
技報オンラインサービス実施中
抄録 (和) 巡回セールスマン問題において,セールスマンの辿る経路が異なると対応する経路長も異なるための条件について検討する.これは暗号の一意復号可能性に関連する.一般項が連続する前3項の和として与えられるトリボナッチ数列の要素をあるルールに基づいて都市間距離として与えると,経路長からセールスマンの辿った経路が一意に定まることを示す. 次に,このトリボナッチ数列を用いた巡回セールスマン問題を公開鍵暗号に応用する.秘密鍵であるトリボナッチ数列の要素aにアフィン変換αa +βを施したものを公開鍵とし,幾つかのa毎に異なる複数のβを用いる場合には,復号アルゴリズムは非決定性となり,平文は一意に復号されるが,復号に要する計算量はβの個数に関する指数オーダーとなることを示す. 
(英) We consider the relation between the cycle and cycle length of traveling salesman problem using tribonacci sequence. It is shown that the condition which fix the cycle uniquely from the cycle length of traveling salesman problem using tribonacci sequence is obtained. Then, we apply the traveling salesman problem using tribonacci sequence to public key cryptosystem. As the plural constant t of affine transformation sa+t are used in key generation, this decoding algorithm becomes to non-deterministic algorithm and the complexity for decoding is exponential order relative to the number of t.
キーワード (和) 巡回セールスマン問題 / トリボナッチ数列 / ハミルトン閉路超増加 / アフィン変換 / 非決定性復号アルゴリズム / / /  
(英) Traveling salesman problem / Toribonacci sequence / Hamilton cycle super-increasing / Affine transformation / Non-deterministic decoding algorithm / / /  
文献情報 信学技報, vol. 106, no. 176, ISEC2006-42, pp. 13-18, 2006年7月.
資料番号 ISEC2006-42 
発行日 2006-07-14 (ISEC) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 ISEC SITE IPSJ-CSEC  
開催期間 2006-07-20 - 2006-07-21 
開催地(和) 岡山大学 
開催地(英) Okayama Univ. 
テーマ(和) 一般.情報通信システムセキュリティ時限研究専門委員会(ICSS)協賛 
テーマ(英)  
講演論文情報の詳細
申込み研究会 ISEC 
会議コード 2006-07-ISEC-SITE-IPSJ-CSEC 
本文の言語 日本語 
タイトル(和) 巡回セールスマン問題とトリボナッチ数列 
サブタイトル(和)  
タイトル(英) Traveling Salesman Problem and Tribonacci Sequence 
サブタイトル(英)  
キーワード(1)(和/英) 巡回セールスマン問題 / Traveling salesman problem  
キーワード(2)(和/英) トリボナッチ数列 / Toribonacci sequence  
キーワード(3)(和/英) ハミルトン閉路超増加 / Hamilton cycle super-increasing  
キーワード(4)(和/英) アフィン変換 / Affine transformation  
キーワード(5)(和/英) 非決定性復号アルゴリズム / Non-deterministic decoding algorithm  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 小林 邦勝 / Kunikatsu Kobayashi / コバヤシ クニカツ
第1著者 所属(和/英) 山形大学 (略称: 山形大)
Yamagata University (略称: Yamagata Univ.)
第2著者 氏名(和/英/ヨミ) 国分 清一郎 / Seiichirou Kokubun /
第2著者 所属(和/英) 山形大学 (略称: 山形大)
Yamagata University (略称: Yamagata Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2006-07-21 10:20:00 
発表時間 25 
申込先研究会 ISEC 
資料番号 IEICE-ISEC2006-42 
巻番号(vol) IEICE-106 
号番号(no) no.176 
ページ範囲 pp.13-18 
ページ数 IEICE-6 
発行日 IEICE-ISEC-2006-07-14 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会