.

Ce mémoire présente mes travaux de recherche de 1988 à 2001, travaux effectués d'abord à l'INRIA Rocquencourt au sein du projet Algo (1988 à 1992), puis à l'INRIA Lorraine et au LORIA dans les projets Euréca (1993 à 1997), PolKA (1998 à 2000), et Spaces (2001). Au niveau thématique, on peut distinguer grosso modo trois phases : une première période allant de 1988 à 1992 où j'ai surtout travaillé sur l'analyse d'algorithmes et la génération aléatoire, une seconde période de 1993 à 1997 où je me suis investi dans le calcul formel et les algorithmes sous-jacents, enfin une troisième période depuis 1998 où je me suis intéressé aux problèmes d'arithmétique exacte en précision arbitraire.

Dans la littérature, plusieurs recherches parlent du potentiel de l'utilisation de la technologie dans l'apprentissage de l'algèbre au secondaire. Cependant, peu de ces recherches portent sur la factorisation. Mon travail de recherche a été motivé par ces deux faits et avait pour objectif d'explorer si la calculatrice symbolique pouvait jouer un rôle significatif dans l'apprentissage de la factorisation. Dans ma recherche, je me suis inspirée de l'approche technique/théorique développée par Chevallard (1999), et adaptée ensuite par Artigue (2002a) et Lagrange (2000). Dans cette approche, les composantes technique et théorique sont étroitement liées et la dimension théorique ne peut progresser, dans les environnements technologiques, sans la présence de la dimension technique. Mon but a donc été d'explorer le rôle d'une approche technique/théorique, intégrée dans un environnement où l'on utilise la calculatrice symbolique, pour l'apprentissage de la notion de factorisation chez des élèves en 4ième secondaire. Pour atteindre ce but, j'ai fait une étude comparative entre deux groupes d'élèves de 4ième secondaire ayant des difficultés en algèbre: un groupe dont les élèves avaient chacun accès à une calculatrice symbolique (6 élèves) et un groupe où tel n'était pas le cas (10 élèves). Des feuilles d'activités avec des questions similaires pour les deux groupes ont été réalisées. Avant d'accomplir la séquence didactique composée des activités, les élèves avaient fait un pré-test pour que je puisse voir si les deux groupes avaient des connaissances semblables dans les composantes technique et théorique. La séquence didactique a été suivie par un post-test pour explorer les acquis des élèves et les différences entre les deux groupes. Des notes ont été consignées dans un journal de bord pour chacun des cours avec les deux groupes. De plus, j'ai été l'enseignante des deux groupes lors de cette étude. En comparant les résultats au pré-test des deux groupes, on s'est aperçu qu'ils étaient similaires pour la dimension technique, mais qu'iIs étaient légèrement plus forts pour la dimension théorique dans un groupe. Cependant, les résultats pour la dimension théorique étaient très bas dans les deux groupes. Les résultats au post-test nous ont indiqué que le groupe avec la calculatrice symbolique a accompli plus d'améliorations que le groupe sans calculatrice et ce, dans les deux dimensions (technique et théorique). À la suite de l'analyse des notes gardées dans le journal de bord et des réponses contenues dans les feuilles d'activités des élèves des deux groupes, on a pu dégager trois fonctions remplies par la calculatrice symbolique, qui expliqueraient les améliorations chez les élèves du groupe avec celle-ci. Les trois fonctions jouées par la calculatrice étaient les suivantes: la fonction génératrice de formes exactes, la fonction vérificatrice et la fonction instigatrice de discussions. Cette recherche m'a permis de réaliser que le fait d'avoir rendu accessible une calculatrice à des élèves ayant des difficultés en factorisation a eu un apport positif. En fait, ces jeunes ont plus appris avec cet outil, tant au niveau technique que théorique, que les autres élèves qui n'ont pas eu accès à cet outil. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Factorisation, Calculatrice symbolique, Système de calcul formel, Technique, Théorie, Théorique, Vérificatrice, Génératrice de formes exactes, Instigatrice de discussions.

Thèse doctorat : Informatique : Lille 1 : 2003. / N° d'ordre (Lille 1) : 3296. Résumé en français et en anglais. Bibliogr. p. 133-136.

