1
$\begingroup$

I was checking the following lecture notes, and on page 5, it says that $m$ vectors $x_1,\ldots,x_m$ are independently sampled from the Gaussian distribution, and then they are reduced modulo the parallelepiped $\mathcal{P}(B)$ of the lattice $\Lambda(B)$, where $B$ is the basis, in order to obtain new vectors $y_1,\ldots,y_m$. Given that the parallelepiped is defined as $\mathcal{P}(B) = \{ \sum a_ib_i \mid a_i \in \mathbb{R}, a_i \in [0,1) \}$, what exactly it means to reduce a vector modulo the parallelepiped, i.e., compute $y_i = x_i \mod \mathcal{P}(B)$?

$\endgroup$
2
  • 1
    $\begingroup$ Decompose $x_{i}$ into its coordinate representation in $B$ and take all the coordinates $\pmod{1}$. $\endgroup$ Commented Jul 4, 2023 at 20:26
  • $\begingroup$ @JoshuaWang What exactly you mean by coordinate representation in 𝐵? Something like $Bz = x$, so $z$ is the coordinate representation? What if $x$ is not a lattice point? $\endgroup$
    – pandora
    Commented Jul 5, 2023 at 7:54

1 Answer 1

1
$\begingroup$

The equation $y_i = x_i \bmod \mathcal{P}(B)$ denotes that $y_i$ represents the unique vector in $\mathcal{P}(B)$ such that $y_i - x_i \in \mathcal{L}(B)$. To derive this $y_i$, we can express $x_i = \sum_{i=1}^{n} c_i b_i$ where $c_i \in \mathbb{R}$. Then, it is easy to see that $y_i = \sum_{i=1}^{n} (c_i - \lfloor c_i \rfloor) \cdot b_i$ satisfies the above conditions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .