La solution la plus commune pour résoudre les problèmes de précision liés aux arithmétiques des ordinateurs est l'utilisation d'arithmétiques exactes. Nous proposons dans la première partie de cette thèse une optimisation très puissante des arithmétiques rationnelles : l'arithmétique rationnelle paresseuse. L'originalité de cette arithmétique est de retarder les calculs exacts jusqu'à ce qu'ils deviennent soit inutiles, soit inévitables. Ainsi les calculs exacts qui ne sont pas nécessaires ne sont jamais faits. L'arithmétique paresseuse se présente sous la forme d'une bibliothèque autonome prenant à sa charge les problèmes de précision et qui est indépendante des programmes qui l'utilisent. La deuxième partie de cette thèse présente un outil de modélisation dont le principal intérêt est d'utiliser l'image des objets comme support à leur modélisation sous forme d'arbre de construction. Cet outil est interactif, l'utilisateur pourra de cette manière ne modéliser que ce dont il a besoin et avec le niveau de détails le plus adapté à ses applications. Les extensions que nous proposons dans le domaine de l'incrustation d'images de synthèse dans des images naturelles permettent de traiter correctement l'ombrage de la scène finale en tenant compte de la nature des éclairages, des ombres portées et des reflets.

La résolution de l'éclairement global d'une scène par le trace de rayons implique l'élaboration de méthodes de Monté Carlo adaptées à la complexité de l'équation de rendu. Nous proposons une méthode de résolution globale et adaptative un trace de chemin spectral partant de l'il basée sur un échantillonnage d'importance permettant d'augmenter la vitesse de convergence de la résolution. Notre méthode consiste à mimer les variations de la luminance réfléchie en tenant compte de la fonction de réflectance bidirectionnelle et des caractéristiques des sources. Ce premier échantillonnage a priori est progressivement modifie par un schéma a posteriori s'adaptant à la luminance réellement réfléchie à mesure qu'elle est connue. Le deuxième aspect de nos travaux porte sur la génération des points de l'écran afin de ne calculer que ceux qui sont nécessaires à une qualité d'image donnée. Nous proposons une technique progressive basée sur une notion d'homogénéité visuelle locale de l'image. Cette homogénéité est testée à l'aide d'un procède statistique puissant utilisant l'analyse séquentielle. Notre méthode permet souvent des gains en temps de calcul très substantiels pour une bonne qualité d'image. L'ensemble de nos travaux a été inspire par la notion de réalisme. Nous montrons que le photoréalisme est insuffisant au contrôle d'une image et proposons des pistes de réflexion pour ce concept trop peu aborde en synthèse d'images

Dans les années quatre-vingts dix du siècle dernier, R. W. Thomason a démontréun théorème de concentration pour la K-théorie équivariante algébrique sur lesschémas munis d'une action d'un groupe algébrique G diagonalisable. Comme d'habitude,un tel théorème entraîne une formule des points fixes de type Lefschetz qui permetde calculer la caractéristique d'Euler-Poincaré équivariante d'un G-faisceau cohérent surun G-schéma propre en termes d'une caractéristique sur le sous-schéma des points fixes.Le but de cette thèse est de généraliser les résultats de R.W. Thomason dans le contextede la géométrie d'Arakelov. Dans ce travail, nous considérons les schémas arithmétiquesau sens de Gillet-Soulé et nous tout d'abord démontrons un analogue arithmétiquedu théorème de concentration pour les schémas arithmétiques munis d'une action duschéma en groupe diagonalisable associé à Z/nZ. La démonstration résulte du théorèmede concentration algébrique joint à des arguments analytiques. Dans le dernier chapitre,nous formulons et démontrons deux types de formules de Lefschetz arithmétiques. Cesdeux formules donnent une réponse positive à deux conjectures énoncées par K. Köhler,V. Maillot et D. Rössler.

