Tesis sobre el tema "Algebraic normal form"

Boolean functions play an important role in the design and analysis of symmetric-key cryptosystems, as well as having applications in other fields such as coding theory. Boolean functions acting on large number of inputs introduces the problem of computing the cryptographic properties. Traditional methods of computing these properties involve transformations which require computation and memory resources exponential in the number of input variables. When the number of inputs is large, Boolean functions are usually defined by the algebraic normal form (ANF) representation. In this thesis, methods for computing the weight and nonlinearity of Boolean functions from the ANF representation are investigated. The relation between the ANF coecients and the weight of a Boolean function was introduced by Carlet and Guillot. This expression allows the weight to be computed in $mathcal{O}(2^p)$ operations for a Boolean function containing p monomials in its ANF. In this work, a more ecient algorithm for computing the weight is proposed, which eliminates the unnecessary calculations in the weight expression. By generalizing the weight expression, a formulation of the distances to the set of linear functions is obtained. Using this formulation, the problem of computing the nonlinearity of a Boolean function from its ANF is reduced to an associated binary integer programming problem. This approach allows the computation of nonlinearity for Boolean functions with high number of input variables and consisting of small number of monomials in a reasonable time.

A new normal form x2 + y2 = c2(1 + x2y2) of elliptic curves was introduced by M. Harold Edwards in 2007 over the field k having characteristic different than 2. This new form has very special and important properties such that addition operation is strongly unified and complete for properly chosen parameter c . In other words, doubling can be done by using the addition formula and any two points on the curve can be added by the addition formula without exception. D. Bernstein and T. Lange added one more parameter d to the normal form to cover a large class of elliptic curves, x2 + y2 = c2(1 + dx2y2) over the same field. In this thesis, an expository overview of the literature on Edwards curves is given. First, the types of Edwards curves over the nonbinary field k are introduced, addition and doubling over the curves are derived and efficient algorithms for addition and doubling are stated with their costs. Finally, known elliptic curves and Edwards curves are compared according to their cryptographic applications. The way to choose the Edwards curve which is most appropriate for cryptographic applications is also explained.

