La théorie des formes modulaires de Siegel fournit de nombreuses applications en arithmétique, en géométrie algébrique et plus récemment en physique théorique. Le sujet de cette thèse est motivé par la construction d'analogues tridimensionnels de la fonction êta de Dedekind, question apparue dans la théorie des algèbres de Kac-Moody et celle des cordes ainsi qu'en géométrie algébrique. De telles formes modulaires ont été construites par V Gritsenko et V Nlkulln entre 1995 et 1998 pour les groupes paramodulalres complets. Dans cette thèse, nous repondons à cette question pour les sous-groupes de congruence des groupes paramodulaires nous obtenons une classifiation complète des formes de Siegel de diviseur le plus simple et les exhibons Nous les avons nommées dd-formes (diviseur diagonal) Notre solution repose sur l'utilisation de formes de Jacobi et deux types de relèvements. En 1979, H. Maass proposa une construction de formes modulaires de Siegel à partir de formes de Jacobl d'indice 1 En 1993, V Gritsenko généralisa cette construction aux formes de Jacobi d'indice t. Nous les généralisons aux sous-groupes de congruencc de SL(2:Z) On obtient ainsi des formes modulaires de Siegel pour des sous-groupes des groupes paramodulaircs. Il s'agit de relévements artthmétiques Ensuite, nous construisons un relèvement multiplicatif ou produit automorphe de Borcherds à partir de formes de Jacobi presque holomorphes de poids 0 et d'indice t pour le sous-groupe de congruence de type de Heckc Gamma0(N). Cette construction généralise celle proposée par V Gntsenko et V Nikulin en 1998. Les dd-formes sont des formes rètlexives. Elles nous ont permis de retrouvcr la structure de certains anneaux gradués de formes modulaires / The theory of Siegel modular forms gives us a lot of applications in arithmetic, algebraic geometry and more recently in physics. The subject of this dissertation is motivated bv the construction of a three-dimensional analogue of the eta function of Dedekind, problem arisen in the theory of Lorentzian KacMoody Lie algebras, algebraic geometrv and also in string theory Such modular forms have been bullt bv V Gntsenko and V Nikulin betw\een 1995- 1998 for the full paramodular groups. ln this dissertation, wc answer to this problem for congruence subgroups of paramodular groups we obtain a complete classification of thc Siegel modular forms with the simplest divisor and we produce ail of them. We called them dd-forms (modular forms with diagonal diyisor) Our solution is based on the use of Jacobi forms and two types of liftings. ln 1979, H. Maass proposed a construction of Siegel modular forms by using Jacobi forms of index one. ln 1993, V Gritsenko generalized this construction to Jacobi forms of index t. We generalize these ones to congruence subgroups of SL(2;Z). ln this way, we obtain Siegel modular forms for subgroups of the full paramodular groups. We call such a construction artthmetlc lifting. Then we construct a multiplicative lifting or Borcherds' automorphic product by using nearly holomorphic Jacobi forms of weight 0 and index t for congruence subgroups of Heeke type Gamma0(N). This construction generalizes the one proposed bv V Gritsenko and V Nlkulln in 1998 The dd-forms are retlectives modular forms.Thev have allowed us new proofs of the structure of some graded rings of modular forms

