Number Theory: What does $\theta_i$ mean here?

62 Views Asked by At

(Posting this again since the last one was an image and people told me to write it down).

Found this from this paper (Page 4; Section 4.1). Image version.

I wanted help in understand what $\theta_{i}$ and $x = ( x_{1},\dots,x_{k} ) _{\equiv}$ mean here.

Is $\theta$ a 'sequence' of zero's and then a one at the i'th position? If so, how does one calculate something like $\alpha_{i}^{\delta{i}} \ \theta_{i} = \mathbb{mod} \ \mathit{\Pi}$ where $\alpha_{i} \in \{1, 0\}^{t}$ and $\{0, 1\}^{t}$ is a set of t-bit numbers. (Page 2; Section 1)

The definitions of the notation:

Let $\mathit{\Pi} = \prod_{i=1}^{k}{p_{i}^{\delta_{i}}}$ be the $n$-bit product of the first $k$ primes with some small exponents $\delta_{i}$, and let $\Delta = \textrm{max}_{i}\delta_{i}$. We denote by $x = ( x_{1},\dots,x_{k} ) _{\equiv}$ the modular representation of $x \in \mathbb{Z}_{\mathit{\Pi}}$, i.e., $x_{i} = x \bmod \ p_{i}^{\delta_{i}}$. For $i = 1, \dots, k$, one then defines $\theta_{i} = (0, \dots, 1, \dots, 0)_{\equiv}$ where the "$1$" stands for the $i^{\text{th}}$ position. It is obvious to see that we always have: $$\forall x \in \mathbb{Z}_{\mathit{\Pi}}\qquad x = \sum_{i=1}^{k}x_{i} \theta_{i} \bmod{\mathit{\Pi}}$$ [some proof/reasoning here for the calculations below] $$\begin{align}\forall x \in \mathbb{Z}_{\mathit{\Pi}} \qquad \forall x \in \mathbb{Z}^{*}_{\mathit{\Pi}} &\Longleftrightarrow x_{i} \in \mathbb{Z}^{*}_{p_{i}^{\delta_{i}}} \\ &\Longleftrightarrow x_{i}^{\delta_{i}} \not\equiv 0 \pmod{ p_{i}^{\delta_{i}}} \\ &\Longleftrightarrow x_{i}^{\delta_{i}} \theta_{i} \not\equiv 0 \pmod{\mathit{\Pi}} \;\text{for $i = 1, \dots, k$} \end{align}$$