Reproduction de : Thèse de doctorat : informatique : Grenoble, INPG : 1988. / Titre provenant de l'écran-titre. Bibliogr. p. 155-159.

Pac est un système de calcul formel dédié a une machine Mind massivement parallèle. Dans une première partie, l'architecture du système est décrite. Elle est illustrée par une modélisation théorique et pratique de la parallélisation du produit de deux polynômes. Le système Pac est implante sur la machine t40 de Fps (32 processeurs). Dans une deuxième partie, l'arithmétique nodale en précision infinie sur les rationnels est étudiée. Différents algorithmes sont dégagés, notamment pour la multiplication, la division et le pgcd d'entiers de taille quelconque. Une vectorisation de l'arithmétique de base est discutée et expérimentée

Le calcul de l'infimum global $f^*$ d'un polynôme à $n$ variables sous contraintes est une question centrale qui apparaît dans de nombreux domaines des sciences de l'ingénieur. Pour certaines applications, il est important d'obtenir des résultats fiables. De nombreuses techniques ont été développées dans le cas où les contraintes sont données par des inéquations polynomiales. Dans cette thèse, on se concentre sur le problème d'optimisation d'un polynôme à $n$ variables sous des contraintes définies par des équations polynomiales à $n$ variables. Notre but est d'obtenir des outils, algorithmes et implémentations efficaces et fiables pour résoudre ces problèmes d'optimisation. Notre stratégie est de ramener le problème d'optimisation sous des contraintes qui définissent des ensembles algébriques de dimension quelconque à un problème équivalent, sous des nouvelles contraintes dont on maîtrise la dimension. La variété algébrique définie par ces nouvelles contraintes est l'union du lieu critique du polynôme objectif et d'un ensemble algébrique de dimension au plus 1. Pour cela, on utilise des objets géométriques définis comme lieux critiques de projections linéaires. Grâce au bon contrôle de la dimension, on prouve l'existence de certificats pour des bornes inférieures sur $f^*$ sur nos nouvelles variétés. Ces certificats sont donnés par des sommes de carrés et on ne suppose pas que $f^*$ est atteint. De même, on utilise les propriétés de nos objets géométriques pour concevoir un algorithme exact pour le calcul de $f^*$. S'il existe, l'algorithme renvoie aussi un minimiseur. Pour un problème avec $s$ contraintes et des polynômes de degrés au plus $D$, la complexité est essentiellement cubique en $(sD)^n$ et linéaire en la complexité d'évaluation des entrées. L'implantation, disponible sous forme de bibliothèque Maple, reflète cette complexité. Elle a permis de résoudre des problèmes inatteignables par les autres algorithmes exacts.

