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.
Bonjour!
Catégories
- 164.9K Toutes les catégories
- 58 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 57 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 50 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 83 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 77 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 334 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 796 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres