On Space-Time Trade-Off for Montgomery Multipliers over Finite Fields

La multiplication dans le corps de Galois à 2^m éléments (i.e. GF(2^m)) est une opérations très importante pour les applications de la théorie des correcteurs et de la cryptographie. Dans ce mémoire, nous nous intéressons aux réalisations parallèles de multiplicateurs dans GF(2^m) lorsque ce dernier est généré par des trinômes irréductibles. Notre point de départ est le multiplicateur de Montgomery qui calcule A(x)B(x)x^(-u) efficacement, étant donné A(x), B(x) in GF(2^m) pour u choisi judicieusement. Nous étudions ensuite l'algorithme diviser pour régner PCHS qui permet de partitionner les multiplicandes d'un produit dans GF(2^m) lorsque m est impair. Nous l'appliquons pour la partitionnement de A(x) et de B(x) dans la multiplication de Montgomery A(x)B(x)x^(-u) pour GF(2^m) même si m est pair. Basé sur cette nouvelle approche, nous construisons un multiplicateur dans GF(2^m) généré par des trinôme irréductibles. Une nouvelle astuce de réutilisation des résultats intermédiaires nous permet d'éliminer plusieurs portes XOR redondantes. Les complexités de temps (i.e. le délais) et d'espace (i.e. le nombre de portes logiques) du nouveau multiplicateur sont ensuite analysées: 1. Le nouveau multiplicateur demande environ 25% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito lorsque GF(2^m) est généré par des trinômes irréductible et m est suffisamment grand. Le nombre de portes du nouveau multiplicateur est presque identique à celui du multiplicateur de Karatsuba proposé par Elia. 2. Le délai de calcul du nouveau multiplicateur excède celui des meilleurs multiplicateurs d'au plus deux évaluations de portes XOR. 3. Nous determinons le délai et le nombre de portes logiques du nouveau multiplicateur sur les deux corps de Galois recommandés par le National Institute of Standards and Technology (NIST). Nous montrons que notre multiplicateurs contient 15% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito au coût d'un délai d'au plus une porte XOR supplémentaire. De plus, notre multiplicateur a un délai d'une porte XOR moindre que celui du multiplicateur d'Elia au coût d'une augmentation de moins de 1% du nombre total de portes logiques.

Quotients d'une variété algébrique par un groupe algébrique linéairement réductif et ses sous-groupes maximaux unipotents

