論文の概要: The Supersingular Isogeny Problem in Time and Memory $p^{1/3+o(1)}$, Unconditionally

• arxiv url: http://arxiv.org/abs/2609.22018v1
• Date: Fri, 18 Sep 2026 17:12:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-21 18:40:17.201752
• Title: The Supersingular Isogeny Problem in Time and Memory $p^{1/3+o(1)}$, Unconditionally
• Title（参考訳）: 時間と記憶における超特異等質問題$p^{1/3+o(1)}$,無条件で
• Abstract要約: 超特異楕円曲線 $E/mathbbF_p2$ が与えられたとき、$mathsfEnd$問題は、$E$ の非スカラー自己準同型を求める。 既知の還元により、この問題を解くことは超特異な自己同型環や同種問題も解決する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, the $\mathsf{OneEnd}$ problem asks for a non-scalar endomorphism of $E$. By known reductions, solving this problem also solves the supersingular endomorphism ring and isogeny problems. Wesolowski obtained exponent $1/3$ under an assumption on the factorization of a small degree, whereas the previous unconditional exponent was $2/5$. We give a Las Vegas algorithm, analyzed without a smoothness heuristic, with expected time and memory \[ p^{1/3}\exp\bigl(O(\sqrt{\log p\,\log\log p})\bigr) = p^{1/3+o(1)}. \] The algorithm fixes in advance a family of degrees that are products of small primes. Known counting results provide many isogenies of these degrees from curves to their Frobenius conjugates, and a collision estimate shows that the isogenies occur on sufficiently many distinct curves for a random walk to reach one of them. From such a curve, the algorithm splits a degree into two parts, enumerates two lists of shorter isogenies, and matches their targets to obtain an isogeny to the conjugate, whose composition with Frobenius gives the required endomorphism.
• Abstract（参考訳）: 超特異楕円曲線 $E/\mathbb{F}_{p^2}$ が与えられたとき、$\mathsf{OneEnd}$問題は、$E$ の非スカラー自己準同型を求める。 既知の還元により、この問題を解くことは超特異な自己同型環や同種問題も解決する。 ヴェゾロフスキーは小さな因子の分解を仮定して指数$1/3$を得たが、以前の非条件指数は2/5$であった。 我々は,スムーズなヒューリスティックを伴わずに解析したラスベガスのアルゴリズムを,期待時間とメモリ \[p^{1/3}\exp\bigl(O(\sqrt{\log p\,\log\log p})\bigr) = p^{1/3+o(1)} で提供する。 アルゴリズムは前もって、小さな素数の積である次数の族を修正します。 数えられる結果は、曲線からフロベニウス共役まで、これらの次数の多くの等質性を与え、衝突推定は、ランダムウォークがそれらのうちの1つに到達するのに十分な数の異なる曲線で等質性が発生することを示している。 そのような曲線から、アルゴリズムは次数を2つに分割し、より短い同種性の2つのリストを列挙し、その対象と一致して共役への同型を得る。

関連論文リスト

• An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
  単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。 私たちの指導原則は、最大値が丸みを帯びた候補であることです。
  論文  参考訳（メタデータ） (2026-08-03T17:58:00Z)
• Topology of the Set of Entangled State [0.0]
  ここでは、$mathsf E$ はパス接続であり、2ビットの場合を除いて単に接続されていることを示す。 この例外的な場合、$mathsf E$ は極大交絡状態の集合とホモトピー同値であることが判明した。
  論文  参考訳（メタデータ） (2026-07-20T16:04:26Z)
• Nodal algebraic curves and entropy diagnostics in degenerate two-dimensional harmonic-oscillator shells [0.0]
  退化量子固有空間は、固定エネルギーにおける結節幾何学の実質的な変化を支持することができることを示す。 これらの基準をエントロピー診断と組み合わせて、トポロジに変化する事象が発生する可能性のある層を同定する。 この枠組みは、実相エルミート-ガウス構造光とほぼ等方性に閉じ込められた運動系に対する実験的に再構成可能なシグネチャを提案する。
  論文  参考訳（メタデータ） (2026-04-30T17:15:26Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Rigorous derivation of the Efimov effect in a simple model [68.8204255655161]
  我々は、2体ゼロレンジ相互作用と、与えられた半径$a>0$の3体ハードコア反発を持つ$mathbbR3$の3つの同一ボソンの系を考える。
  論文  参考訳（メタデータ） (2023-06-21T10:11:28Z)
• Universality in the tripartite information after global quenches: (generalised) quantum XY models [0.0]
  我々は、R'enyi-$alpha$ tripartite information $I_3(alpha)$ 定常状態における3つの隣接部分系が、等質状態と二成分状態の両方からの非相互作用スピン鎖における大域的クエンチの後に現れると考える。 我々は、$I_3(alpha)$が無限長の極限においてもゼロではないような設定を特定し、はしご上の自由フェルミオン場の記述を効果的に量子場理論で記述する。
  論文  参考訳（メタデータ） (2023-02-02T18:50:42Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。 我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
  論文  参考訳（メタデータ） (2021-04-26T15:03:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。