# Polynomial Breakdown in proof of lower bounds on Discrete Log in the Generic Group

In Shoup's proof of the hardness of discrete log in the generic group in this paper, he mentions that:

At any step in the game, the algorithm has computed a list $$F_1,\dots,F_k$$ of linear polynomials in $$Z/p^t[X]$$ along with a list of values $$z_1,\dots,z_k$$ in $$Z/s$$, and a list $$\sigma_1,\dots,\sigma_k$$ of distinct values in $$S$$.

The algorithm is initially given the encodings of $$1,x$$ and access to the group operation + inverses so it is clear that anything the algorithm computes can be expressed as a linear polynomial in $$Z/n[X]$$, where $$n=p^t s$$. However, I don't see how this breaks down into a linear polynomial in $$Z/p^t[X]$$ and a constant in $$Z/s$$.

$$n$$ and $$p^t$$ are coprime numbers. Then, we can use the Chinese remainder theorem to deduce a ring isomorphism $$\phi$$ from $$\mathbb{Z}_n$$ to $$\mathbb{Z}_s\times \mathbb{Z}_{p^t}.$$

And $$\phi$$ is just $$y \mapsto (y \mod s, y \mod p^t).$$

In the proof, the value of $$(x\mod s)$$ is chosen uniformly at random at the beginning of the game : it's $$z_2$$ in the paper. But $$x \mod p^t$$ is written as the indeterminate $$X$$ by the challenger (it's $$F_2$$). Because $$1 \mod s = 1$$ and $$1 \mod p^t =1$$, $$(z_1,F_1)=(1,1).$$

Then for all the new elements, they are written as a linear combination of $$x$$ and $$1$$ in $$\mathbb{Z}_n$$ and also (by using the chinese remainder theorem) as a linear combination of $$(z_2, X)$$ and $$(1,1)$$ in $$\mathbb{Z}_n$$.

To compute the new coefficients for the $$k^{th}$$ element which is decomposed as $$\lambda_1 \cdot 1 + \lambda_x \cdot x$$ in $$\mathbb{Z}_n$$, you have to use the ring isomorphism $$\phi.$$

$$\phi(\lambda_1 \cdot 1 + \lambda_x \cdot x) = \phi(\lambda_1 \cdot 1) + \phi(\lambda_x \cdot x) = \phi(\lambda_1) +\phi(\lambda_x) \cdot(z_2, X)$$

$$=(\lambda_1 \mod s, \lambda_1 \mod p^t) + (\lambda_x \cdot z_2 \mod s, (\lambda_x \mod p^t)\cdot X)$$ $$= ((\lambda_1 +\lambda_x \cdot z_2) \mod s, \lambda_1 \mod p^t +(\lambda_x \mod p^t)\cdot X)$$

We deduce that $$z_k=(\lambda_1 +\lambda_x \cdot z_2) \mod s$$ and $$F_k =\lambda_1 \mod p^t +(\lambda_x \mod p^t)\cdot X).$$