論文の概要: Memetic Search for Supersingular Elliptic Curves over $\mathbb{F}_p$
- arxiv url: http://arxiv.org/abs/2609.03249v1
- Date: Thu, 03 Sep 2026 01:11:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-04 18:28:38.888094
- Title: Memetic Search for Supersingular Elliptic Curves over $\mathbb{F}_p$
- Title（参考訳）: $\mathbb{F}_p$ 上の超特異楕円曲線のメメティックサーチ
- Abstract要約: 超特異楕円曲線の探索は、等質暗号における基本的な計算問題である。
我々は,1次元の$j$-不変染色体,ビットレベル組換え,適応突然変異,周期的局所探索を用いて,$mathbbF_p$に合わせたメメティックアルゴリズムを開発した。
結果は、アルゴリズムが46ビットの正確な超特異曲線を発見し、フロベニウスのトレースが著しく0に近いような、ほぼ超特異な通常の曲線に連続的に収束することを示している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The search for supersingular elliptic curves is a fundamental computational problem in isogeny-based cryptography. A recent metaheuristic formulation over $\mathbb{F}_{p^2}$ introduced the NonMultiplicity Distance (NMD) objective, measuring the deviation of the Frobenius trace from a multiple of $p$, and showed that uninformed random search fails beyond $\approx 10^{13}$ candidates. This work investigates metaheuristic search over the prime field $\mathbb{F}_p$, the setting for oriented isogeny protocols such as CSIDH, OSIDH, and SQISign. Although the candidate space decreases from $p^2$ to $p$, the supersingular locus is asymptotically sparse ($O(\sqrt{p}\log p)$ curves), keeping the search exponentially difficult. We formulate a memetic algorithm tailored to $\mathbb{F}_p$ using a one-dimensional $j$-invariant chromosome, bit-level recombination, adaptive mutation, and periodic local search under the NMD objective. Benchmarks across 30 independent seeds at 40-bit, 46-bit, and 51-bit prime sizes ($p \approx 1.13\times 10^{15}$) show that the algorithm discovers an exact supersingular curve at 46 bits and consistently converges to ``near-supersingular'' ordinary curves with Frobenius traces remarkably close to zero: best NMD values of 19 at 40 bits and 3 at 51 bits, corresponding to relative trace deviations of $1.3\times 10^{-5}$ and $4.5\times 10^{-8}$ across the Hasse interval. These results demonstrate that NMD-driven memetic search effectively navigates the sparse $\mathbb{F}_p$ landscape and systematically locates near-supersingular structures.
- Abstract（参考訳）: 超特異楕円曲線の探索は、等質暗号における基本的な計算問題である。
最近のメタヒューリスティックな定式化では、$\mathbb{F}_{p^2}$がNonMultiplicity Distance (NMD) の目的を導入し、$p$の倍からフロベニウストレースの偏差を測定し、不整形なランダム探索が$\approx 10^{13}$の候補を超えて失敗することを示した。
本研究は、CSIDH, OSIDH, SQISign などの配向同種プロトコルの設定である素体 $\mathbb{F}_p$ 上のメタヒューリスティック探索について検討する。
候補空間は$p^2$から$p$に減少するが、超特異軌跡は漸近的にスパース(O(\sqrt{p}\log p)$曲線)であり、指数関数的に検索が困難である。
我々は,1次元の$j$不変染色体,ビットレベル組換え,適応突然変異,周期的局所探索を用いて,$\mathbb{F}_p$に調整したメメティックアルゴリズムを定式化する。
40ビット、46ビット、51ビットの素サイズ(p \approx 1.13\times 10^{15}$)で30個の独立種子をベンチマークすると、アルゴリズムは46ビットで正確な超特異曲線を発見し、一貫してフロベニウスの通常の曲線に収束する。
これらの結果は,NMD駆動のメメティックサーチがスパース$\mathbb{F}_p$ランドスケープを効果的にナビゲートし,ほぼ超特異な構造を体系的に見つけることを示した。
関連論文リスト
- Evolving Quantum Error-Correcting Encodings for Molecular Simulation [0.6372261626436676]
言語モデルがプログラムを編集し、外部検証器が結果をスコアし、ハイスコアプログラムを保持・変更する。
ケーススタディでは、このループをfermion-to-qubitエンコーディングであるGeneralized Superfast (GSE)に適用する。
我々の知る限り、これらは高密度の分子ハミルトニアンに対して3ドルを超える距離のGSE/スーパーファストエンコーディングである。
論文 参考訳（メタデータ） (2026-06-24T14:19:43Z) - Detection of local geometry in random graphs: information-theoretic and computational limits [4.67223325681232]
ランダムグラフにおける局所幾何学の検出問題について検討する。
平均サイズ$k$の隠れコミュニティがランダムな幾何グラフとして描画されるようなモデル$mathcalG(n, p, d, k)$を導入する。
残りのすべての辺はアーズ=レーニモデル $mathcalG(n, p)$ に従う。
論文 参考訳（メタデータ） (2026-03-25T17:20:01Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - The Complexity of Finding Local Optima in Contrastive Learning [18.910128965812124]
個別設定で$mathsfPLS$-hardness、連続設定で$mathsfPLS$-hardnessを証明します。
この結果から,アルゴリズムが様々なコントラスト学習問題の局所的最適解を見つけることは不可能であることが示唆された。
論文 参考訳（メタデータ） (2025-09-21T03:21:04Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。
SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - 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) - Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approach [18.009376840944284]
本稿では,ヘッセン損失行列を効果的に正規化できるアルゴリズムを提案する。
提案手法は,CLIPとチェーン・オブ・ファインチューニングデータセットの事前学習における一般化の改善に有効である。
論文 参考訳（メタデータ） (2023-06-14T14:58:36Z) - Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models:
Sharp Minimax Rates [1.0309387309011746]
スパースな代替品に対する信号検出問題を、既知のスパシティ$s$に対して検討する。
ミニマックス分離半径$epsilon*$の上の上限と下限を見つけ、それらが常に一致することを証明する。
以上の結果から,epsilon*$の挙動に関する新たな位相遷移が,Sigma$の疎度レベル,$Lt$メトリック,およびヘテロスセダサシティプロファイル(herescedasticity profile)に現れる。
論文 参考訳（メタデータ） (2022-11-15T23:53:39Z) - 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) - Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed
Number of Neurons [5.37133760455631]
一定数のニューロンを持つ全ての連続関数に対する普遍近似特性を実現するフィードフォワードニューラルネットワークを開発した。
例えば、$sigma$-activated networks with width $36d(2d+1)$ and depth $111$ can almost any continuous function on a $d$-dimensioanl hypercube in an arbitrarilyly small error。
論文 参考訳（メタデータ） (2021-07-06T05:24:30Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。