Dans cette thèse, nous discutons d’aspects algorithmiques de trois différents problèmes, en lien avec la cryptographie. La première partie est consacrée à l’algèbre linéaire creuse. Nous y présentons un nouvel algorithme de pivot de Gauss pour matrices creuses à coefficients exacts, ainsi qu’une nouvelle heuristique de sélection de pivots, qui rend l’entière procédure particulièrement efficace dans certains cas. La deuxième partie porte sur une variante du problème des anniversaires, avec trois listes. Ce problème, que nous appelons problème 3XOR, consiste intuitivement à trouver trois chaînes de caractères uniformément aléatoires de longueur fixée, telles que leur XOR soit la chaîne nulle. Nous discutons des considérations pratiques qui émanent de ce problème et proposons un nouvel algorithme plus rapide à la fois en théorie et en pratique que les précédents. La troisième partie est en lien avec le problème learning with errors (LWE). Ce problème est connu pour être l’un des principaux problèmes difficiles sur lesquels repose la cryptographie à base de réseaux euclidiens. Nous introduisons d’abord un générateur pseudo-aléatoire, basé sur la variante dé-randomisée learning with rounding de LWE, dont le temps d’évaluation est comparable avec celui d’AES. Dans un second temps, nous présentons une variante de LWE sur l’anneau des entiers. Nous montrerons que dans ce cas le problème est facile à résoudre et nous proposons une application intéressante en re-visitant une attaque par canaux auxiliaires contre le schéma de signature BLISS. / In this thesis, we discuss algorithmic aspects of three different problems, related to cryptography. The first part is devoted to sparse linear algebra. We present a new Gaussian elimination algorithm for sparse matrices whose coefficients are exact, along with a new pivots selection heuristic, which make the whole procedure particularly efficient in some cases. The second part treats with a variant of the Birthday Problem with three lists. This problem, which we call 3XOR problem, intuitively consists in finding three uniformly random bit-strings of fixed length, such that their XOR is the zero string. We discuss practical considerations arising from this problem, and propose a new algorithm which is faster in theory as well as in practice than previous ones. The third part is related to the learning with errors (LWE) problem. This problem is known for being one of the main hard problems on which lattice-based cryptography relies. We first introduce a pseudorandom generator, based on the de-randomised learning with rounding variant of LWE, whose running time is competitive with AES. Second, we present a variant of LWE over the ring of integers. We show that in this case the problem is easier to solve, and we propose an interesting application, revisiting a side-channel attack against the BLISS signature scheme.

Dans cette thèse nous présentons la formalisation de trois résultats principaux que sont la forme normale de Jordan d’une matrice, le théorème de Bolzano-Weierstraß et le théorème de Perron-Frobenius. Pour la formalisation de la forme normale de Jordan nous introduisons différents concepts d’algèbre linéaire tel que les matrices diagonales par blocs, les matrices compagnes, les facteurs invariants, ... Ensuite nous définissons et développons une théorie sur les espaces topologiques et métriques pour la formalisation du théorème de Bolzano-Weierstraß. La formalisation du théorème de Perron-Frobenius n’est pas terminée. La preuve de ce théorème utilise des résultats d’algèbre linéaire, mais aussi de topologie. Nous montrerons comment les précédents résultats seront réutilisés. / In this thesis we present the formalization of three principal results that are the Jordan normal form of a matrix, the Bolzano-Weierstraß theorem, and the Perron-Frobenius theorem. To formalize the Jordan normal form, we introduce many concepts of linear algebra like block diagonal matrices, companion matrices, invariant factors, ... The formalization of Bolzano-Weierstraß theorem needs to develop some theory about topological space and metric space. The Perron-Frobenius theorem is not completly formalized. The proof of this theorem uses both algebraic and topological results. We will show how we reuse the previous results.