Les limites physiques des circuits à base de silicium étant en passe d'être atteintes, de nouveaux moyens doivent être trouvés pour outrepasser la fin de la loi de Moore. Beaucoup d'applications peuvent tolérer des approximations dans leurs calculs à différents niveaux, sans dégrader la qualité de leur sortie, ou en la dégradant de manière acceptable. Cette thèse se concentre sur les architectures arithmétiques approximatives afin de saisir cette opportunité. Tout d'abord, une étude critique de l'état de l'art des additionneurs et multiplieurs approximatifs est présentée. Ensuite, un modèle de propagation d'erreur virgule-fixe mettant en œuvre la densité spectrale de puissance est proposée, suivi d'un modèle de propagation du taux d'erreur binaire positionnel des opérateurs approximatifs. Les opérateurs approximatifs sont ensuite utilisés pour la reproduction des effets de la VOS dans les opérateurs arithmétiques exacts. Grâce à notre outil de travail open-source ApxPerf et ses bibliothèques synthétisables C++ apx_fixed pour les opérateurs approximatifs et ct_float pour l'arithmétique flottante basse consommation, deux études consécutives sont proposées, basées sur des applications de traitement du signal complexes. Tout d'abord, les opérateurs approximatifs sont comparés à l'arithmétique virgule-fixe, et la supériorité de la virgule-fixe est soulignée. Enfin, la virgule fixe est comparée aux petits flottants dans des conditions équivalentes. En fonction des conditions applicatives, la virgule-flottante montre une compétitivité inattendue face à la virgule-fixe. Les résultats et discussions de cette thèse donnent un regard nouveau sur l'arithmétique approximative et suggère de nouvelles directions pour le futur des architectures efficaces en énergie. / The physical limits being reached in silicon-based computing, new ways have to be found to overcome the predicted end of Moore's law. Many applications can tolerate approximations in their computations at several levels without degrading the quality of their output, or degrading it in an acceptable way. This thesis focuses on approximate arithmetic architectures to seize this opportunity. Firstly, a critical study of state-of-the-art approximate adders and multipliers is presented. Then, a model for fixed-point error propagation leveraging power spectral density is proposed, followed by a model for bitwise-error rate propagation of approximate operators. Approximate operators are then used for the reproduction of voltage over-scaling effects in exact arithmetic operators. Leveraging our open-source framework ApxPerf and its synthesizable template-based C++ libraries apx_fixed for approximate operators, and ct_float for low-power floating-point arithmetic, two consecutive studies are proposed leveraging complex signal processing applications. Firstly, approximate operators are compared to fixed-point arithmetic, and the superiority of fixed-point is highlighted. Secondly, fixed-point is compared to small-width floating-point in equivalent conditions. Depending on the applicative conditions, floating-point shows an unexpected competitiveness compared to fixed-point. The results and discussions of this thesis give a fresh look on approximate arithmetic and suggest new directions for the future of energy-efficient architectures.

Dans le cadre de cette thèse, nous nous intéressons à la structure multiplicative des nombres entiers par le biais des deux fonctions arithmétiques sqk(n) :=Ypjjn<kp et powk(n) :=Ypjjnkp; nommées respectivement la partie k-libre de n et la partie k-puissante de n. DXans le premier chapitre, nous évaluons le comportement asymptotique de la sommation nx sqa k(n)powbk (n) pour k 2 fixé et avec différentes valeurs réelles de a et b. Nous obtenons par exemple que X nx sqk(n) = C(k)x2 + O x1+ 1 k tandis que X nx powk(n) = D(k)x1+ 1 k + O x1+ 1 k+1 , d'où nous pouvons conclure que la partie k-libre est fréquemment plus grande que la partie k-puissante. De plus, l'ordre de grandeur de la somme dépend généralement du maximum entre a et b. Dans le deuxième chapitre, nous obtenons divers résultats en lien avec les deux fonctions sqk(n) et powk(n) lorsque k = 2. Nous touchons en particulier à la distribution de leurs valeurs, à la densité des nombres satisfaisant pow2(n) > sq2(n), ainsi qu'à la valeur moyenne asymptotique de ces deux fonctions sur les nombres n'ayant aucun facteur premier plus grand que y, et ce pour différents ordres de grandeur de y. D'ailleurs, nous montrons que l'égalité log 0 BBBBB@ X nx P(n)y sq2(n) x 1 CCCCCA = (1 + o(1)) log 0 BBBBB@ X nx P(n)y pow2(n) x 1 CCCCCA est valide uniquement lorsque y = 2 log x auquel cas nous obtenons que ces expressions sont égales à (1 + o(1)) 2 log 2 log x log log x lorsque x ! 1: Finalement, dans le troisième et dernier chapitre, nous généralisons les résultats du chapitre précédent aux valeurs de k supérieures à 2. / In this thesis, we study the multiplicative structure of integers by using the two arithmetical functions sqk(n) := Y pjjn <k p and powk(n) := Y pjjn k p; named respectively the k-free part of n and the k-full part of n. In the first chapter, we evaluate the asymptotic behavior of the summation X nx sqa k(n)powbk (n) for k 2 fixed and for different real values of a and b. For example, we obtain that X nx sqk(n) = C(k)x2 + O x1+ 1 k while X nx powk(n) = D(k)x1+ 1 k + O x1+ 1 k+1 , which means the k-free part is frequently greater than the k-full part. Furthermore, the order of magnitude of the sum generally depends on the maximum between a and b. In the second chapter, we get various results related to the functions sqk(n) and powk(n) when k = 2. We study in particular the distribution of their values, the density of numbers satisfying pow2(n) > sq2(n), and also the asymptotic mean value of those two functions on the numbers without any prime factor greater than y, and for different values of y. In fact, we show that the equality log 0 BBBBB@ X nx P(n)y sq2(n) x 1 CCCCCA = (1 + o(1)) log 0 BBBBB@ X nx P(n)y pow2(n) x 1 CCCCCA holds only for y = 2 log x. And for this value of y, those expressions are in fact equal to (1 + o(1)) 2 log 2 log x log log x as x ! 1: Finally, in the third and last chapter, we generalize the results of the previous chapter to k greater than 2.

Dans cette thèse nous construisons un groupe faible de cobordisme arithmétique dans le contexte de la géométrie d'Arakelov. Nous introduisons des versions faibles des groupes de K-théorie arithmétique et de Chow arithmétique, et en dégageons une notion de théorie homologique orientée de type arithmétique. Nous construisons alors un groupe universel parmi ces théories homologiques et prouvons ses principales propriétés structurelles. / In this thesis we construct a weak group of arithmetic cobordism in the context of Arakelov geometry. We introduce weak versions of arithmetic K-theory and arithmetic Chow groups, that give rise to the notion of oriented homological theory of arithmetic type. We then build a universal such homological theory, and prove its main structural features.

Les protocoles de cryptographie asymétrique nécessitent des calculs arithmétiques dans différentes structures mathématiques de grandes tailles. Pour garantir une sécurité suffisante, ces tailles varient de plusieurs centaines à plusieurs milliers de bits et rendent les opérations arithmétiques coûteuses en temps de calcul. D'autre part, les architectures grand public actuelles embarquent plusieurs unités de calcul, réparties sur les processeurs et éventuellement sur les cartes graphiques. Ces ressources sont aujourd'hui facilement exploitables grâce à des interfaces de programmation parallèle comme OpenMP ou CUDA. Dans cette thèse, nous étudions la parallélisation d'opérateurs à différents niveaux arithmétique. Nous nous intéressons plus particulièrement à la multiplication entre entiers multiprécision ; à la multiplication modulaire ; et enfin à la multiplication scalaire sur les courbes elliptiques.Dans chacun des cas, nous étudions différents ordonnancements des calculs permettant d'obtenir les meilleures performances. Nous proposons également une bibliothèque permettant la parallélisation sur processeur graphique d'instances d'opérations modulaires et d'opérations sur les courbes elliptiques. Enfin, nous proposons une méthode d'optimisation automatique de la multiplication scalaire sur les courbes elliptiques pour de petits scalaires permettant l'élimination des sous-expressions communes apparaissant dans la formule et l'application systématique de transformations arithmétiques. / Asymmetric cryptography requires some computations in large size finite mathematical structures. To insure the required security, these sizes range from several hundred to several thousand of bits. Mathematical operations are thus expansive in terms of computation time. Otherwise, current architectures have several computing units, which are distribued over the processors and GPU and easily implementable using dedicated languages as OpenMP or CUDA. In this dissertation, we investigate the parallelization of some operators for different arithmetical levels.In particular, our research focuse on parallel multiprecision and modular multiplications, and the parallelization of scalar multiplication over elliptic curves. We also propose a library to parallelize modular operations and elliptic curves operations. Finally, we present a method which allow to optimize scalar elliptic curve multiplication for small scalars.

.

La recherche sur les Environnements Informatiques pour l’Apprentissage Humain (EIAH) et la psychologie convergent dans leur intérêt d’une meilleure compréhension du sujet et plus particulièrement dans sa modélisation, ouvrant des perspectives en éducation. La thèse, fondamentalement interdisciplinaire, vise à resserrer le lien entre la psychologie expérimentale et les EIAH dans le domaine des Problèmes Arithmétiques à Enoncés Verbaux (PAEV), tout en abordant la question plus générale d’intégration de modèles cognitifs dans les EIAH. Dans une première partie, un module de diagnostic comportemental est mis en place accompagnée d’une méthodologie de tests et d’autoévaluation pour pouvoir être employé en psychologie expérimentale. Mieux comprendre, et surtout modéliser les comportements est une étape nécessaire préalable à la mise en place du module de diagnostic épistémique. C’est l’objet de la deuxième partie, où un travail de modélisation cognitive a été effectué, qui montre par la construction de modèles exécutables que les productions des sujets peuvent être mises en lien avec des stratégies, conscientes ou non, de résolution de problèmes, telles que la réinterprétation de phrases et l’usage de mots-clefs. Dans la troisième partie, afin de répondre à la problématique du diagnostic individuel par la modélisation cognitive, une mesure adaptée à ces modèles a été mise place. Un logiciel a aussi été développé pour construire des versions simples de modèles cognitifs et les tester sur les données issues d’un EIAH. Ce logiciel et cette mesure ont ensuite été mis en application dans le cadre d’une nouvelle expérimentation sur les PAEV. / Research in psychology and in Intelligent Learning Environment (ILE) share the goal of a better understanding of the subject, more precisely in its modeling with strong educative perspectives. This Ph.D. Thesis, intrinsically interdisciplinary, aims to strengthen the link between experimental psychology and ILEs, especially in the domain of arithmetical word problem solving (WP) while addressing the more general issue of the integration of cognitive models in the ILEs. In the first part, a behavioral diagnostic module is presented, with a test-based methodology to assess its relevance in the context of experimental psychology studies. A better understanding of word problem solving behavior is a prerequisite of the development of any cognitive diagnostic module. This is the core of the second part, which presents the cognitive models put in place and compare their productions with human data. It has been shown that a large part of WP solving behavior can be explained via the light of keyword-based strategy and the alteration of the meaning of textual propositions. In the last part, in order to address the issue of individual cognitive diagnosis, a metric quantifying the fit of the diagnosis has been developed. A software has also been developed, allowing to build and test simple cognitive models over data coming from ILEs. This metric and this software have been used concretely within the context of an experimentation involving word problem solving.