Dans la première partie de cette thèse, nous étudions les équations différentielles algébriques (en abrégé EDA) linéaires et les systèmes de contrôles linéaires associés (en abrégé SCEDA). Les problèmes traités et les résultats obtenus sont résumés comme suit : 1. Relations géométriques entre les EDA linéaires et les systèmes de contrôles génériques SCEDO. Nous introduisons une méthode, appelée explicitation, pour associer un SCEDO à n'importe quel EDA linéaire. L'explicitation d'une EDA est une classe des SCEDO, précisément un SCEDO défini, à un changement de coordonnées près, une transformation de bouclage près et une injection de sortie près. Puis nous comparons les « suites de Wong » d'une EDA avec les espaces invariants de son explicitation. Nous prouvons que la forme canonique de Kronecker FCK d'une EDA linéaire et la forme canonique de Morse FCM d'un SCEDO, ont une correspondance une à une et que leurs invariants sont liés. De plus, nous définissons l'équivalence interne de deux EDA et montrons sa particularité par rapport à l'équivalence externe en examinant les relations avec la régularité interne, i.e., l'existence et l'unicité de solutions. 2. Transformation d'un SCEDA linéaire vers sa forme canonique via la méthode d'explicitation avec des variables de driving. Nous étudions les relations entre la forme canonique par bouclage FCFB d'un SCEDA proposée dans la littérature et la forme canonique de Morse pour les SCEDO. Premièrement, dans le but de relier SCEDA avec les SCEDO, nous utilisons une méthode appelée explicitation (avec des variables de driving). Cette méthode attache à une classe de SCEDO avec deux types d'entrées (le contrôle original et le vecteur des variables de driving) à un SCEDA donné. D'autre part, pour un SCEDO linéaire classique (sans variable de driving) nous proposons une forme de Morse triangulaire FMT pour modifier la construction de la FCM. Basé sur la FMT nous proposons une forme étendue FMT et une forme étendue de FCM pour les SCEDO avec deux types d'entrées. Finalement, un algorithme est donné pour transformer un SCEDA dans sa FCFB. Cet algorithme est construit sur la FCM d'un SCEDO donné par la procédure d'explicitation. Un exemple numérique illustre la structure et l'efficacité de l'algorithme. Pour les EDA non linéaires et les SCEDA (quasi linéaires) nous étudions les problèmes suivants : 3. Explicitations, analyse externe et interne et formes normales des EDA non linéaires. Nous généralisons les deux procédures d'explicitation (avec ou sans variables de driving) dans le cas des EDA non linéaires. L'objectif de ces deux méthodes est d'associer un SCEDO non linéaire à une EDA non linéaire telle que nous puissions l'analyser à l'aide de la théorie des EDO non linéaires. Nous comparons les différences de l'équivalence interne et externe des EDA non linéaires en étudiant leurs relations avec l'existence et l'unicité d'une solution (régularité interne). Puis nous montrons que l'analyse interne des EDA non linéaire est liée à la dynamique nulle en théorie classique du contrôle non linéaire. De plus, nous montrons les relations des EDAS de forme purement semi-explicite avec les 2 procédures d'explicitations. Finalement, une généralisation de la forme de Weierstrass non linéaire FW basée sur la dynamique nulle d'un SCEDO non linéaire donné par la méthode d'explicitation est proposée
In the first part of this thesis, we study linear differential-algebraic equations (shortly, DAEs) and linear control systems given by DAEs (shortly, DAECSs). The discussed problems and obtained results are summarized as follows. 1. Geometric connections between linear DAEs and linear ODE control systems ODECSs. We propose a procedure, named explicitation, to associate a linear ODECS to any linear DAE. The explicitation of a DAE is a class of ODECSs, or more precisely, an ODECS defined up to a coordinates change, a feedback transformation and an output injection. Then we compare the Wong sequences of a DAE with invariant subspaces of its explicitation. We prove that the basic canonical forms, the Kronecker canonical form KCF of linear DAEs and the Morse canonical form MCF of ODECSs, have a perfect correspondence and their invariants (indices and subspaces) are related. Furthermore, we define the internal equivalence of two DAEs and show its difference with the external equivalence by discussing their relations with internal regularity, i.e., the existence and uniqueness of solutions. 2. Transform a linear DAECS into its feedback canonical form via the explicitation with driving variables. We study connections between the feedback canonical form FBCF of DAE control systems DAECSs proposed in the literature and the famous Morse canonical form MCF of ODECSs. In order to connect DAECSs with ODECSs, we use a procedure named explicitation (with driving variables). This procedure attaches a class of ODECSs with two kinds of inputs (the original control input and the vector of driving variables) to a given DAECS. On the other hand, for classical linear ODECSs (without driving variables), we propose a Morse triangular form MTF to modify the construction of the classical MCF. Based on the MTF, we propose an extended MTF and an extended MCF for ODECSs with two kinds of inputs. Finally, an algorithm is proposed to transform a given DAECS into its FBCF. This algorithm is based on the extended MCF of an ODECS given by the explication procedure. Finally, a numerical example is given to show the structure and efficiency of the proposed algorithm. For nonlinear DAEs and DAECSs (of quasi-linear form), we study the following problems: 3. Explicitations, external and internal analysis, and normal forms of nonlinear DAEs. We generalize the two explicitation procedures (with or without driving variable) proposed in the linear case for nonlinear DAEs of quasi-linear form. The purpose of these two explicitation procedures is to associate a nonlinear ODECS to any nonlinear DAE such that we can use the classical nonlinear ODE control theory to analyze nonlinear DAEs. We discuss differences of internal and external equivalence of nonlinear DAEs by showing their relations with the existence and uniqueness of solutions (internal regularity). Then we show that the internal analysis of nonlinear DAEs is closely related to the zero dynamics in the classical nonlinear control theory. Moreover, we show relations of DAEs of pure semi-explicit form with the two explicitation procedures. Furthermore, a nonlinear generalization of the Weierstrass form WE is proposed based on the zero dynamics of a nonlinear ODECS given by the explicitation procedure

