lagrange_bases.tex

%\vspace{-0.05in}
\subsection{Lagrange Bases}
\label{sec:lagrange}
%\vspace{-0.05in}
For finite field $\mathbb{F}$ (see section~\ref{sec:pairings}) we denote by $H$ a subgroup of the multiplicative group of $\mathbb{F}$ such that $n = |H|$ is a large power of 2. 
Let $\omega$ be an $n$-th root of unity in $\mathbb{F}$ such that $\omega$ is a generator of $H$. A Lagrange base is the polynomial set $\{L_i(X)\} _{0 \leq i\leq n-1}$, 
where $\forall i, 0 \leq i \leq n-1$, $L_i(X)$ is the unique polynomial in $\mathbb{F}_{<n}[X]$ s. t. $L_i(\omega^i) =1$ and $L_i(\omega^j) = 0, \forall j \neq i$. 
We denote by $\block$ a power of 2 such that $\block < n$ and use $\block$ for defining one of our conditional NP relations in section \ref{sec:snarks}. 
We assume $n = \mathsf{poly} (\lambda)$ and $\block = \Theta(\lambda)$ and $|\mathbb{F}|= 2^{\Theta(\lambda)}$.
%, i.e., $|\mathbb{F}|$ is exponential in $\lambda$.}
%\vspace{-0.08in}
 
%{\color{blue} TO DO: Make the statement about $|\mathbb{F}|$ stronger. In the following we assume 
%$n= \mathsf{poly} (\lambda)$ and $|\mathbb{F}|= \lambda^{\omega(1)}$, i.e., $|\mathbb{F}|$ is super-polynomial in $\lambda$. Also, is $\block$ a constant or is $\mathsf{poly} (\lambda)$? }