論文の概要: A Fast Multiplication Algorithm and RLWE-PLWE Equivalence for the Maximal Real Subfield of the $2^r p^s$-th Cyclotomic Field

• arxiv url: http://arxiv.org/abs/2504.05159v1
• Date: Mon, 07 Apr 2025 15:01:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-08 14:08:28.958588
• Title: A Fast Multiplication Algorithm and RLWE-PLWE Equivalence for the Maximal Real Subfield of the $2^r p^s$-th Cyclotomic Field
• Title（参考訳）: 2^r p^s$-thサイクロトミック場の最大実部分場に対する高速乗算アルゴリズムとRLWE-PLWE等価性
• Authors: Wilmar Bolaños, Antti Haavikko, Rodrigo Martín Sánchez-Ledesma,
• Abstract要約: 導体$n = 2r ps$ でシクロトミック場の最大実部分体に対する RLWE-PLWE 同値性を証明する。 また、これらの実部分体の整数環における高速乗法アルゴリズムについても述べる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: This paper proves the RLWE-PLWE equivalence for the maximal real subfields of the cyclotomic fields with conductor $n = 2^r p^s$, where $p$ is an odd prime, and $r \geq 0$ and $s \geq 1$ are integers. In particular, we show that the canonical embedding as a linear transform has a condition number bounded above by a polynomial in $n$. In addition, we describe a fast multiplication algorithm in the ring of integers of these real subfields. The multiplication algorithm uses the fast Discrete Cosine Transform (DCT) and has computational complexity $\mathcal{O}(n \log n)$. Both the proof of the RLWE-PLWE equivalence and the fast multiplication algorithm are generalizations of previous results by Ahola et al., where the same claims are proved for a single prime $p = 3$.
• Abstract（参考訳）: 本稿では、導体$n = 2^r p^s$、$p$が奇素数、$r \geq 0$と$s \geq 1$が整数であるシクロトミック場の最大実部分体に対するRLWE-PLWE同値性を証明する。 特に、線型変換としての正準埋め込みは、$n$の多項式によって上に有界な条件数を持つことを示す。 さらに、これらの実部分体の整数環における高速乗法アルゴリズムについて述べる。 乗算アルゴリズムは高速離散コサイン変換(DCT)を使用し、計算複雑性は$\mathcal{O}(n \log n)$である。 RLWE-PLWE同値性の証明と高速乗法アルゴリズムの両方がアホラらによる以前の結果の一般化であり、同じ主張は1つの素数$p = 3$に対して証明される。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Maximal Real Subfields of Cyclotomic Fields [6.487242614495099]
  RLWE(Ring Learning With Errors)問題とPLWE(Polynomial Learning With Errors)問題との等価性を実証する。 また、最大実部分体の環内の2つの要素の積を計算するための高速整数についても述べる。
  論文  参考訳（メタデータ） (2024-10-01T15:32:02Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Computing $\varphi(N)$ for an RSA module with a single quantum query [0.0]
  RSAモジュールの$N$に対して$varphi(N)$を、ランダムに選択された整数の代入として$N$を演算する計算時間アルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-06-06T13:30:18Z)
• The Qudit ZH Calculus for Arbitrary Finite Fields: Universality and Application [0.0]
  原動力次元$q = pt$のクォーディットに対するグラフィカルなZH計算の一般化を提案する。 この計算は、$mathbb Cqn から mathbb Cqm$ への行列上の普遍性を示し、環 $mathbb Z[omega]$ ここで $omega$ はユニタリの$p$thルートである。
  論文  参考訳（メタデータ） (2024-06-04T11:21:10Z)
• Efficient Parallelization of a Ubiquitous Sequential Computation [0.0]
  x_t = a_t x_t-1 + b_t$ を並列に計算するための簡潔な式が見つかる。 n$並列プロセッサでは、$n$要素の計算は$mathcalO(log n)$ timeと$mathcalO(n)$ spaceを発生させる。 ソフトウェアで表現を実装し、並列ハードウェア上でテストし、$fracnlog n$の係数で逐次計算よりも高速に実行されることを検証します。
  論文  参考訳（メタデータ） (2023-10-27T21:58:55Z)
• 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)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
  我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。 また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
  論文  参考訳（メタデータ） (2022-02-11T23:53:43Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。 次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。 Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
  論文  参考訳（メタデータ） (2020-06-21T06:57:59Z)

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

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