Abstract FR:

Le premier chapitre de ce travail consiste en l'etude de base lll#(##)-reduite et d'un algorithme effectuant une telle reduction. Nous avons mesure, s. V. Designant la norme d'un plus court vecteur du reseau engendre par la famille (b#1,. . ,b#n). A) l'influence du choix de sur les nombres moyens de bases aleatoires b#-#1,. . ,b#-#n satisfaisant respectivement 1) s. V=l(b#-#1) ; 2) s. V=l(b#-#i), avec 2in ; 3) s. Vl(b#-#i), pour tout i, 1in. B) l'influence du type de tir aleatoire sur les resultats de a) ; ou (b#-#i) designe un vecteur quelconque de la base lll#(##)-reduite. A partir des resultats experimentaux nous constatons que: a) le pourcentage des bases satisfaisant 1) augmente avec. B) l'influence du choix du tir aleatoire sur les resultats de a) n'est pas notable. Nous avons egalement compare les longueurs des differents vecteurs d'une famille lll#(##)-reduite, et cela suivant que vaut 0. 75 ou 0. 99. A partir des resultats experimentaux nous constatons que: a) toute famille lll#(#0#. #9#9#)-reduite est ordonnee, i. E. L(b#-#1)<<l(b#-#n) ; ce n'est pas le cas si =0. 75. B) l(b#-#1)#0#. #9#9<l(b#-#1)#0#. #7#5: la longueur du premier vecteur d'une base reduite decroit lorsque augmente. C) le temps de reduction d'une base augmente avec. Le deuxieme chapitre de notre travail consiste en l'etude de la notion de base reduite au sens de korkine-zolotareff (kz-reduite) et d'un algorithme effectuant une telle reduction. Nous avons mesure: 1) l'influence du choix du sur les nombres moyen de bases qui, lll#(##)-reduites et telles que s. V=l(b#-#1), sont egalement kz-reduites. 2) le temps moyen de calcul. Dans le troisieme chapitre de notre travail nous etudions le probleme dit du sac a dos de parametres (a,s) qui, reformule en termes de reseaux. Le reseau l(a,s) n'est pas unique ; coster, lamacchia, odlyzko et schnorr 5 d'une part, joux et stern 11 d'autre part, proposent de tel(le)s (bases de) reseaux ; nous les avons employees comme bases initiales de l'algorithme dit floating point algorithm ; nous en avons compare l'efficacite. Nous avons particulierement etudie au moyen de la base fournie dans 5, le nombre moyen de solutions obtenues et la variation de cette moyenne en fonction de la densite du probleme. Nous avons egalement etudie le probleme dit du sac a dos, a deux equations. Pour cela, nous avons adapte la base fournie dans 5 de maniere a formuler ce probleme en termes de reseaux. Dans la deuxieme partie de notre travail nous avons employe les methodes de la programmation lineaire pour resoudre le probleme de factorisation des entiers. Precisement, nous nous proposons de resoudre, etant donne un entier positif z (dans nos experimentations z<2#1#5), le probleme de programmation lineaire (l. P. P. ) dont le systeme d'equations s represente l'unique equation binaire x. Y = z, x et y etant entiers. L'ensemble des entiers peut etre divise en deux parties s-z1 et s-z2 suivant que la solution du l. P. P. De parametre z a ou n'a pas tous ses coefficients dans 0,1. De plus, chacun des ensembles s-z1 et s-z2 admet une partition en deux classes, respectivement s-z1-1, s-z1-2 et s-i-z2, s-r-z2 ; en particulier, les solutions du l. P. P. Associe aux parametres z elements de s-z1-1 ou s-i-z2 fournissent une factorisation