A Fast Multiplication Algorithm and RLWE-PLWE Equivalence for the Maximal Real Subfield of the $2^r p^s$-th Cyclotomic Field
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913818903314432 |
|---|---|
| author | Bolaños, Wilmar Haavikko, Antti Sánchez-Ledesma, Rodrigo Martín |
| author_facet | Bolaños, Wilmar Haavikko, Antti Sánchez-Ledesma, Rodrigo Martín |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05159 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Fast Multiplication Algorithm and RLWE-PLWE Equivalence for the Maximal Real Subfield of the $2^r p^s$-th Cyclotomic Field Bolaños, Wilmar Haavikko, Antti Sánchez-Ledesma, Rodrigo Martín Cryptography and Security Number Theory 94A60 (Primary), 11R80, 11T06 (Secondary) E.3.3 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$. |
| title | A Fast Multiplication Algorithm and RLWE-PLWE Equivalence for the Maximal Real Subfield of the $2^r p^s$-th Cyclotomic Field |
| topic | Cryptography and Security Number Theory 94A60 (Primary), 11R80, 11T06 (Secondary) E.3.3 |
| url | https://arxiv.org/abs/2504.05159 |