In this thesis we study algorithms for computing normal forms for matrices of Ore polynomials while controlling coefficient growth. By formulating row reduction as a linear algebra problem, we obtain a fraction-free algorithm for row reduction for matrices of Ore polynomials. The algorithm allows us to compute the rank and a basis of the left nullspace of the input matrix. When the input is restricted to matrices of shift polynomials and ordinary polynomials, we obtain fraction-free algorithms for computing row-reduced forms and weak Popov forms. These algorithms can be used to compute a greatest common right divisor and a least common left multiple of such matrices. Our fraction-free row reduction algorithm can be viewed as a generalization of subresultant algorithms. The linear algebra formulation allows us to obtain bounds on the size of the intermediate results and to analyze the complexity of our algorithms. We then make use of the fraction-free algorithm as a basis to formulate modular algorithms for computing a row-reduced form, a weak Popov form, and the Popov form of a polynomial matrix. By examining the linear algebra formulation, we develop criteria for detecting unlucky homomorphisms and determining the number of homomorphic images required.

The subject matter of this dissertation is the design, analysis and practical implementation of a new numerical method to approximate the eigenvalues and eigenfunctions of regular Sturm–Liouville problems, given in Liouville’s normal form, defined on compact intervals, with self-adjoint separated boundary conditions. These are classical problems in computational mathematics which lie on the interface between numerical analysis and spectral theory, with important applications in physics and chemistry, not least in the approximation of energy levels and wave functions of quantum systems. Because of their great importance, many numerical algorithms have been proposed over the years which span a vast and diverse repertoire of techniques. When compared with previous approaches, the principal advantage of the numerical method proposed in this dissertation is that it is accompanied by error bounds which: (i) hold uniformly over the entire eigenvalue range, and, (ii) can attain arbitrary high-order. This dissertation is composed of two parts, aggregated according to the regularity of the potential function. First, in the main part of this thesis, this work considers the truncation, discretization, practical implementation and MATLAB software, of the new approach for the classical setting with continuous and piecewise analytic potentials (Ramos and Iserles, 2015; Ramos, 2015a,b,c). Later, towards the end, this work touches upon an extension of the new ideas that enabled the truncation of the new approach, but instead for the general setting with absolutely integrable potentials (Ramos, 2014).

In spite of its 150 years history, the problem of classifying all finite-dimensional division algebras over a field k is still unsolved whenever k is not algebraically closed. The present thesis concerns some different aspects of this problem, and the related problems of classifying all composition and absolute valued algebras. A tripartition of the class of all fields is given, based on the dimensions in which division algebras over a field exist. Moreover, all finite-dimensional flexible real division algebras are classified. This class includes in particular all finite-dimensional commutative real division algebras, of which two different classifications, along different lines, are presented. It is shown that every vector product algebra has dimension zero, one, three or seven, and that its isomorphism type is determined by its adherent quadratic form. This yields a new and elementary proof for the corresponding, classical result for unital composition algebras. A rotation in a Euclidean space is an orthogonal map that locally acts as a plane rotation with a fixed angle. All pairs of rotations in finite-dimensional Euclidean spaces are classified up to orthogonal similarity. A description of all composition algebras having an LR-bijective idempotent is given. On the basis of this description, all absolute valued algebras having a one-sided unity or a non-zero central idempotent are classified.