Ma thèse porte sur l'étude des couplages, et plus particulièrement leur utilisation en cryptographie. Mes premiers travaux ont portés sur l'arithmétique des couplages à travers une comparaison des complexités en nombre d'opérations des couplages de Weil et Tate. Puis je me suis intéressée à l'étude de l'arithmétique utile pour les couplages. Un de mes travaux propose d'utiliser une représentation alternative des corps finis pour améliorer l'efficacité des calculs impliqués dans les couplages. Le second étudie en détail l'arithmétique des couplages pour les courbes dont le degré d'enfoncement est 15. Ces premiers travaux m'ont permis de me familiariser avec les couplages et je me suis alors orientée vers la résistance aux attaques par canaux cachés des algorithmes de couplage. J'ai étudié les faiblesses de l'algorithme de Miller lorsqu'il subit des attaques par analyse de consommation de courant et par injection de fautes.

Les protocoles de cryptographie asymétrique nécessitent des calculs arithmétiques dans différentes structures mathématiques. Un grand nombre de ces protocoles requièrent en particulier des calculs dans des structures finies, rendant indispensable une arithmétique modulaire efficace. Ces opérations modulaires sont composées d'opérations multiprécision entre opérandes de tailles suffisamment grandes pour garantir le niveau de sécurité requis (de plusieurs centaines à plusieurs milliers de bits). Enfin, certains protocoles nécessitent des opérations arithmétiques dans le groupe des points d'une courbe elliptique, opérations elles-mêmes composées d'opérations dans le corps de définition de la courbe. Les tailles de clés utilisées par les protocoles rendent ainsi les opérations arithmétiques coûteuses en temps de calcul. Par ailleurs, 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. Cette thèse s'articule autour de la définition d'opérateurs arithmétiques parallèles permettant de tirer parti de l'ensemble des ressources de calcul, en particulier sur des architectures multicœur à mémoire partagée. La parallélisation au niveau arithmétique le plus bas permet des gains modérés en termes temps de calcul, car les tailles des opérandes ne sont pas suffisamment importantes pour que l'intensité arithmétique des calculs masque les latences dues au parallélisme. Nous proposons donc des algorithmes permettant une parallélisation aux niveaux arithmétiques supérieurs : algorithmes parallèles pour la multiplication modulaire et pour la multiplication scalaire sur les courbes elliptiques. Pour la multiplication modulaire, nous étudions en particulier plusieurs ordonnancements des calculs au niveau de l'arithmétique modulaire et proposons également une parallélisation à deux niveaux : modulaire et multiprécision. Ce parallélisme à plus gros grain permet en pratique des gains plus conséquents en temps de calcul. Nous proposons également une parallélisation sur processeur graphique d'opérations modulaires et d'opérations dans le groupe des points d'une courbe elliptique. Enfin, nous présentons une méthode pour optimiser la multiplication scalaire sur les courbes elliptiques pour de petits scalaires.

L'étude de la distribution des points rationnels sur les variétés algébriques est un sujet classique de la géométrie diophantienne. Le programme proposé par V. Batyrev et Y. Manin dans des années 90 donne une prédiction sur l'ordre de croissance tandis que sa version ultérieure dûe à E. Peyre conjecture l'existence d'une distribution globale. Dans cette thèse nous nous proposons une étude de la distribution locale des points rationnels de hauteur bornée sur les variétés algébriques. Ceci envisage une description plus fine que celle globale en dénombrant les points le plus proche d'un point fixé. Nous nous plaçons sur le cadre récent du travail de D. McKinnon et M. Roth qui met en évidence que la géométrie de la variété gouverne l'approximation diophantienne sur elle et nous reprenons les résultats de S. Pagelot. L'ordre de croissance espéré et l'existence d'une mesure asymptotique sur certaines surfaces toriques sont démontrés, alors que démontrons-nous un résultat totalement différent pour une autre surface sur laquelle il n'y pas de mesure asymptotique et les meilleurs approximants génériques s'obtiennent sur des courbes rationnelles nodales. Ces deux phénomènes sont de nature radicalement différente au point de vu de l'approximation diophantienne. / The study of the distribution of rational points on algebraic varieties is a classic subject of Diophantine geometry. The program proposed by V. Batyrev and Y. Manin in the 1990s gives a prediction on the order of growth whereas its later version due to E. Peyre conjectures the existence of a global distribution. In this thesis we propose a study of the local distribution of rational points of bounded height on algebraic manifolds. This aims at giving a description finer than the global one by counting the points closest to a fixed point. We set ourselves on the recent framework of the work of D. McKinnon and M. Roth who prefers that the geometry of the variety governs the Diophantine approximation on it and we take up the results of S. Pagelot. The expected order of growth and the existence of an asymptotic measure on some toric surfaces are demonstrated, while we demonstrate a totally different result for another surface on which there is no asymptotic measure and the best generic approximates are obtained on nodal rational curves. These two phenomena are of a radically different nature from the point of view of the Diophantine approximation.

