文献

J-GLOBAL ID：202202269249704357   整理番号：22A0553396

系列の最小有理分数表現のためのアルゴリズムの再検討【JST・京大機械翻訳】

Algorithms for the Minimal Rational Fraction Representation of Sequences Revisited

著者 (4件)： Che Jun (College of Computer Science and Technology, Qingdao University, Qingdao, China) ,  Tian Chengliang (College of Computer Science and Technology, Qingdao University, Qingdao, China) ,  Jiang Yupeng (School of Cyber Science and Technology, Beihang University, Beijing, China) ,  Xu Guangwu (School of Cyber Science and Technology, Shandong University (Qingdao), Qingdao, China)
資料名： IEEE Transactions on Information Theory  (IEEE Transactions on Information Theory)
巻： 68  号： 2  ページ： 1316-1328  発行年： 2022年 
JST資料番号： C0231A  ISSN： 0018-9448  CODEN： IETTAW  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 長さnのバイナリシーケンスを考えると,その最小有理比率表現(MRFR)の決定は,ストリーム暗号の設計と暗号解析において重要な応用を持つ。KlapperとGoreskyが最初にO(n2lognloglogn)の時間複雑性を有する適応有理近似アルゴリズムを導入したので,この問題の多くの研究がある。本論文では,適応および非適応効率的アルゴリズムの両方を考慮することにより,この問題を再検討した。最先端の方法と比較して,MRFRを見つける問題に対していくつかの貢献を行った。最初に,連続打切シーケンスにより生成された2つの隣接格子の最小基底間の一般的で正確な再帰的関係を見出した。これにより,Li等によって提案された現在最も速い適応アルゴリズムを改善できる。第二に,二次元格子のためのよく知られたLagrange低減アルゴリズムの時間消費ステップを最適化することによって,著者らは,グローバルユークリッドアルゴリズムと呼ばれる非適応的で,しかも,実用的に高速のMRFR解決アルゴリズムを得る。第3に,著者らは,逆用例によって文献におけるいくつかの非適応方法に関する理論的欠陥を同定して,部分的ユークリッドアルゴリズムという修正ユークリッドアルゴリズムを設計することによって問題を修正した。一方,著者らは,半gcdアルゴリズムを呼び出すことによって,O(n2)からO(nlog2nloglogn)まで既存のアルゴリズムの時間複雑性をさらに減らした。また,上記のアルゴリズムについて包括的な実験的比較解析を行い,理論解析を検証した。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  最適化 ,  システム ,  リチウム ,  基底 ,  適応 ,  近似法 ,  高速度 ,  性質 ,  暗号
準シソーラス用語： 適応アルゴリズム ,  ストリーム暗号 ,  暗号解析 ,  複雑性 ,  理論解析 ,  バイナリー ,  二次元格子 ,  有理近似 , 【Automatic Indexing@JST】

分類 (1件)： 符号理論  (ND02030R)

タイトルに関連する用語 (2件)： 系列 ,  アルゴリズム