Polynomials to Compute:

\(P(X,Y)=\sum_{i=1}^m \lambda_i(X)\mu_i(Y)\), where \(\{\lambda_i(X)\}_{i=1}^m\) is the set of interpolation polynomials for the subgroup \(\mathbb{H}=\{1, \omega, \ldots, \omega^{m-1}\}\) of size \(m\), while \(\{\mu_i(X)\}_{i=1}^M\) interpolate the subgroup \(\mathbb{V}=\{1, \nu, \ldots, \nu^{M-1}\}\), M>m.
Is \(\mathbb{H}\subset\mathbb{V}??\)

If \(\mathbb{H}\subset\mathbb{V}\) then as
\[ \lambda_i(X) = \frac{\omega^i(X^m-1)}{m(X-\omega^i)}; \quad \mu_j(X) = \frac{\nu^j(X^M-1)}{M(X-\nu^j)} \]
we have
\[ \omega = \nu^t \]
and
\[ \lambda_i(X) = \frac{\nu^{it}(X^m-1)}{m(X-\nu^{it})} = \mu_{it}(X)\frac{(X^m-1)t}{(X^{mt}-1)} \]

\[ X^M-1=(X^m-1)z_{V\setminus H}(X), \ z_{V\setminus H}(X)=\prod_{n \in I} (X^n-\nu^n) \]

Where \(I=\{n \ s.t. \ n=2^k \ and \ m<n<M \}\)

\(a(X)=\sum_{i=0}^{2^m-1}i\lambda_i(X)\). Can we compute \(a(\alpha)\) fast?. a(X) is a polynomial that approximates the function \(\log\), so probably not. (see reference)

Discrete logarithm as a polynomial: https://core.ac.uk/download/pdf/82390964.pdf
http://matwbn.icm.edu.pl/ksiazki/aa/aa47/aa4735.pdf

\[ a(\omega X ) = a(X)+1 \text{ for }X\in \mathbb{H} \]

\(D(X,Y)=\sum_{i=1}^m X^{i-1}\lambda_i(Y)\)