Les couplages sont des primitives cryptographiques qui interviennent désormais dans de nombreux protocoles. Dès lors, il est nécessaire de s'intéresser à leur calcul et à leur implémentation efficace. Pour ce faire, nous nous reposons sur une étude algorithmique et arithmétique de ces fonctions mathématiques. Les couplages sont des applications bilinéaires définies sur des courbes algébriques, plus particulièrement, dans le cas qui nous intéresse, des courbes elliptiques et hyperelliptiques. Nous avons choisi de nous concentrer sur une sous-famille de celles-ci : les courbes supersingulières dont les propriétés permettent d'obtenir à la fois des couplages symétriques et des algorithmes efficaces pour leur calcul. Nous décrivons alors une approche unifiée permettant d'établir une large variété d'algorithmes calculant des couplages. Nous l'appliquons notamment à la construction d'un nouvel algorithme pour le calcul de couplages sur des courbes supersingulières de genre 2 et de caractéristique 2. Les calculs nécessaires aux couplages que nous décrivons s'appuient sur l'implémentation d'une arithmétique rapide pour les corps finis de petite caractéristique : la multiplication est l'opération critique qu'il convient d'optimiser. Nous présentons donc un algorithme de recherche exhaustive de formules de multiplication. Enfin, nous appliquons toutes les méthodes précédentes à la conception et l'implémentation de différents accélérateurs matériels pour le calcul de couplages sur différentes courbes dont les architectures ont été optimisées soit pour leur rapidité, soit pour leur compacité / Pairings are cryptographic primitives which are now used in numerous protocols. Computing and implementing them efficiently is then an interestingchallenge relying on an algorithmic and arithmetic study of those mathematical functions. More precisely, pairings are bilinear maps defined over elliptic and hyperelliptic curves. Among those, we restrict our study to supersingular curves, as they allow both symmetric pairings and efficient algorithm for pairing computation. We propose an unified framework for the construction of algorithms computing pairings and we apply it to the design of a novel algorithm for a pairing over a genus-2 characteristic-2 hyperelliptic curve. The computations involved in our algorithms require the implementation of rapid arithmetic for finite fields of small characteristic. Since multiplication is the critical operation, we present an algorithm for the exhaustive search of multiplication formulae. Finally, we apply all the previous methods to the design and implementation of different hardware accelerators for the computation of cryptographic pairings over various curves