Dans cette thèse on étudie certains phénomènes d'interactions entre caractéristique positive et caractéristique nulle. Dans un premier temps on s'occupe du problème de relèvement locale d'actions de groupes. On y montre des conditions nécessaires pour l'existence de relèvement de certains actions du groupe Z/pZ x Z/pZ. Pour une action d'un groupe fini quelconque, on y étudie les arbres de Hurwitz, en montrant que chaque arbre de Hurwitz admet un plongement dans le disque unitaire fermé de Berkovich et que ses données de Hurwitz peuvent être décrites de façon analytique. Dans une deuxième partie nous construisons un analogue de la représentation de Weil à coefficients dans un anneau intègre, et nous montrons que cela satisfait les mêmes propriétés que dans le cas de coefficients complexes / In this thesis, we study the interplay between positive and zero characteristic. In a first instance, we deal with the local lifting problem of lifting actions of curves. We show necessary conditions for the existence of liftings of some actions of Z/pZ x Z/pZ. Then, for an action of a general finite group, we study the associated Hurwitz tree, showing that every Hurwitz tree has a canonical metric embedding in the Berkovich closed unit disc, and that the Hurwitz data can be described analytically.In the last chapter, we define an analog of the Weil representation with coefficients in an integral domain, showing that such representation satisfies the same properties than in the case with complex coefficients

Doctorat en sciences psychologiques / info:eu-repo/semantics/nonPublished

