論文の概要: Supersingularity and Superspeciality Verification of Abelian Surfaces
- arxiv url: http://arxiv.org/abs/2610.01924v1
- Date: Thu, 01 Oct 2026 15:57:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 01:19:24.248917
- Title: Supersingularity and Superspeciality Verification of Abelian Surfaces
- Title（参考訳）: アーベル曲面の超特異性と超特異性検証
- Abstract要約: 超特異アーベル曲面は等質暗号において必須である。
我々は、$mathbbF_p$ 上のアーベル曲面が超特異であるかどうかを検証する効率的なモンテカルロアルゴリズムを与える。
また、任意の次元のアーベル多様体が最小か最大かを検証する効率的なアルゴリズムも導出する。
- 参考スコア（独自算出の注目度）: 1.962656580942496
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Supersingular abelian surfaces are essential in isogeny-based cryptography. Despite this, we have no efficient algorithm to verify if a given abelian surface is supersingular. In this work, we initiate this research topic by giving an efficient Monte Carlo algorithm to verify if an abelian surface over $\mathbb{F}_p$ is supersingular in $O(\log p)$ with negligible failure probability, and an efficient conclusive algorithm if the order is smooth. We derive this algorithm by a careful analysis on the structure of supersingular Jacobians over $\mathbb{F}_p$. Furthermore, we derive efficient algorithms to verify if an abelian variety of any dimension is minimal or maximal, and to verify if a Jacobian of any dimension is superspecial.
- Abstract（参考訳）: 超特異アーベル曲面は等質暗号において必須である。
それにもかかわらず、与えられたアーベル曲面が超特異であるかどうかを検証する効率的なアルゴリズムは存在しない。
本研究では, 既知の失敗確率を持つ$O(\log p)$において, $\mathbb{F}_p$ 上のアーベル曲面が超特異であるかどうかを検証するための効率的なモンテカルロアルゴリズムと, 順序が滑らかであるような効率的な決定アルゴリズムを提供することにより, この研究トピックを開始する。
このアルゴリズムは、超特異ヤコビアンの構造を$\mathbb{F}_p$で慎重に解析することで導出する。
さらに、任意の次元のアーベル多様体が極小であるか極大であるかを検証し、任意の次元のヤコビアンが超特殊であるかどうかを検証するための効率的なアルゴリズムを導出する。
関連論文リスト
- Learning to Sparsify Stochastic Linear Bandits [12.61900668356141]
本稿では,高次元空間から連続的に行動を選択する線形帯域幅の分散化を学習する問題に対処する。
本稿では,パラメータ学習のための最小二乗法と,スパース動作選択のための特別サブルーチンを用いて,適応的に段階的に探索・利用を行うアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2026-05-11T07:57:37Z) - Quantum Algorithms for Projection-Free Sparse Convex Optimization [32.34794896079469]
ベクトル領域に対しては、$O(sqrtd/varepsilon)$のクエリ複雑性を持つ$varepsilon$-optimal解を求めるスパース制約に対する2つの量子アルゴリズムを提案する。
行列領域に対しては、時間複雑性を$tildeO(rd/varepsilon2)$と$tildeO(sqrtrd/varepsilon3)$に改善する2つの核ノルム制約の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-07-11T12:43:58Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic
Composite Optimization [10.762749887051546]
本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。
以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
論文 参考訳（メタデータ） (2023-02-20T05:16:18Z) - Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - The Hypervolume Indicator Hessian Matrix: Analytical Expression,
Computational Time Complexity, and Sparsity [4.523133864190258]
本稿では,$d$次元決定空間における$n$点の(固定サイズ)集合からスカラー超体積指標値への写像のヘッセン行列の解析式を確立する。
ヘッセン行列はニュートン・ラフソン最適化法のような二階法において重要な役割を担い、局所最適集合の検証に使用できる。
論文 参考訳（メタデータ） (2022-11-08T11:24:18Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。