| 講演名 | 2000/3/16 GuruswamiとSudanの代数幾何符号のリスト復号アルゴリズムにおける因数分解について 松本 隆太郎, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 代数幾何符号のリスト復号において、代数関数体を係数体とする一変数多項式の一次の因数をすべて見つける必要がある.HoholdtとRefslund Nielsenが提案した係数がエルミート関数体の場合に因数を見つける手法を任意の代数関数体で動作するように一般化する.提案手法は確率的アリゴリズムで, 平均実行時間はO(s^2l^2logqloglloglogl)である.ここでsはリストの大きさで, lは係数の最大の極位数である.またリスト復号において, 関数体に付随する線形空間の基底で, 指定した点における零位数が相異なるものを見つける必要がある.そのような基底を見つける方法もあわせて議論する. |
| 抄録(英) | In the list decoding of AG codes, we have to find all linear factors of a univariate polynomial over an algebraic function field. We generalize the factorization method by Hoholdt and Refslund Nielsen for the Hermitian function field to arbitrary algebraic function field. The algorithm is probabilistic and its running time is O(s^2l^2logqloglloglogl), where l is the maximum pole order of the coefficients of the polynomial, q the size of the finite field, and s the size of the list. In the list decoding we also have to find a basis of a linear system with pairwise distinct zero orders at a place of the function field. We also discuss how to find such a basis. |
| キーワード(和) | 代数幾何符号 / リスト復号 / 素因数分解 |
| キーワード(英) | algebraic geometry codes / list decoding / factorization |
| 資料番号 | IT99-75,ISEC99-114,SST99-123 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2000/3/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | GuruswamiとSudanの代数幾何符号のリスト復号アルゴリズムにおける因数分解について |
| サブタイトル（和） | |
| タイトル（英） | On the second step in the Guruswami-Sudan list decoding algorithm for AG codes |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 代数幾何符号 / algebraic geometry codes |
| キーワード(2)（和/英） | リスト復号 / list decoding |
| キーワード(3)（和/英） | 素因数分解 / factorization |
| 第 1 著者 氏名（和/英） | 松本 隆太郎 / Ryutaroh MATSUMOTO |
| 第 1 著者 所属（和/英） | 東京工業大学工学部電気電子工学科坂庭研究室 Sakaniwa Lab., Dept.of Electrical & Electronic Eng., Tokyo Institute of Technology |
| 発表年月日 | 2000/3/16 |
| 資料番号 | IT99-75,ISEC99-114,SST99-123 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 701 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |