論文の概要: Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings
- arxiv url: http://arxiv.org/abs/2402.05059v1
- Date: Wed, 7 Feb 2024 18:10:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 07:38:15.352913
- Title: Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings
- Title（参考訳）: カニのレムマとブルーハト・ティッツ木におけるパスフィンディングを繋ぎ、超特異な自己同型環を計算する
- Authors: Kirsten Eisentraeger, Gabrielle Scullard,
- Abstract要約: 我々は、標数 p の超特異楕円曲線の自己準同型環を計算する決定論的時間アルゴリズムを与える。
我々は、局所自己同型環に向かうために高次元同相の技法を用いる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give a deterministic polynomial time algorithm to compute the endomorphism ring of a supersingular elliptic curve in characteristic p, provided that we are given two noncommuting endomorphisms and the factorization of the discriminant of the ring $\mathcal{O}_0$ they generate. At each prime $q$ for which $\mathcal{O}_0$ is not maximal, we compute the endomorphism ring locally by computing a q-maximal order containing it and, when $q \neq p$, recovering a path to $\text{End}(E) \otimes \mathbb{Z}_q$ in the Bruhat-Tits tree. We use techniques of higher-dimensional isogenies to navigate towards the local endomorphism ring. Our algorithm improves on a previous algorithm which requires a restricted input and runs in subexponential time under certain heuristics. Page and Wesolowski give a probabilistic polynomial time algorithm to compute the endomorphism ring on input of a single non-scalar endomorphism. Beyond using techniques of higher-dimensional isogenies to divide endomorphisms by a scalar, our methods are completely different.
- Abstract（参考訳）: 標数 p における超特異楕円曲線の自己準同型環を計算するための決定論的多項式時間アルゴリズムを与え、それらが生成する環 $\mathcal{O}_0$ の非可換自己準同型と判別式の分解を与える。
任意の素数$q$において、$\mathcal{O}_0$ は極大でないが、この自己準同型環は、それを含む q-極大順序を計算して局所的に計算し、$q \neq p$ が $\text{End}(E) \otimes \mathbb{Z}_q$ への経路をブルーハ・ティッツ木で回復する。
我々は、局所自己同型環に向かうために高次元同相の技法を用いる。
我々のアルゴリズムは、制限された入力を必要とする以前のアルゴリズムを改良し、特定のヒューリスティックスの下で指数時間以下で実行する。
Page と Wesolowski は1つの非スカラー自己準同型を入力して自己準同型環を計算する確率多項式時間アルゴリズムを与える。
高次元同相の技法を用いて、スカラーによって自己準同型を分割するだけでなく、我々の方法は全く異なる。
関連論文リスト
- The supersingular endomorphism ring problem given one endomorphism [5.01069065110753]
我々は、E の自己準同型環が古典的時間で計算できることを証明した。
また、楕円曲線上の滑らかなイデアルの作用が時間内に計算できることも証明する。
論文 参考訳（メタデータ） (2023-09-21T09:22:43Z) - The supersingular Endomorphism Ring and One Endomorphism problems are equivalent [5.01069065110753]
自己準同型環問題は、超特異楕円曲線間の任意の等元性を計算する問題と等価である。
我々は、追加情報を持つ等質グラフの研究のための柔軟なフレームワークを導入する。
論文 参考訳（メタデータ） (2023-09-19T08:47:12Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields [0.0]
$mathbb F_q$ 上で定義される虚超楕円曲線のヤコビアンは、ドリンフェルト加群の同型類の部分集合に作用する。
これは、Couveignes-Rostovtsev-Stolbunov群作用の関数場類似体である。
群作用を反転する問題は、Drynfeld $mathbb F_q[X]$-加群の間の固定された$tau$-次数の同種関係を見つける問題を減少させる。
論文 参考訳（メタデータ） (2022-03-14T10:11:35Z) - q-Paths: Generalizing the Geometric Annealing Path using Power Means [51.73925445218366]
我々は、幾何学と算術の混合を特別なケースとして含むパスのファミリーである$q$-pathsを紹介した。
幾何経路から離れた小さな偏差がベイズ推定に経験的利得をもたらすことを示す。
論文 参考訳（メタデータ） (2021-07-01T21:09:06Z) - Trotter product formulae for $*$-automorphisms of quantum lattice
systems [0.0]
我々は、$tau_t$ が $n$ 自己同型積によって効率的に近似できることを示した。
我々の境界はノルムで、有限体積観測可能量で十分に近似された代数元に対して点的に成り立つ。
論文 参考訳（メタデータ） (2021-05-29T01:09:21Z) - The Geometry of Time in Topological Quantum Gravity of the Ricci Flow [62.997667081978825]
我々は、リッチフロー方程式の族に付随する非相対論的量子重力の研究を継続する。
この位相重力はコホモロジー型であり、$cal N=2$拡張BRST対称性を示す。
我々は、場が$g_ij$, $ni$, $n$であり、(i)$g_ij$の位相的変形と(ii)超局所非相対論的空間の極限からなる理論の標準的な一段階BRSTゲージ固定を実証する。
論文 参考訳（メタデータ） (2020-11-12T06:57:10Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z) - Efficient quantum processing of ideals in finite rings [1.1724565818034947]
ポリ(log |R|)時間において、I に対して加法基底表現を求める方法を示す。
このアルゴリズムは、量子コンピュータが有限環に関する様々な問題を迅速に解くことができる有用なプリミティブであることを示す。
論文 参考訳（メタデータ） (2009-07-31T23:00:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。