Cette thèse est composée de deux axes principaux, le premier portant sur le chiffrement homomorphe et le second sur l’algèbre linéaire creuse sur corps finis. Avec l’essor des technologies de communication et en particulier d’internet, de nouveaux protocoles de chiffrement sont développés. En particulier, le besoin de systèmes de chiffrement permettant de manipuler les données chiffrées tout en assurant leur sécurité. C’est dans ce contexte que des systèmes de chiffrement homomorphe sont développés, ces protocoles permettent d’effectuer des calculs avec des données chiffrées. La sécurité de ce type système repose sur l’ajout de bruit aux messages à chiffrer. Ce bruit augmente avec chaque opération effectuée, mais il ne doit pas dépasser un certain seuil. Pour contourner ce problème, une technique nommée bootstrapping est utilisée permettant de réduire le bruit d’un chiffré. Les bootstrappings sont le goulot d’étranglement lors des calculs sur des données chiffrées, il est important d’en faire le moins possible. Or la quantité de bootstrappings à faire est déterminée par la nature des calculs à effectuer ainsi que du protocole de chiffrement utilisé.C’est dans ce contexte que notre travail intervient, nous proposons une méthode effective pour réduire le nombre bootstrappings basé sur la programmation linéaire en nombre entier. Cette méthode s’adapte à un grand nombre de protocoles de chiffrement. De plus, nous effectuons une analyse de la complexité de ce problème en montrant qu’il est APX-complet et nous fournissons un algorithme d’approximation.La résolution de système linéaire sur corps finis est une brique de calcul essentielle dans de nombreux problèmes de calcul formel. En particulier, beaucoup de problèmes produisent des matrices comprenant un grand nombre de zéros, on dit qu’elles sont creuses. Les meilleurs algorithmes permettant de résoudre ce type de système linéaire creux sont des algorithmes dits itératifs. L’opération fondamentale de ces algorithmes itératifs est la multiplication de la matrice par un vecteur ou une matrice dense. Afin d’obtenir les meilleures performances, il est important de tenir compte des propriétés (SIMD, multicoeurs, hiérarchie des caches ....) des processus modernes .C’est dans ce contexte que notre travail intervient, nous étudions la meilleure façon d’implanter efficacement cette opération sur les processeurs récents.Nous proposons un nouveau format permettant de tenir compte du grand nombre de +- 1 présents dans une matrice.Nous proposons une implantation parallèle basée sur le paradigme du vol de tâche offrant un meilleur passage à l’échelle que le parallélisme par threads.Nous montrons comment exploiter au mieux les instructions SIMD des processeurs dans les différentes opérations.Finalement, nous proposons une méthode efficace permettant d’effectuer cette opération lorsque le corps finis est multiprécision (les éléments sont stockés sur plusieurs mots machine) en ayant recours au système de représentation RNS. / This thesis is composed of two independent parts.The first one is related to homomorphic encryption and the second part deal with sparse linear algebra on finite fields.Homomorphic encryption extends traditional encryption in the sense that it becomes feasible to perform operations on ciphertexts, without the knowledge of the secret decryption key. As such, it enables someone to delegate heavy computations on his sensitive data to an untrusted third party, in a secure way. More precisely, with such a system, one user can encrypt his sensitive data such that the third party can evaluate a function on the encrypted data, without learning any information on the underlying plain data. Getting back the encrypted result, the user can use his secret key to decrypt it and obtain, in clear, the result of the evaluation of the function on his sensitive plain data. For a cloud user, the applications are numerous, and reconcile both a rich user experience and a strong privacy protection.The first fully homomorphic encryption (FHE) scheme, able to handle an arbitrary number of additions and multiplications on ciphertexts, has been proposed by Gentry in 2009.In homomorphic encryption schemes, the executed function is typically represented as an arithmetic circuit. In practice, any circuit can be described as a set of successive operation gates, each one being either a sum or a product performed over some ring.In Gentry’s construction, based on lattices, each ciphertext is associated with some noise, which grows at each operation (addition or multiplication) done throughout the evaluation of the function. When this noise reaches a certain limit, decryption is not possible anymore.To overcome this limitation, closely related to the number of operations that the HE.Eval procedure can handle, Gentry proposed in a technique of noise refreshment called“bootstrapping”.The main idea behind this bootstrapping procedure is to homomorphically run the decryptionprocedure of the scheme on the ciphertext, using an encrypted version of the secret key. In this context, our contribution is twofold. We first prove that the lmax-minimizing bootstrapping problem is APX-complete and NP-complete for lmax ≥ 3. We then propose a new method to determine the minimal number of bootstrappings needed for a given FHE scheme and a given circuit.We use linear programming to find the best outcome for our problem. The main advantage of our method over the previous one is that it is highly flexible and can be adapted for numerous types of homomorphic encryption schemes and circuits.Computing a kernel element of a matrix is a fundamental kernel in many computer algebra and cryptography algorithms. Especially, many applications produces matrices with many matrix elements equals to 0.Those matrices are named sparse matrices. Sparse linear algebra is fundamentally relying on iterative approaches such as Wiedemann or Lanczos. The main idea is to replace the direct manipulation of a sparse matrix with its Krylov subspace. In such approach, the cost is therefore dominated by the computation of the Krylov subspace, which is done by successive product of a matrix by a vector or a dense matrix.Modern processor unit characteristics (SIMD, multicores, caches hierarchy, ...) greatly influence algorithm design.In this context our work deal with the best approach to design efficient implementation of sparse matrix vector product for modern processors.We propose a new sparse matrix format dealing with the many +-1 matrix elements to improve performance.We propose a parallel implementation based on the work stealing paradigm that provide a good scaling on multicores architectures.We study the impact of SIMD instructions on sparse matrix operations.Finally, we provide a modular arithmetic implementation based on residue number system to deal with sparse matrix vector product over multiprecision finite fields.

