| 講演抄録／キーワード |
| 講演名 |
2006-07-21 10:20
巡回セールスマン問題とトリボナッチ数列
○小林邦勝・国分清一郎（山形大） |
| 抄録 |
（和） |
巡回セールスマン問題において，セールスマンの辿る経路が異なると対応する経路長も異なるための条件について検討する．これは暗号の一意復号可能性に関連する．一般項が連続する前３項の和として与えられるトリボナッチ数列の要素をあるルールに基づいて都市間距離として与えると，経路長からセールスマンの辿った経路が一意に定まることを示す． 次に，このトリボナッチ数列を用いた巡回セールスマン問題を公開鍵暗号に応用する．秘密鍵であるトリボナッチ数列の要素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 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
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著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2006-07-21 10:20:00 |
| 発表時間 |
25分 |
| 申込先研究会 |
ISEC |
| 資料番号 |
ISEC2006-42 |
| 巻番号（vol） |
vol.106 |
| 号番号（no） |
no.176 |
| ページ範囲 |
pp.13-18 |
| ページ数 |
6 |
| 発行日 |
2006-07-14 (ISEC) |