Cette thèse est consacrée essentiellement à l'étude des métriques sous-riemanniennes dites de contact en dimension 3. Bien que cette étude soit faite localement, on observe des différences fondamentales avec les métriques riemanniennes. En particulier, les lieux conjugue et cut d'un point p contiennent p dans leur adhérence. Ce travail se divise en deux parties : 1. On montre, dans un premier temps, qu'on peut associer à toute métrique sous-riemannienne de contact formelle une forme normale formelle. Ensuite, dans un deuxième temps, on montre que cette forme normale est actuellement lisse (i. E. C, c) si la métrique l'est. Aussi, cette forme normale permet de définir des invariants associés aux métriques sous-riemanniennes de contact. 2. A l'aide de cette forme normale on prouve que l'application exponentielle d'une métrique sous-riemannienne de contact générique est déterminée par un certain jet fini de la métrique. Et on en déduit une classification générique de ces singularités (i. E. Lieux conjugués).

Groebner bases have many applications in mathematics, science, and engineering. This dissertation deals with the algorithmic aspects of computing these bases. The dissertation begins with a brief introduction of fundamental concepts about Groebner bases. Following this a discussion of various implementation issues are discussed. Much of the practical difficulties of using Groebner basis algorithms and techniques stems from the high computational complexity. It is shown that the algorithmic complexity of computing a Groebner basis primarily stems from the calculation of normal forms. This is established by studying run profiles of various computations. This leads to two options of making Groebner basis techniques more practical. They are to reduce the complexity by developing new algorithms (heuristics) or reduce running time of normal form calculations by introducing concurrency. The later approach is taken in the remainder of the dissertation where a multithreaded normal form algorithm is presented and discussed. It is shown with a simple example that the new algorithm demonstrates a speedup and scalability. The algorithm also has the advantage of being completion strategy independent. We conclude with an outline of future research involving the new algorithm.

The motivation for this thesis is the computer-assisted calculation of the Jones poly- nomial from braid words in the Artin braid group on three strands, denoted B3. The method used for calculation of the Jones polynomial is the original method that was created when the Jones polynomial was first discovered by Vaughan Jones in 1984. This method utilizes the Temperley-Lieb algebra, and in our case the Temperley-Lieb Algebra on three strands, denoted A3, thus generalizations about A3 that assist with the process of calculation are pursued.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Physics, 2002.
Includes bibliographical references (p. 92-95).
16 years and counting ... In 1986 Bednorz and Muller discovered the layered perovskite structure (La - Ba)2Cu04 which showed the phenomenon of superconductivity at the unprecedented high temperature of Tc = 33 K. In the ensuing months and years it became more and more apparent that the cuprates, as the materials came to be known, show very peculiar correlations in their "normal" state at temperatures T > Tc. The majority of this thesis is concerned with this abnormal "normal" state, attempting to extract a coherent picture for the strange phenomenology. The underlying theoretical framework is a slave particle description of the tJ model proposed by Wen and Lee. The conceptual background is rooted in Anderson's proposal of spin charge separation as the key emergent phenomenon in cuprate physics. After a brief motivation we look at single particle tunneling into the cuprate's superconducting state from the perspective of both d-wave BCS and the SU(2) slave boson theory of Wen and Lee. Both approaches work well close to zero tunneling bias. The slave particle formulation however also naturally incorporates the particle/hole asymmetric background that is seen in experiments.
(cont.) The question of single particle correlations studied experimentally via angle resolved photo emission experiments motivates the analysis of the next chapter. The broad spectral line-shapes seen experimentally imply the absence of well defined quasi-particles in the Fermi liquid sense. We study how gauge fluctuations arising from our use of slave particle coordinates affect the physical hole spectral function. The primary influence of gauge fluctuations turns out to be through their confining tendency on the vertex rather than as a scattering field for the slave particles. The last chapter discusses the effect of gauge fluctuations on the spin susceptibility and shows that they play a vital role in restoring Neel correlations. This allows us to give a natural explanation for the spin related phenomenology of underdoped cuprates.
by Walter Rantner.
Ph.D.

