Composition proof

$$\def\F{\mathbb F}$$

Context. Are values are from a

Goal. Given $P\in\F_{< N}[X]$ Proof the following constraint using Schwartz-Sippel and a $\le N$ low degree test:

$$F(G(X)) \mod H(X) = 0$$

$$\frac{P(X)^{2^{64}} - 1}{X^N - 1}$$

Lemma. Polynomials satisfying the above constraint satisfy $P(\omega_N^i) = \omega_{2^{64}}^{k_i}$ for $i \in [0,N)$.

Definition. $\F_{< N}[X] \sim \F[X]/ X^N$

Assume for the moment $N = 2^{64}$, we can generalize later

$$\frac{P(X)^N - 1}{X^N - 1}$$

This puts some constraints on the coefficients of $P$.

$$P(X) = \sum_{i\in[0,N)} p_i X^i$$

$$\frac{P(X)^N - 1}{X^N - 1} = \frac{\left(\sum_{i\in[0,N)} p_i X^i\right)^N - 1}{X^N - 1}$$

We can now expand using something like the https://en.wikipedia.org/wiki/Binomial_theorem, i.e. https://en.wikipedia.org/wiki/Multinomial_theorem.

To do. Look into differentials.

Simplifications

We can further restrict the problem to the case $h(x) = x^n - 1$. This can help because we can now factor $h$ as

$$h(x) = (x - ω_n^0) (x - ω_n^1) (x - ω_n^2) \cdots (x - ω_n^{n-1})$$

or (thanks Yan Zhang)

$$h(x) = (x - 1) (x + 1) (x^2 + 1) (x^4 + 1) \cdots (x^n + 1)$$

The problem could be broken solved modulo these factors and then invoke CRT.

References

• J. F. Ritt (1921). "Prime and Composite Polynomials". link.
• Raoul Blankertz (2014). "A polynomial time algorithm for computing all minimal decompositions of a polynomial" link
• K. S. Kedlaya, C. Umans (2011). "Fast polynomial factorization and modular composition" link

Remco Bloemen
Math & Engineering
https://2π.com