論文の概要: The complexity of solving a random polynomial system
- arxiv url: http://arxiv.org/abs/2309.03855v1
- Date: Thu, 7 Sep 2023 17:14:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-25 16:20:50.124307
- Title: The complexity of solving a random polynomial system
- Title（参考訳）: ランダム多項式系を解く複雑さ
- Authors: Giulia Gaggero, Elisa Gorla,
- Abstract要約: 本稿では,多変量系の解法に用いる一般アルゴリズムの概要について述べる。
次に、ランダムなシステム、特に"ランダム"が私たちにとって何を意味するかについて話します。
このようなランダムシステムの正則度と解度の両方に上限を与える。
- 参考スコア（独自算出の注目度）: 3.420117005350141
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A multivariate cryptograpic instance in practice is a multivariate polynomial system. So the security of a protocol rely on the complexity of solving a multivariate polynomial system. In this paper there is an overview on a general algorithm used to solve a multivariate system and the quantity to which the complexity of this algorithm depends on: the solving degree. Unfortunately, it is hard to compute. For this reason, it is introduced an invariant: the degree of regularity. This invariant, under certain condition, give us an upper bound on the solving degree. Then we speak about random polynomial systems and in particular what "random" means to us. Finally, we give an upper bound on both the degree of regularity and the solving degree of such random systems.
- Abstract（参考訳）: 実際には、多変量暗号グラフのインスタンスは多変量多項式系である。
したがって、プロトコルのセキュリティは多変量多項式系を解く複雑さに依存している。
本稿では,多変量系を解くのに使用される一般アルゴリズムの概要と,このアルゴリズムの複雑性が依存する量,すなわち解度について概説する。
残念ながら、計算は困難です。
そのため、正則性の次数という不変量が導入される。
この不変量は、ある条件下では、解度の上限を与える。
そして、ランダム多項式系、特に「ランダム」が我々にどんな意味を持つかについて話す。
最後に、そのようなランダムシステムの正則度と解度の両方に上限を与える。
関連論文リスト
- Quantum Advantage via Solving Multivariate Quadratics [12.62849227946452]
p_i(x_n)=y_i_iin [m]$ over $mathbbF$。
解は高い確率で存在するが、古典的暗号解析に基づく解を見つけることは困難である。
論文 参考訳（メタデータ） (2024-11-22T03:10:10Z) - Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers [7.953947994427209]
我々は、Lyapunov関数を発見し、システムのグローバルな安定性を保証するという、数学における長年のオープンな問題を考える。
この問題には既知の一般解はなく、いくつかの小さなアルゴリズム系にのみ存在する。
そこで本研究では,システム上でのシーケンス・ツー・シーケンス・トランスフォーマが,解法や人間よりも優れた性能を示すことを示す。
論文 参考訳（メタデータ） (2024-10-10T18:50:10Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Solving Degree Bounds For Iterated Polynomial Systems [0.0]
我々は,MIMC,Feistel-MiMC,Feistel-MiMC-Hash,Hades,GMiMCに対する攻撃に対する正則性評価を行った。
我々の境界は、これらの設計に対するGr"オブナーベースアタックの仮定された複雑さと一致している。
論文 参考訳（メタデータ） (2023-10-05T16:10:14Z) - An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。
我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
論文 参考訳（メタデータ） (2023-08-27T11:51:27Z) - Automatic Solver Generator for Systems of Laurent Polynomial Equations [1.7188280334580197]
同じ単項構造であるが様々な係数を持つ三角系(ローラン系)が与えられたとき、任意の族に対する解をできるだけ早く計算する解法を見つける。
ローラン方程式系に対する自動解法生成器を提案する。
論文 参考訳（メタデータ） (2023-07-01T12:12:52Z) - A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium [0.3749861135832073]
我々は,少なくとも1つの解を持つシステム向けに設計されたMultiというアルゴリズムで,この戦略を実装した。
我々は,最大ステップ数のマルチステップ戦略を用いることで,Multiの最適複雑性が達成されることを証明し,その結果,単一のステップからなる戦略である標準的な推測・決定戦略が最悪の選択であることを示す。
論文 参考訳（メタデータ） (2023-04-16T16:09:14Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳（メタデータ） (2023-01-22T22:08:28Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。