Cette thèse propose des améliorations aux problèmes de la multiplication et de la factorisation d’entier.L’algorithme de Schönhage-Strassen pour la multiplication d’entier, publié en 1971, fut le premier à atteindre une complexité de O(n log(n) log(log(n))) pour multiplier deux entiers de n bits, et reste parmi les plus rapides en pratique. Il réduit la multiplication d’entier à celle de polynôme sur un anneau fini, en utilisant la transformée de Fourier rapide pour calculer le produit de convolution. Dans un travail commun avec Gaudry et Zimmermann, nous décrivons une implantation efficace de cet algorithme, basée sur la bibliothèque GNU MP; par rapport aux travaux antérieurs, nous améliorons l’utilisation de la mémoire cache, la sélection des parameters et la longueur de convolution, ce qui donne un gain d’un facteur 2 environ.Les algorithmes P–1 et P+1 trouvent un facteur p d’un entier composé rapidement si p-1, respectivement p+1, ne contient pas de grand facteur premier. Ces algorithmes comportent deux phases : la première phase calcule une grande puissance g1 d’un élément g0 d’un groupe fini défini sur Fp, respectivement Fp^2 , la seconde phase cherche une collision entre puissances de g1, qui est trouvée de manière efficace par évaluation-interpolation de polynômes. Dans un travail avec Peter Lawrence Montgomery, nous proposons une amélioration de la seconde phase de ces algorithmes, avec une construction plus rapide des polynômes requis, et une consommation mémoire optimale, ce qui permet d’augmenter la limite pratique pour le plus grand facteur premier de p-1, resp. p + 1, d’un facteur 100 environ par rapport aux implantations antérieures.Le crible algébrique (NFS) est le meilleur algorithme connu pour factoriser des entiers dont les facteurs n’ont aucune propriété permettant de les trouver rapidement. En particulier, le module du système RSA de chiffrement est choisi de telle sorte, et sa factorisation casse le système. De nombreux efforts ont ainsi été consentis pour améliorer NFS, de façon à établir précisément la sécurité de RSA. Nous donnons un bref aperçu de NFS et de son historique. Lors de la phase de crible de NFS, de nombreux petits entiers doivent être factorisés. Nous présentons en detail une implantation de P–1, P+1, et de la méthode ECM basée sur les courbes elliptiques, qui est optimisée pour de tels petits entiers. Finalement, nous montrons comment les paramètres de ces algorithmes peuvent être choisis finement, en tenant compte de la distribution des facteurs premiers dans les entiers produits par NFS, et de la probabilité de trouver des facteurs premiers d’une taille donnée / This thesis explores improvements to well-known algorithms for integer multiplication and factorization.The Schönhage-Strassen algorithm for integer multiplication, published in 1971, was the firstto achieve complexity O(n log(n) log(log(n))) for multiplication of n-bit numbers and is stillamong the fastest in practice. It reduces integer multiplication to multiplication of polynomials over finite rings which allow the use of the Fast Fourier Transform for computing the convolution product. In joint work with Gaudry and Zimmermann, we describe an efficient implementation of the algorithm based on the GNU Multiple Precision arithmetic library, improving cache utilization, parameter selection and convolution length for the polynomial multiplication over previous implementations, resulting in nearly 2-fold speedup.The P–1 and P+1 factoring algorithms find a prime factor p of a composite number quickly if p-1, respectively p+1, contains no large prime factors. They work in two stages: the first step computes a high power g1 of an element g0 of a finite group defined over Fp, respectively Fp^2 , the second stage looks for a collision of powers of g1 which can be performed efficiently via polynomial multi-point evaluation. In joint work with Peter Lawrence Montgomery, we present an improved stage 2 for these algorithms with faster construction of the required polynomial and very memory-efficient evaluation, increasing the practical search limit for the largest permissible prime in p-1, resp. p+1, approximately 100-fold over previous implementations.The Number Field Sieve (NFS) is the fastest known factoring algorithm for “hard” integers where the factors have no properties that would make them easy to find. In particular, the modulus of the RSA encryption system is chosen to be a hard composite integer, and its factorization breaks the encryption. Great efforts are therefore made to improve NFS in order to assess the security of RSA accurately. We give a brief overview of the NFS and its history. In the sieving phase of NFS, a great many smaller integers must be factored. We present in detail an implementation of the P–1, P+1, and Elliptic Curve methods of factorization optimized for high-throughput factorization of small integers. Finally, we show how parameters for these algorithms can be chosen accurately, taking into account the distribution of prime factors in integers produced by NFS to obtain an accurate estimate of finding a prime factor with given parameters

On considère le problème du calcul dans des extensions de Q par des nombres algébriques. Il s'agit (par diverses approches) de savoir comment l'arithmétique exacte peut être envisagée dans ces extensions. On présente l'approche classique basée sur l'élément primitif, on montre qu'elle est très coûteuse et que les résultats obtenus sont inutilisables. On voit une autre approche basée sur des factorisations dans les extensions, on montre qu'elle est meilleure que la première, cependant l'algorithme de factorisation est assez coûteuse. On aborde le cas particulier où les nombres algébriques sont loin d'être triviales mais qu'en se plaçant sur un corps de base Ko engendré sur Q par ζo = exp iπ/4 on peut surmonter toutes les difficultés. On présente l'algorithme et des exemples dans le cas de un ou de deux radicaux. La généralisation à plusieurs radicaux ne semble pas poser des difficultés supplémentaires