Cette thèse vise à développer des stratégies permettant d'augmenter la puissance du calcul séquentiel et des systèmes distribués, elle traite en particulier, la décomposition séquentielle des opérations ainsi que des systèmes d'édition collaboratifs décentralisés. Nous introduisons, une méthode d'indexage avec précision contrôlée. Celle-ci permet la génération d'identifiants uniques utilisés dans l'indexage des communications dans les systèmes distribués, plus particulièrement dans les systèmes d'édition collaboratifs décentralisés. Ces identifiants sont des nombres réels avec un motif de précision contrôlé. Un ensemble fini d'identifiants est conservé pour permettre le calcul de cardinalités locales et globales. Cette propriété joue un rôle prépondérant dans la gestion des communications indexées. De plus, d'autres propriétés incluant la préservation de l'ordre sont observées. La méthode d'indexage a été testée et vérifiée avec succès. Ceci a permis la conception d'un système d'édition collaboratif décentralisé. Aussi, nous explorons les stratégies existantes, relatives a la décomposition séquentielle d'opérations, que nous étendons à de nouvelles stratégies. Ces stratégies mènent à une optimisation (processeur, compilateur, mémoire, code). Ces styles de décomposition portent un intérêt majeur à la communauté scientifique. Des recherches et des implémentations de plus en plus rapides résultent de la conception d'unité arithmétique. / This thesis aims at developing strategies to enhance the power of sequential computation and distributed systems, particularly, it deals with sequential break down of operations and decentralized collaborative editing systems. In this thesis, we introduced precision control indexing method that generates unique identifiers which are used for indexed communication in distributed systems, particularly, in decentralized collaborative editing systems. These identifiers are still real numbers with a specific controlled pattern of precision. Set of identifiers is kept finite that makes it possible to compute local as well as global cardinality. This property plays important role in dealing with indexed communication. Besides this, some other properties including order preservation are observed. The indexing method is tested and verified by experimentation successfully and it leads to design decentralized collaborative editing system. Dealing with sequential break down of operations, we explore limitations of the existing strategies, extended the idea by introducing new strategies. These strategies lead towards optimization (processor, compiler, memory, code). This style of decomposition attracts research communities for further investigation and practical implementation that could lead towards designing an arithmetic unit.

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.

Notre recherche porte sur la question de l'enseignement de l'algèbre linéaire au niveau universitaire, plus précisément sur les applications linéaires en Classes Préparatoires aux Grandes Écoles. La théorie des situations didactiques avec la sémiotique de Peirce fournissent le cadre principal de nos travaux et nous permettent d'analyser les raisonnements produits par les étudiants en situation d'interrogation orale. Nous proposons dans un premier temps des éléments d'analyse épistémologique concernant le rôle des applications linéaires dans l'émergence de l'algèbre linéaire. Puis nous présentons dans une optique d'analyse didactique les principaux éléments de la sémiotique de Peirce et son algébrisation par le treillis des classes de signes. Nous complétons alors le modèle d'analyse des raisonnements de Bloch et Gibel et proposons un outil d'analyse sémiotique, le diagramme sémantique. Nous utilisons cet outil pour une analyse sémiotique locale a priori d'une situation mathématique. Cette analyse met en évidence le lien entre les premiers signes et premières actions de la situation et la sémiose qui en découle. Nous procédons ensuite à une analyse des raisonnements produits par des étudiants en situation d'interrogation orale, dite « classique ». Cette analyse confirme le lien entre l'absence de niveaux de milieu adidactiques et la difficulté sémantique d'organiser les objets en situation de preuve. Puis, nous expérimentons une situation d'interrogation orale de telle sorte que les niveaux de milieu adidactiques soient riches et stabilisés. L'analyse des raisonnements produits dans cette situation nous permet de montrer que les étudiants sollicitent un point de vue sémantique sur les objets utile lors de leurs validations et contrôles. Ces trois moments de notre travail confirment l'importance du discours et des pratiques heuristiques dans le cadre de l'algèbre linéaire. / Our research is concerned with the teaching of linear algebra at the university level. More precisely, it focuses on the teaching of linear transformations in Classes Préparatoires aux Grandes Écoles. The theory of didactical situations, jointly with Peirce’s semiotics, constitute the main theoretical framework of our works and allow us to analyse student’s reasoning in situations of oral evaluation. Firstly, we put forward some epistemological aspects highlighting the links between linear transformations and the emergence of linear algebra. Then, with a didactical objective, we outline the main features of Perice’s semiotics and its algebraization with the treillis of sign’s categories. Hence, we can enhance the model of analysis for reasoning processes of Bloch and Gibel and build a tool for semiotic analysis called semantic diagram. We illustrate the use of this tool by conducting a local semiotic a priori analysis of a mathematical situation. This analysis highlight the link between the first signs and actions of the situation and the resulting semiosis. Next, we analyse some students’ reasonings produced during oral evaluations said « classical ». This analysis confirms the link between the lack of an adidactical milieu and the semantic difficulty to organize and articulate the objects and signs in a proof situation. Then we experiment a situation of oral evaluation in which the adidactical milieus are rich enough and stabilized. The analysis of the reasoning process conducted in this experimental situation allows us to show that, in this case, the students rely on a semantic point of view on the objects to produce their validations and controls their productions. These three different moments of our research attest the importance of the heuristic practices and discourse in the field of linear algebra.

