論文の概要: A New Algorithm for Computing Branch Number of Non-Singular Matrices over Finite Fields
- arxiv url: http://arxiv.org/abs/2405.07007v2
- Date: Mon, 23 Sep 2024 07:20:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-09 02:41:28.036271
- Title: A New Algorithm for Computing Branch Number of Non-Singular Matrices over Finite Fields
- Title（参考訳）: 有限場上の非特異行列分岐数計算アルゴリズム
- Authors: P. R. Mishra, Yogesh Kumar, Susanta Samanta, Atul Gaur,
- Abstract要約: 状態差やリニアマスクにおけるゼロでない要素の数は、アクティブなSボックスと直接相関する。
微分分岐数または線形分岐数は、SPN暗号の2つの連続するラウンドにおける活性S-ボックスの最小数を示す。
本稿では,有限体上の非特異行列の分岐数を計算するための新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 1.3332839594069594
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The notion of branch numbers of a linear transformation is crucial for both linear and differential cryptanalysis. The number of non-zero elements in a state difference or linear mask directly correlates with the active S-Boxes. The differential or linear branch number indicates the minimum number of active S-Boxes in two consecutive rounds of an SPN cipher, specifically for differential or linear cryptanalysis, respectively. This paper presents a new algorithm for computing the branch number of non-singular matrices over finite fields. The algorithm is based on the existing classical method but demonstrates improved computational complexity compared to its predecessor. We conduct a comparative study of the proposed algorithm and the classical approach, providing an analytical estimation of the algorithm's complexity. Our analysis reveals that the computational complexity of our algorithm is the square root of that of the classical approach.
- Abstract（参考訳）: 線形変換の分岐数の概念は、線形および微分暗号解析の両方に不可欠である。
状態差やリニアマスクにおけるゼロでない要素の数は、アクティブなSボックスと直接相関する。
微分または線形分岐数は、SPN暗号の2つの連続するラウンドにおいて、それぞれ微分または線形暗号解析のために、最小の活性S-ボックス数を示す。
本稿では,有限体上の非特異行列の分岐数を計算するための新しいアルゴリズムを提案する。
このアルゴリズムは、既存の古典的手法に基づいているが、前者に比べて計算の複雑さが改善されている。
本稿では,提案アルゴリズムと古典的アプローチの比較研究を行い,アルゴリズムの複雑さを解析的に推定する。
解析の結果,アルゴリズムの計算複雑性は古典的アプローチの平方根であることが判明した。
関連論文リスト
- Quantum Algorithms for tensor-SVD [10.96131926459428]
我々は2つの新しい量子t-SVD (tensor-SVD)アルゴリズムを導入する。
第一のアルゴリズムは、主にコンテキスト認識レコメンデーションシステムのための量子t-SVDアルゴリズムを提案する以前の研究に基づいている。
第二のアルゴリズムは、主に既知の変分量子SVDアルゴリズムに基づくハイブリッド変分法を用いる。
論文 参考訳（メタデータ） (2024-05-29T20:01:11Z) - A fixed-point algorithm for matrix projections with applications in
quantum information [7.988085110283119]
このアルゴリズムは反復数において最適解に指数関数的に収束することを示す。
量子資源理論および量子シャノン理論における我々のアルゴリズムのいくつかの応用について論じる。
論文 参考訳（メタデータ） (2023-12-22T11:16:11Z) - From Optimization to Control: Quasi Policy Iteration [3.4376560669160394]
準政治反復(QPI)と呼ばれる新しい制御アルゴリズムを提案する。
QPIは、政策反復アルゴリズムにおける「ヘシアン」行列の新たな近似に基づいて、MDPに特有の2つの線形構造制約を利用する。
これは、割引係数に対する感度が極めて低い政策反復と同様の実証的な収束挙動を示す。
論文 参考訳（メタデータ） (2023-11-18T21:00:14Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳（メタデータ） (2022-02-25T16:35:26Z) - Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。
我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
論文 参考訳（メタデータ） (2021-05-18T05:23:53Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。