A Boolean function can be represented in several different forms. These different representation have advantages and disadvantages of their own. The Algebraic Normal Form, truth table, and Walsh spectrum representations are widely studied in literature. In 1999, Claude Carlet and Phillippe Guillot introduced the Numerical Normal Form. NumericalNormal Form(NNF) of a Boolean function is similar to Algebraic Normal Form, with integer coefficients instead of coefficients from the two element field. Using NNF representation, just like the Walsh spectrum, characterization of several cryptographically important functions, such as resilient and bent functions, is possible. In 2002, Carlet had shown several divisibility results concerning resilient and correlation-immune functions using NNF. With these divisibility results, Carlet is able to give bounds concerning nonlinearity of resilient and correlation immune functions. In this thesis, following Carlet and Guillot, we introduce the Numerical Normal Form and derive the pairwise relations between the mentioned representations. Characterization of Boolean, resilient and bent functions using NNF is also given. We then review the divisibility results of Carlet, which will be linked to some results on the nonlinearity of resilient and correlation immune functions. We show the Mö
bius inversion properties of NNF of a Boolean function, using Gian-Carlo Rota&rsquo
s work as a guide. Finally, using a lot of the mentioned results, we prove a necessary condition on theWalsh spectrum of Boolean functions with given degree.

Nous définissons des formes normales géodésiques pour les séries générales des groupes de réflexions complexes G(de,e,n). Ceci nécessite l'élaboration d'une technique combinatoire afin de déterminer des décompositions réduites et de calculer la longueur des éléments de G(de,e,n) sur un ensemble générateur donné. En utilisant ces formes normales géodésiques, nous construisons des intervalles dans G(e,e,n) qui permettent d'obtenir des groupes de Garside. Certains de ces groupes correspondent au groupe de tresses complexe B(e,e,n). Pour les autres groupes de Garside, nous étudions certaines de leurs propriétés et nous calculons leurs groupes d'homologie sur Z d'ordre 2. Inspirés par les formes normales géodésiques, nous définissons aussi de nouvelles présentations et de nouvelles bases pour les algèbres de Hecke associées aux groupes de réflexions complexes G(e,e,n) et G(d,1,n) ce qui permet d'obtenir une nouvelle preuve de la conjecture de liberté de BMR (Broué-Malle-Rouquier) pour ces deux cas. Ensuite, nous définissons des algèbres de BMW (Birman-Murakami-Wenzl) et de Brauer pour le type (e,e,n). Ceci nous permet de construire des représentations de Krammer explicites pour des cas particuliers des groupes de tresses complexes B(e,e,n). Nous conjecturons que ces représentations sont fidèles. Enfin, en se basant sur nos calculs heuristiques, nous proposons une conjecture sur la structure de l'algèbre de BMW
We define geodesic normal forms for the general series of complex reflection groups G(de,e,n). This requires the elaboration of a combinatorial technique in order to determine minimal word representatives and to compute the length of the elements of G(de,e,n) over some generating set. Using these geodesic normal forms, we construct intervals in G(e,e,n) that give rise to Garside groups. Some of these groups correspond to the complex braid group B(e,e,n). For the other Garside groups that appear, we study some of their properties and compute their second integral homology groups. Inspired by the geodesic normal forms, we also define new presentations and new bases for the Hecke algebras associated to the complex reflection groups G(e,e,n) and G(d,1,n) which lead to a new proof of the BMR (Broué-Malle-Rouquier) freeness conjecture for these two cases. Next, we define a BMW (Birman-Murakami-Wenzl) and Brauer algebras for type (e,e,n). This enables us to construct explicit Krammer's representations for some cases of the complex braid groups B(e,e,n). We conjecture that these representations are faithful. Finally, based on our heuristic computations, we propose a conjecture about the structure of the BMW algebra

