Système d'équations non-linéaires

Bonjour à tous,

Soient $q$ un entier premier (grand), $d,\kappa\in \mathbb{N}^*$
On considere l'ensemble des polynomes $P_d=\mathbb{Z}_q[X_1,\ldots,X_\kappa]$ définis par

$$P_d=\left\lbrace  \sum_{ije}a_{ije}X_i^eX_j^{d-e}| a_{ije}\in \mathbb{Z}_q\right\rbrace$$

On choisit aléatoirement :
 - deux polynômes $p_1,p_1'$ dans $P_d$
- $\kappa-1$ polynômes $p_2,\ldots,p_\kappa$ ayant les mêmes monomes que $p_1\times p_1'$
- une matrice inversible $S$ dans $\mathbb{Z}_q^{\kappa \times \kappa}$

On calcule ensuite les polynomes $r_1,\ldots,r_\kappa$ définis par:

$$(r_1,\ldots,r_\kappa)=S^{-1}(p_1\times p_1',p_2,\ldots,p_\kappa)$$

Problème. Retrouver $s_{11}/s_{12}$ ne connaissant que les coefficients des monômes des  polynômes $r_1,\ldots,r_\kappa$ 

Solution. Par construction, on a
$$\langle s_1,(r_1(u),\ldots,r_\kappa(u))\rangle=p_1(u)\times p_1'(u)$$
pour tout $u\in\mathbb{Z}_q^{\kappa}$ où $s_1$ est la première ligne de $S$ . En échantillonnant $u$ dans $\mathbb{Z}_q^{\kappa}$, on obtient des équations quadratiques où les variables sont : $s_{11},\ldots,s_{1\kappa}$ ainsi que les coefficients des monômes de $p_1,p_1'$.
En utilisant fonction Ideal\_elimination() de SageMath (on élimine toutes les variables sauf $s_{11},s_{12}$), on parvient a résoudre le problème.

Mais c'est très lent...plusieurs heures avec $\kappa=5,d=2$...peut-on faire mieux? Y aurait-il une méthode plus adaptée?

Merci à vous









Connectez-vous ou Inscrivez-vous pour répondre.