Le problème du calcul d'isogénies est apparu dans l'algorithme SEA de comptage de points de courbes elliptiques définies sur des corps finis. L'apparition de nouvelles applications du calcul d'isogénies (crypto système à trappe, fonction de hachage, accélération de la multiplication scalaire, crypto système post quantique) ont motivé par ailleurs la recherche d'algorithmes plus rapides en dehors du contexte SEA. L'algorithme de Couveignes (1996), malgré ses améliorations par De Feo (2011), présente la meilleure complexité en le degré de l'isogénie mais ne peut s'appliquer dans le cas de grande caractéristique.L'objectif de cette thèse est donc de présenter une modification de l'algorithme de Couveignes (1996) utilisable en toute caractéristique avec une complexité en le degré de l'isogénie similaire à celui de Couveignes (1996).L'amélioration de l'algorithme de Couveignes (1996) se fait à travers deux axes: la construction de tours d'extensions de degré $ell$ efficaces pour rendre les opérations plus rapides, à l'image des travaux de De Feo (2011), et la détermination d'ensemble de points d'ordre $ell^k$ stables sous l'action d'isogénies.L'apport majeur de cette thèse est fait sur le second axe pour lequel nous étudions les graphes d'isogénies dans lesquels les points représentent les courbes elliptiques et les arrêtes représentent les isogénies. Nous utilisons pour notre travail les résultats précédents de Kohel (1996), Fouquet et Morain (2001), Miret emph{et al.} (2005,2006,2008), Ionica et Joux (2001). Nous présentons donc dans cette thèse, à l'aide d'une étude de l'action du Frobenius sur les points d'ordre $ell^k$, un nouveau moyen de déterminer les directions dans le graphe (volcan) d'isogénies. / Isogeny computation problem appeared in the SEA algorithm to count the number of points on an elliptic curve defined over a finite field. Algorithms using ideas of Elkies (1998) solved this problem with satisfying results in this context. The appearance of new applications of the isogeny computation problem (trapdoor crypto system, hash function, scalar multiplication acceleration, post quantic crypto system) motivated the search for a faster algorithm outside the SEA context. Couveignes's algorithm (1996) offers the best complexity in the degree of the isogeny but, despite improvements by DeFeo (2011), it proves being unpractical with great characteristic.The aim of this work is to present a modified version of Couveignes's algorithm (1996) that maintains the same complexity in the degree of the isogeny but is practical with any characteristic.Two approaches contribute to the improvement of Couveignes's algorithm (1996) : firstly, the construction of towers of degree $ell$ extensions which are efficient for faster arithmetic operations, as used in the work of De Feo (2011), and secondly, the specification of sets of points of order $ell^k$ that are stable under the action of isogenies.The main contribution of this document is done following the second approach. Our work uses the graph of isogeny where the vertices are elliptic curves and the edges are isogenies. We based our work on the previous results of David Kohel (1996), Fouquet and Morain (2001), Miret emph{& al.} (2005,2006,2008), Ionica and Joux (2001). We therefore present in this document, through the study of the action of the Frobenius endomorphism on points of order $ell^k$, a new way to specify directions in the isogeny graph (volcano).

Réalisation d'un petit système de calcul formel en pascal, sur micro-ordinateur, systeme dénoté SYPAC pour système PASCAL d'aide au calcul formel. Pour décrire les algorithmes de SYPAC on utilise un langage de surface note PALDES pour PASCAL ALDES, dérivant du langage ALDES supportant les systèmes sac-1 et sac-2. On a écrit a partir de la grammaire ll(1) de PALDES un compilateur de ce langage, celui-ci engendre comme code du PASCAL minimal. SYPAC est un systeme modulaire dont la partie résidente est écrite en PASCAL, et les modules recouvrables en PALDES, actuellement deux modules sont implantes : le calcul en précision infinie et le calcul sur les polynômes de z (x). Sa portabilité est assurée par le fait que le PASCAL hôte et l'UCSD PASCAL, disponible sur presque tous les micro-ordinateurs du commerce. L'utilisation prévue de SYPAC est à finalité pédagogique pour l'enseignement secondaire.