La construction d'un quotient, en topologie, est relativement simple; si $G$ est un groupe topologique agissant sur un espace topologique $X$, on peut considérer l'application naturelle de $X$ dans $X/G$, l'espace d'orbites muni de la topologie quotient. En géométrie algébrique, malheureusement, il n'est généralement pas possible de munir l'espace d'orbites d'une structure de variété. Dans le cas de l'action d'un groupe linéairement réductif $G$ sur une variété projective $X$, la théorie géométrique des invariants nous permet toutefois de construire un morphisme de variété d'un ouvert $U$ de $X$ vers une variété projective $X//U$, se rapprochant autant que possible d'une application quotient, au sens topologique du terme. Considérons par exemple $X\subseteq P^{n}$, une $k$-variété projective sur laquelle agit un groupe linéairement réductif $G$ et supposons que cette action soit induite par une action linéaire de $G$ sur $A^{n+1}$. Soit $\widehat{X}\subseteq A^{n+1}$, le cône affine au dessus de $\X$. Par un théorème de la théorie classique des invariants, il existe alors des invariants homogènes $f_{1},...,f_{r}\in C[\widehat{X}]^{G}$ tels que $$C[\widehat{X}]^{G}= C[f_{1},...,f_{r}].$$ On appellera le nilcone, que l'on notera $N$, la sous-variété de $\X$ définie par le locus des invariants $f_{1},...,f_{r}$. Soit $Proj(C[\widehat{X}]^{G})$, le spectre projectif de l'anneau des invariants. L'application rationnelle $$\pi:X\dashrightarrow Proj(C[f_{1},...,f_{r}])$$ induite par l'inclusion de $C[\widehat{X}]^{G}$ dans $C[\widehat{X}]$ est alors surjective, constante sur les orbites et sépare les orbites autant qu'il est possible de le faire; plus précisément, chaque fibre contient exactement une orbite fermée. Pour obtenir une application régulière satisfaisant les mêmes propriétés, il est nécessaire de jeter les points du nilcone. On obtient alors l'application quotient $$\pi:X\backslash N\rightarrow Proj(C[f_{1},...,f_{r}]).$$ Le critère de Hilbert-Mumford, dû à Hilbert et repris par Mumford près d'un demi-siècle plus tard, permet de décrire $N$ sans connaître les $f_{1},...,f_{r}$. Ce critère est d'autant plus utile que les générateurs de l'anneau des invariants ne sont connus que dans certains cas particuliers. Malgré les applications concrètes de ce théorème en géométrie algébrique classique, les démonstrations que l'on en trouve dans la littérature sont généralement données dans le cadre peu accessible des schémas. L'objectif de ce mémoire sera, entre autres, de donner une démonstration de ce critère en utilisant autant que possible les outils de la géométrie algébrique classique et de l'algèbre commutative. La version que nous démontrerons est un peu plus générale que la version originale de Hilbert \cite{hilbert} et se retrouve, par exemple, dans \cite{kempf}. Notre preuve est valide sur $C$ mais pourrait être généralisée à un corps $k$ de caractéristique nulle, pas nécessairement algébriquement clos. Dans la seconde partie de ce mémoire, nous étudierons la relation entre la construction précédente et celle obtenue en incluant les covariants en plus des invariants. Nous démontrerons dans ce cas un critère analogue au critère de Hilbert-Mumford (Théorème 6.3.2). C'est un théorème de Brion pour lequel nous donnerons une version un peu plus générale. Cette version, de même qu'une preuve simplifiée d'un théorème de Grosshans (Théorème 6.1.7), sont les éléments de ce mémoire que l'on ne retrouve pas dans la littérature.

Online Dispute Resolution: The Next Phase

Ce texte traite de l’évolution des modes alternatifs de résolution de conflit (MARC) en ligne. L’auteur dresse un historique des différents projets de médiation en ligne en passant par ses « débuts » en 1999 lorsque l’Online Ombuds Office (OOO) fut approché pour l’élaboration d’un système de médiation pour les clients d’eBay, par SquareTrade.com, par les règles de l’ICANN, par Cybersettle et Clicknsettle, etc. Il expose ensuite le courrant que prendra la cybermédiation et le cyberarbitrage dans les années à venir. Ainsi, le médium informatique devient lentement une « quatrième partie » aux discussions et peut venir en aide aux arbitres et aux médiateurs dans la gestion et la communication d’informations. De plus les fonctions d’affichages propres aux ordinateurs, c’est-à-dire la possibilité d’incorporer images, graphiques, plans, etc., devront être mis à l’œuvre par les systèmes de MARC en ligne si ceux-ci sont destinés à prendre de l’expansion dans d’autres domaines que ceux leur étant présentement réservés.

Rôle des associations de quartier dans l’organisation des services publics dans les quartiers précaires à Port-au-Prince : Une étude de cas à Village Solidarité

Port-au-Prince, la ville la plus peuplée des Caraïbes est ceinturée de quartiers précaires connus sous l’appellation de bidonvilles. Ces quartiers construits généralement sur des terrains dangereux, envahis par une population en quête de logement, abritent la plus forte proportion des habitants de la ville. Ils constituent en même temps des lieux d’observation de l’inimaginable capacité des populations locales à garantir l’accès à certains services. À travers l’action d’une association locale évoluant à Village solidarité dans la zone métropolitaine de Port-au-Prince, nous avons étudié les apports et les limites des stratégies utilisées dans l’organisation de services publics d’électricité. L’analyse repose fondamentalement sur une approche de développement local reposant sur cinq notions complémentaires et interreliées qui sont les suivantes : le projet commun, l’appartenance et l’identité collective, les ressources, le leadership, l’opportunité politique. Les résultats de la recherche font état d’un projet commun aux contours assez flous qui reflète des insuffisances au niveau des modes de pensée, et au niveau des ressources matérielles et financières mises en jeu. Le style de leadership en place au sein de l’association est teinté de déterminisme religieux, pris au piège des manœuvres clientélistes des politiciens locaux et infantilisé par l’action des agences gouvernementales. A la fin de l’étude nous dégageons des pistes pour dynamiser les forces du milieu et réorienter l’action associative afin d’aller vers un projet collectif. Ces pistes reposent fondamentalement sur la transformation des modes de pensée influençant l’action et la transformation des pratiques organisationnelles.

Dénombrement des polynômes irréductibles unitaires dans les corps finis avec différentes contraintes sur les coefficients.

Le but de ce mémoire est de dénombrer les polynômes irréductibles unitaires dans les corps finis avec certaines conditions sur les coefficients. Notre première condition sera de fixer la trace du polynôme. Par la suite, nous choisirons la cotrace lorsque la trace sera déjà fixée à zéro. Finalement, nous discuterons du cas où la trace et le terme constant sont fixés en même temps.

La distribution des zéros des fonctions L

Selon la philosophie de Katz et Sarnak, la distribution des zéros des fonctions $L$ est prédite par le comportement des valeurs propres de matrices aléatoires. En particulier, le comportement des zéros près du point central révèle le type de symétrie de la famille de fonctions $L$. Une fois la symétrie identifiée, la philosophie de Katz et Sarnak conjecture que plusieurs statistiques associées aux zéros seront modélisées par les valeurs propres de matrices aléatoires du groupe correspondant. Ce mémoire étudiera la distribution des zéros près du point central de la famille des courbes elliptiques sur $\mathbb{Q}[i]$. Brumer a effectué ces calculs en 1992 sur la famille de courbes elliptiques sur $\mathbb{Q}$. Les nouvelles problématiques reliées à la généralisation de ses travaux vers un corps de nombres seront mises en évidence

Simulation-Based Finite-Sample Normality Tests in Linear Regressions

In the literature on tests of normality, much concern has been expressed over the problems associated with residual-based procedures. Indeed, the specialized tables of critical points which are needed to perform the tests have been derived for the location-scale model; hence reliance on available significance points in the context of regression models may cause size distortions. We propose a general solution to the problem of controlling the size normality tests for the disturbances of standard linear regression, which is based on using the technique of Monte Carlo tests.

Finite-Sample Diagnostics for Multivariate Regressions with Applications to Linear Asset Pricing Models

In this paper, we propose several finite-sample specification tests for multivariate linear regressions (MLR) with applications to asset pricing models. We focus on departures from the assumption of i.i.d. errors assumption, at univariate and multivariate levels, with Gaussian and non-Gaussian (including Student t) errors. The univariate tests studied extend existing exact procedures by allowing for unspecified parameters in the error distributions (e.g., the degrees of freedom in the case of the Student t distribution). The multivariate tests are based on properly standardized multivariate residuals to ensure invariance to MLR coefficients and error covariances. We consider tests for serial correlation, tests for multivariate GARCH and sign-type tests against general dependencies and asymmetries. The procedures proposed provide exact versions of those applied in Shanken (1990) which consist in combining univariate specification tests. Specifically, we combine tests across equations using the MC test procedure to avoid Bonferroni-type bounds. Since non-Gaussian based tests are not pivotal, we apply the “maximized MC” (MMC) test method [Dufour (2002)], where the MC p-value for the tested hypothesis (which depends on nuisance parameters) is maximized (with respect to these nuisance parameters) to control the test’s significance level. The tests proposed are applied to an asset pricing model with observable risk-free rates, using monthly returns on New York Stock Exchange (NYSE) portfolios over five-year subperiods from 1926-1995. Our empirical results reveal the following. Whereas univariate exact tests indicate significant serial correlation, asymmetries and GARCH in some equations, such effects are much less prevalent once error cross-equation covariances are accounted for. In addition, significant departures from the i.i.d. hypothesis are less evident once we allow for non-Gaussian errors.

Finite-Sample Simulation-Based Inference in VAR Models with Applications to Order Selection and Causality Testing

Statistical tests in vector autoregressive (VAR) models are typically based on large-sample approximations, involving the use of asymptotic distributions or bootstrap techniques. After documenting that such methods can be very misleading even with fairly large samples, especially when the number of lags or the number of equations is not small, we propose a general simulation-based technique that allows one to control completely the level of tests in parametric VAR models. In particular, we show that maximized Monte Carlo tests [Dufour (2002)] can provide provably exact tests for such models, whether they are stationary or integrated. Applications to order selection and causality testing are considered as special cases. The technique developed is applied to quarterly and monthly VAR models of the U.S. economy, comprising income, money, interest rates and prices, over the period 1965-1996.

Elf ERAP en Irak, de 1968 à 1977

Dès sa création en 1966, l’ERAP s’est fixé pour but d’accroître la production du pétrole « franc », en diversifiant ses sources d’approvisionnement. Un tel objectif prend une tournure cruciale dès lors que les rapports tendus entre le groupe français et les autorités algériennes semblent menacer ses acquis dans le Sahara. Toutefois, se tailler une place sur le marché mondial semble à cette époque une tâche ardue, voire improbable, puisque les espaces les plus pétrolifères sont déjà occupés par les grandes sociétés, dites Majors. Néanmoins, la société d’État française réussit à s’implanter dans plusieurs pays producteurs, dont l’Irak en 1968, jusqu’alors considéré comme la chasse gardée de la Compagnie française des pétroles (CFP). Aussi, l’expérience irakienne, suite à l’insuccès en Algérie, incite Elf ERAP à se concentrer dans les pays pétroliers de l’Afrique subsaharienne et en Mer du Nord. Le 3 février 1968, Elf ERAP signe un accord avec la compagnie d’État pétrolière, INOC, pour se charger de la prospection et de l’exploitation d’une partie du territoire confisqué par l’État irakien à la puissante Iraq Petroleum Company (IPC). En contrepartie de ses apports financiers et techniques, Elf ERAP sera rémunérée par un approvisionnement garanti en pétrole irakien : il s’agit d’un nouveau genre de partenariat, dit « contrat d’agence ». Ce dernier succède au système classique des concessions et vaut à la société d’État un franc succès dans son projet de pénétration au Moyen Orient. Très vite, les prospections donnent lieu à la découverte de gisements. La production démarre en 1976 et s’élève à 5 millions de tonnes en 1977. Dès lors, Elf ERAP, devenue la SNEA, peut envisager avec optimisme son avenir énergétique, puisque sa sécurité d’approvisionnement est, en partie, assurée par le marché irakien. Mais, contre toute attente, le groupe d’État français se retire de l’affaire en mai 1977, laissant place à l’INOC, qui prend en charge le projet deux ans avant la date prévue par le contrat initial de 1968. Ce sujet de recherche consiste à éclaircir le rôle d’opérateur joué par l’ERAP en Irak, entre 1968 et 1977. Pour tenter d’expliquer le départ prématuré d’Elf Irak, il nous faut identifier les facteurs endogènes et exogènes qui ont pu motiver une telle décision. Autrement dit, la société d’État aurait-elle subi les revers de ses propres choix énergétiques ou un tel dénouement serait-il imputable à la politique pétrolière irakienne? Quelles sont les implications de la conjoncture pétrolière internationale dans le cas d’un tel retrait? Aidée des archives historiques d’Elf et de TOTAL, nous sommes arrivée à la conclusion que la compression du marché pétrolier, entre distributeurs et producteurs, au cours des années 1970, a considérablement nui à la rentabilité des contrats intermédiaires du type agence.

