Algorithm 7: Generating Algorithm for Public Key without Noises

· Let

$d_i\left(x\right)={\displaystyle {\prod }_{\begin{array}{c}j=1\\ j\ne i\end{array}}^m}\left(x^{n-1}+q_j\right),1\le i\le m.$

Since polynomial $x^{n-1}+q_i$ and $x^{n-1}+q_j\left(j\ne i\right)$ are relatively prime in $\mathbb{Z}\left[x\right]/\langle \varphi \left(x\right)\rangle$ , it follows that $\left(x^{n-1}+q_i\mathrm{,}{d}_i\left(x\right)\right)=1$ . Therefore, there is a polynomial ${\mathcal{D}}_i\left(x\right)$ such that

$d_i\left(x\right){\mathcal{D}}_i\left(x\right)\equiv 1\left(\text{mod}\left(x^{n-1}+q_i\right)\right)\mathrm{.}$

We obtain ${\mathcal{D}}_i=\tau \left({\mathcal{D}}_i\left(x\right)\right)$ under the mapping $\tau$ given in section 2.