2025/04/07 by Wilmar Bolaños, Bolaños, Wilmar, Antti Haavikko +3
Computer Science · #11R80 #11T06 (Secondary) #94A60 (Primary) #Coding theory and cryptography #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #E.3.3 #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2504.05159
openalex publication_date 2025/04/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper proves the RLWE-PLWE equivalence for the maximal real subfields of the cyclotomic fields with conductor n = 2r ps, where p is an odd prime, and r ≥ 0 and s ≥ 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 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.