L'éclatement en géométrie algébrique, différentielle et symplectique

L'éclatement est une transformation jouant un rôle important en géométrie, car il permet de résoudre des singularités, de relier des variétés birationnellement équivalentes, et de construire des variétés possédant des propriétés inédites. Ce mémoire présente d'abord l'éclatement tel que développé en géométrie algébrique classique. Nous l'étudierons pour le cas des variétés affines et (quasi-)projectives, en un point, et le long d'un idéal et d'une sous-variété. Nous poursuivrons en étudiant l'extension de cette construction à la catégorie différentiable, sur les corps réels et complexes, en un point et le long d'une sous-variété. Nous conclurons cette section en explorant un exemple de résolution de singularité. Ensuite nous passerons à la catégorie symplectique, où nous ferons la même chose que pour le cas différentiable complexe, en portant une attention particulière à la forme symplectique définie sur la variété. Nous terminerons en étudiant un théorème dû à François Lalonde, où l'éclatement joue un rôle clé dans la démonstration. Ce théorème affirme que toute 4-variété fibrée par des 2-sphères sur une surface de Riemann, et différente du produit cartésien de deux 2-sphères, peut être équipée d'une 2-forme qui lui confère une structure symplectique réglée par des courbes holomorphes par rapport à sa structure presque complexe, et telle que l'aire symplectique de la base est inférieure à la capacité de la variété. La preuve repose sur l'utilisation de l'éclatement symplectique. En effet, en éclatant symplectiquement une boule contenue dans la 4-variété, il est possible d'obtenir une fibration contenant deux sphères d'auto-intersection -1 distinctes: la pré-image du point où est fait l'éclatement complexe usuel, et la transformation propre de la fibre. Ces dernières sont dites exceptionnelles, et donc il est possible de procéder à l'inverse de l'éclatement - la contraction - sur chacune d'elles. En l'accomplissant sur la deuxième, nous obtenons une variété minimale, et en combinant les informations sur les aires symplectiques de ses classes d'homologies et de celles de la variété originale nous obtenons le résultat.

Source spaces and perturbations for cluster complexes

Dans ce travail, nous définissons des objets composés de disques complexes marqués reliés entre eux par des segments de droite munis d’une longueur. Nous construisons deux séries d’espaces de module de ces objets appelés clus- ters, une qui sera dite non symétrique, la version ⊗, et l’autre qui est dite symétrique, la version •. Cette construction permet des choix de perturba- tions pour deux versions correspondantes des trajectoires de Floer introduites par Cornea et Lalonde ([CL]). Ces choix devraient fournir une nouvelle option pour la description géométrique des structures A∞ et L∞ obstruées étudiées par Fukaya, Oh, Ohta et Ono ([FOOO2],[FOOO]) et Cho ([Cho]). Dans le cas où L ⊂ (M, ω) est une sous-variété lagrangienne Pin± mono- tone avec nombre de Maslov ≥ 2, nous définissons une structure d’algèbre A∞ sur les points critiques d’une fonction de Morse générique sur L. Cette struc- ture est présentée comme une extension du complexe des perles de Oh ([Oh]) muni de son produit quantique, plus récemment étudié par Biran et Cornea ([BC]). Plus généralement, nous décrivons une version géométrique d’une catégorie de Fukaya avec seul objet L qui se veut alternative à la description (relative) hamiltonienne de Seidel ([Sei]). Nous vérifions la fonctorialité de notre construction en définissant des espaces de module de clusters occultés qui servent d’espaces sources pour des morphismes de comparaison.

Automates à contraintes semilinéaires = Automata with a semilinear constraint

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts.