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

• URL: http://arxiv.org/abs/2504.05159v1
• Date: Mon, 07 Apr 2025 15:01:48 GMT
• Title: A Fast Multiplication Algorithm and RLWE-PLWE Equivalence for the Maximal Real Subfield of the $2^r p^s$-th Cyclotomic Field
• Authors: Wilmar Bolaños, Antti Haavikko, Rodrigo Martín Sánchez-Ledesma,
• Abstract summary: We prove the RLWE-PLWE equivalence for the maximal real subfields of the cyclotomic fields with conductor $n = 2r ps$.<n>We also describe a fast multiplication algorithm in the ring of integers of these real subfields.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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$.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (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]
  We prove the equivalence between the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems.<n>We also describe a fast integers for computing the product of two elements in the ring of the maximal real subfield.
  arXiv  Detail & Related papers  (2024-10-01T15:32:02Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$. We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
  arXiv  Detail & Related papers  (2024-08-10T04:26:19Z)
• Computing $\varphi(N)$ for an RSA module with a single quantum query [0.0]
  We give a computation time algorithm to compute $varphi(N)$ for an RSA module $N$ using as input the order modulo $N$ of a randomly chosen integer.
  arXiv  Detail & Related papers  (2024-06-06T13:30:18Z)
• The Qudit ZH Calculus for Arbitrary Finite Fields: Universality and Application [0.0]
  We propose a generalization of the graphical ZH calculus to qudits of prime-power dimensions $q = pt$. We show this calculus to be universal over matrices $mathbb Cqn to mathbb Cqm$ with entries in the ring $mathbb Z[omega]$ where $omega$ is a $p$th root of unity.
  arXiv  Detail & Related papers  (2024-06-04T11:21:10Z)
• Efficient Parallelization of a Ubiquitous Sequential Computation [0.0]
  We find a succinct expression for computing the sequence $x_t = a_t x_t-1 + b_t$ in parallel. On $n$ parallel processors, the computation of $n$ elements incurs $mathcalO(log n)$ time and $mathcalO(n)$ space. We implement our expression in software, test it on parallel hardware, and verify that it executes faster than sequential computation by a factor of $fracnlog n$.
  arXiv  Detail & Related papers  (2023-10-27T21:58:55Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Polynomial computational complexity of matrix elements of finite-rank-generated single-particle operators in products of finite bosonic states [0.0]
  It is known that computing the permanent computation of the matrix $1+A$, where $A$ is a finite-rank matrix, requires a number of operations in the matrix size. I extend this result to a generalization of the matrix permanent: an expectation value in a product of a large number of identical bosonic states with a bounded number of bosons.
  arXiv  Detail & Related papers  (2022-10-20T20:09:28Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
  We present an algorithm that computes $k$ models of $C$ among those having the largest values w.r. $$. We also present a pseudo-time algorithm that transforms $C$ into a d-DNNF circuit $C'$ satisfied exactly by the models of $C$ having a value among the top-$k$ ones.
  arXiv  Detail & Related papers  (2022-02-11T23:53:43Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  We first prove a simple variant of the vanilla coordinate ascent, called Coordinate-Ascent+. We then propose Coordinate-Ascent++, that achieves tight $(1-1/e-varepsilon)$-approximation guarantee while performing the same number of iterations. The computation of each round of Coordinate-Ascent++ can be easily parallelized so that the computational cost per machine scales as $O(n/sqrtvarepsilon+nlog n)$.
  arXiv  Detail & Related papers  (2020-06-21T06:57:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.