L’algorithme de basculement de bits à descente de gradient probabiliste (Probabilistic Gradient Descent Bit Flipping :PGDBF) est récemment introduit comme un nouveau type de décodeur de décision forte pour le code de contrôle de parité à faible densité (Low Density Parity Check : LDPC) appliqué au canal symétrique binaire. En suivant précisément les étapes de décodage du décodeur déterministe Gradient Descent Bit-Flipping (GDBF), le PGDBF intègre en plus la perturbation aléatoire dans l'opération de basculement des Nœuds de Variables (VNs) et produit ainsi une performance de décodage exceptionnelle qui est meilleure que tous les décodeurs à basculement des bits (BF : Bit Flipping) connus dans la littérature, et qui approche les performances du décodeur de décision souple. Nous proposons dans cette thèse plusieurs implémentations matérielles du PGDBF, ainsi qu'une analyse théorique de sa capacité de correction d'erreurs. Avec une analyse de chaîne de Markov du décodeur, nous montrons qu’en raison de l'incorporation de la perturbation aléatoire dans le traitement des VNs, le PGDBF s'échappe des états de piégeage qui empêchent sa convergence. De plus, avec la nouvelle méthode d'analyse proposée, la performance du PGDBF peut être prédite et formulée par une équation de taux de trames erronées en fonction du nombre des itérations, pour un motif d'erreur donné. L'analyse fournit également des explications claires sur plusieurs phénomènes de PGDBF tels que le gain de re-décodage (ou de redémarrage) sur un motif d'erreur reçu. La problématique de l’implémentation matérielle du PGDBF est également abordée dans cette thèse. L’implémentation classique du décodeur PGDBF, dans laquelle un générateur de signal probabiliste est ajouté au-dessus du GDBF, est introduite avec une augmentation inévitable de la complexité du décodeur. Plusieurs procédés de génération de signaux probabilistes sont introduits pour minimiser le surcoût matériel du PGDBF. Ces méthodes sont motivées par l'analyse statistique qui révèle les caractéristiques critiques de la séquence aléatoire binaire requise pour obtenir une bonne performance de décodage et suggérer les directions possibles de simplification. Les résultats de synthèse montrent que le PGDBF déployé avec notre méthode de génération des signaux aléatoires n’a besoin qu’une très faible complexité supplémentaire par rapport au GDBF tout en gardant les mêmes performances qu’un décodeur PGDBF théorique. Une implémentation matérielle intéressante et particulière du PGDBF sur les codes LDPC quasicyclique (QC-LPDC) est proposée dans la dernière partie de la thèse. En exploitant la structure du QCLPDC, une nouvelle architecture pour implémenter le PGDBF est proposée sous le nom d'architecture à décalage des Nœuds de Variables (VNSA : Variable-Node Shift Architecture). En implémentant le PGDBF par VNSA, nous montrons que la complexité matérielle du décodeur est même inférieure à celle du GDBF déterministe tout en préservant la performance de décodage aussi élevée que celle fournie par un PGDBF théorique. Enfin, nous montrons la capacité de cette architecture VNSA à se généraliser sur d'autres types d'algorithmes de décodage LDPC. / Probabilistic Gradient Descent Bit Flipping (PGDBF) algorithm have been recently introduced as a new type of hard decision decoder for Low-Density Parity-Check Code (LDPC) applied on the Binary Symmetric Channel. By following precisely the decoding steps of the deterministic Gradient Descent Bit-Flipping (GDBF) decoder, PGDBF additionally incorporates a random perturbation in the ipping operation of Variable Nodes (VNs) and produces an outstanding decoding performance which is better to all known Bit Flipping decoders, approaching the performance of soft decision decoders. We propose in this thesis several hardware implementations of PGDBF, together with a theoretical analysis of its error correction capability. With a Markov Chain analysis of the decoder, we show that, due to the incorporation of random perturbation in VN processing, the PGDBF escapes from the trapping states which prevent the convergence of decoder. Also, with the new proposed analysis method, the PGDBF performance can be predicted and formulated by a Frame Error Rate equation as a function of the iteration, for a given error pattern. The analysis also gives a clear explanation on several phenomenons of PGDBF such as the gain of re-decoding (or restarting) on a received error pattern. The implementation issue of PGDBF is addressed in this thesis. The conventional implementation of PGDBF, in which a probabilistic signal generator is added on top of the GDBF, is shown with an inevitable increase in hardware complexity. Several methods for generating the probabilistic signals are introduced which minimize the overhead complexity of PGDBF. These methods are motivated by the statistical analysis which reveals the critical features of the binary random sequence required to get good decoding performance and suggesting the simpli cation directions. The synthesis results show that the implemented PGDBF with the proposed probabilistic signal generator method requires a negligible extra complexity with the equivalent decoding performance to the theoretical PGDBF. An interesting and particular implementation of PGDBF for the Quasi-Cyclic LPDC (QC-LPDC) is shown in the last part of the thesis. Exploiting the structure of QC-LPDC, a novel architecture to implement PGDBF is proposed called Variable-Node Shift Architecture (VNSA). By implementing PGDBF by VNSA, it is shown that the decoder complexity is even smaller than the deterministic GDBF while preserving the decoding performance as good as the theoretical PGDBF. Furthermore, VNSA is also shown to be able to apply on other types of LDPC decoding algorithms.

Les nombres p-adiques sont un analogue des nombres réels plus proche de l’arithmétique. L’avènement ces dernières décennies de la géométrie arithmétique a engendré la création de nombreux algorithmes utilisant ces nombres. Ces derniers ne peuvent être de manière générale manipulés qu’à précision finie. Nous proposons une méthode, dite de précision différentielle, pour étudier ces problèmes de précision. Elle permet de se ramener à un problème au premier ordre. Nous nous intéressons aussi à la question de savoir quelles bases de Gröbner peuvent être calculées sur les p-adiques. / P-Adic numbers are a field in arithmetic analoguous to the real numbers. The advent during the last few decades of arithmetic geometry has yielded many algorithms using those numbers. Such numbers can only by handled with finite precision. We design a method, that we call differential precision, to study the behaviour of the precision in a p-adic context. It reduces the study to a first-order problem. We also study the question of which Gröbner bases can be computed over a p-adic number field.