Cette thèse présente les limites du mode s.i.m.d. Dans le cadre de la programmation parallèle d'algorithmes d'algèbre linéaire. Plus précisément, celles de la règle d'or du parallélisme massif: un élément de la matrice par processeur, sont développées. Des expérimentations sont effectuées sur une connection machine 2. Néanmoins, la première partie montre comment la création de procédures de communications écrites a partir d'un nouvel algorithme de construction d'arbres équilibres, et un placement de données judicieux permettent d'atteindre des performances proches de la puissance crête. Mais ce type de travail ne peut pas être effectue sur n'importe quel algorithme, et tout ne s'adapte pas aussi bien. Dans la deuxième partie, nous présentons les avantages de la décomposition en blas pour la construction d'algorithmes massivement parallèles. Elle met, dans le chapitre 4, en évidence la barrière de synchronisation pour la methode du gradient conjugue. Nous proposons dans ce cas particulier comme solution, une ancienne methode qui bien qu'elle soit, en séquentiel, de convergence plus lente, est plus rapide en parallèle. De plus, la structure des matrices est un facteur important. Elle permet d'accélérer les calculs et d'augmenter la dimension des problèmes a résoudre. L'architecture des machines actuelles en limite encore trop l'utilisation. La dernière partie est entièrement consacrée aux permutations, et aux communications qu'elles entrainent. Dans le cadre de l'algorithme de Burg, nous proposons une solution qui calcule a la fois les coefficients de réflexion et ceux d'autoregression sans cout supplémentaire

L'ensemble des travaux sur lesquels s'appuie la note de synthèse présente une unité évidente autour du thème de l'algèbre linéaire. Nous dégageons un autre type d'unité portant non pas sur le contenu mathématique étudié mais sur la méthodologie de recherche employée, tout en en soulignant l'originalité. Notre but est de montrer le rôle central joué dans nos travaux didactiques par l'interaction avec nos recherches historiques. Nous abordons cette question sous un angle plus général, en dégageant, au delà du seul exemple de l'algèbre linéaire, la nature des interactions possibles entre recherches historique et didactique et leur apport épistémologique, en dégageant également des questions de méthodologie. Nous nous appuierons sur diverses de nos publications pour construire notre réflexion.

Cette thèse est consacrée a l'étude de la forme normale d'Hermite et a la conception d'algorithmes parallèles pour son calcul. Nous avons examine deux cas particuliers: le cas entier et le cas polynomial. Ce problème présente de manière intrinsèque une caractéristique du calcul formel: le grossissement des coefficients intermédiaires. Cette particularité en fait un exemple test pour évaluer la parallélisation en calcul formel. La forme normale d'Hermite pour des matrices a coefficients dans un anneau euclidien est présentée. Les concepts et propriétés sur lesquels sont bases les algorithmes sont décrits. Nous introduisons la théorie sur les réseaux et les problèmes qui lui sont attaches, la forme normale d'Hermite étant une forme canonique du réseau engendre par les colonnes de la matrice initiale. Les différents algorithmes séquentiels sont présentes. Nous étudions et comparons leurs complexités. Puis, une approche parallèle est considérée. Après la présentation des résultats théoriques de nc-réductibilité du problème, nous abordons l'étude de la parallélisation sur modèles expérimentaux. Nous définissons différents algorithmes pour les modèles a mémoire partagée et distribuée. Une implantation a été réalisée sur un hypercube fps t40 (32 processeurs). Le calcul de la forme normale d'Hermite d'une matrice 160160 à coefficients entiers a pu etre effectue en 3 heures. Ce travail s'inscrit dans le cadre du projet massivement Parallele Pac (parallel algebraic computing).

Parallélisation de quelques algorithmes d'algèbre linéaire à l'aide du formalisme du graphe des taches

Les ressources souterraines fournissent une part importante de l'eau douce de notre planète. Notre travail s'inscrit dans une démarche de protection de cette ressource vitale par la modélisation et la simulation numérique. Couplée aux études de terrains, la simulation numérique est en effet un outil indispensable, du fait de l'incertitude sur le milieu géologique. Cette incertitude conduit à une approche stochastique. Nous nous sommes concentrés sur les écoulements dans les réseaux de fractures générés aléatoirement. Pour permettre la résolution de ces écoulements par une méthode d'éléments finis mixte hybride, nous avons élaboré un algorithme de maillage spécifique aux fractures. Cette technique permet de construire le système linéaire quelle que soit la géométrie du réseau généré. Nous avons ensuite effectué une étude comparative de trois solveurs linéaires : un solveur direct, un multigrille algébrique et un Gradient Conjugué Préconditionné. Cette étude nous a conduit à proposer une méthode de résolution plus efficace pour ce problème. Nous avons alors étudié une méthode de décomposition de domaine de type Schur, qui permet d'allier les avantages du solveur direct et du Gradient Conjugué Préconditionné. Cette méthode consiste à réduire le problème à un problème aux interfaces, par une définition naturelle des fractures, ou paquets de fractures, comme sous-domaines. Nous avons proposé une approche originale d'optimisation de l'algorithme et un préconditionnement global de type déflation. Notre implémentation de cette méthode est compétitive. Elle permet de résoudre tous les cas tests étudiés et elle est plus rapide, dans la majorité des cas, que les trois autres solveurs.