La thèse se compose de 6 articles. (1) Nous calculons les générateurs des SA₃(ℝ)-invariants pour les surfaces paraboliques. (2) Nous calculons les invariants rigides relatifs pour les hypersurfaces rigides 2-non-dégénérées de rang de Levi constant 1 dans ℂ³: V₀, I₀, Q₀ ayant 11, 52, 824 monômes au numérateur. (3) Nous organisons tous les modèles affinement homogènes non-dégénérés dans ℂ³ en branches inéquivalentes. (4) Pour un courant harmonique dirigé autour d'une singularité linéarisée non-hyperbolique qui ne charge pas les séparatrices triviales dont l'extension triviale à travers 0 est ddc-fermée, nous démontrons que le nombre de Lelong en 0 est : 4.1) strictement positif si λ>0 ; 4.2) nul si λ est rationnel et négatif ; 4.3) nul si λ est négatif et si T est invariant sous l'action d'un sous-groupe cofini du groupe de monodromie. (5) Nous construisons des fibrés holomorphes en droites en toute dimension n>=2 non-prolongeables au sens de Hartogs. (6) Nous montrons que les matrices circulantes ayant k entrées 1 et k+1 entrées 0 dans leur première rangée sont toujours non singulières lorsque 2k+1 est soit une puissance d'un nombre premier, soit un produit de deux nombres premiers distincts. Pour tout autre entier 2k+1, nous exhibons une matrice circulante singulière
The thesis consists of 6 papers. (1) We calculate the generators of SA₃(ℝ)-invariants for parabolic surfaces. (2) We calculate rigid relative invariants for rigid constant Levi-rank 1 and 2-non-degenerate hypersurfaces in ℂ³: V₀, I₀, Q₀ having 11, 52, 824 monomials in their numerators. (3) We organize all affinely homogeneous nondegenerate surfaces in ℂ³ in inequivalent branches. (4) For a directed harmonic current near a non-hyperbolic linearized singularity which does not give mass to any of the trivial separatrices and whose trivial extension across 0 is ddc-closed, we show that the Lelong number at 0 is: 4.1) strictly positive if the eigenvalue λ>0; 4.2) zero if λ is a negative rational number; 4.3) zero if λ<0 and if T is invariant under the action of some cofinite subgroup of the monodromy group. (5) We construct non-extendable, in the sense of Hartogs, holomorphic line bundles in any dimension n>=2. (6) We show that circulant matrices having k ones and k+1 zeros in the first row are always nonsingular when 2k+1 is either a power of a prime, or a product of two distinct primes. For any other integer 2k+1 we exhibit a singular circulant matrix

Cette thèse est consacrée à l'étude des systèmes d'équations
différentielles non linéaires aux dérivées partielles. L'approche choisie est celle de l'algèbre différentielle. Étant donné un système d'équations différentielles, nous cherchons à obtenir des renseignements sur ses solutions. Pour ce faire, nous calculons une famille d'ensembles particuliers (appelés chaînes différentielles régulières) dont la réunion des solutions coïncide avec les solutions du système initial.

Les nouveaux résultats relèvent principalement du calcul formel. Le chapitre 2 clarifie le lien entre les chaînes régulières et les chaînes différentielles régulières. Deux nouveaux algorithmes (chapitres 4 et 5) viennent optimiser les algorithmes existants permettant de calculer ces chaînes différentielles régulières. Ces deux algorithmes intègrent des techniques purement algébriques qui permettent de mieux contrôler le grossissement des données et de supprimer des calculs inutiles. Des problèmes jusqu'à présent non résolus ont ainsi pu être traités. Un algorithme de calcul de forme normale d'un polynôme différentiel modulo une chaîne différentielle régulière est exposé dans le chapitre 2.

Les derniers résultats relèvent de l'analyse. Les solutions que nous considérons sont des séries formelles. Le chapitre 3 fournit des conditions suffisantes pour qu'une solution formelle soit analytique. Ce même chapitre présente un contre-exemple à une conjecture portant sur l'analycité des solutions formelles.

This thesis presents a new algorithm for computing the Hermite form of a polynomial matrix. Given a nonsingular n by n matrix A filled with degree d polynomials with coefficients from a field, the algorithm computes the Hermite form of A in expected number of field operations similar to that of matrix multiplication. The algorithm is randomized of the Las Vegas type.