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

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\ge 0$ and $s\ge 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$.