201 |
Algorithms in Elliptic Curve CryptographyHutchinson, Aaron 23 February 2019 (has links)
<p> Elliptic curves have played a large role in modern cryptography. Most notably, the Elliptic Curve Digital Signature Algorithm (ECDSA) and the Elliptic Curve Diffie-Hellman (ECDH) key exchange algorithm are widely used in practice today for their efficiency and small key sizes. More recently, the Supersingular Isogeny-based Diffie-Hellman (SIDH) algorithm provides a method of exchanging keys which is conjectured to be secure in the post-quantum setting. For ECDSA and ECDH, efficient and secure algorithms for scalar multiplication of points are necessary for modern use of these protocols. Likewise, in SIDH it is necessary to be able to compute an isogeny from a given finite subgroup of an elliptic curve in a fast and secure fashion. </p><p> We therefore find strong motivation to study and improve the algorithms used in elliptic curve cryptography, and to develop new algorithms to be deployed within these protocols. In this thesis we design and develop <i>d</i>-MUL, a multidimensional scalar multiplication algorithm which is uniform in its operations and generalizes the well known 1-dimensional Montgomery ladder addition chain and the 2-dimensional addition chain due to Dan J. Bernstein. We analyze the construction and derive many optimizations, implement the algorithm in software, and prove many theoretical and practical results. In the final chapter of the thesis we analyze the operations carried out in the construction of an isogeny from a given subgroup, as performed in SIDH. We detail how to efficiently make use of parallel processing when constructing this isogeny. </p><p>
|
202 |
A Hodge-theoretic Study of Augmentation Varieties Associated to Legendrian Knots/TanglesSu, Tao 10 April 2019 (has links)
<p> In this article, we give a tangle approach in the study of Legendrian knots in the standard contact three-space. On the one hand, we define and construct Legenrian isotopy invariants including ruling polynomials and Legendrian contact homology differential graded algebras (LCH DGAs) for Legendrian tangles, generalizing those of Legendrian knots. Ruling polynomials are the Legendrian analogues of Jones polynomials in topological knot theory, in the sense that they satisfy the composition axiom. </p><p> On the other hand, we study certain aspects of the Hodge theory of the "representation varieties (of rank 1)" of the LCH DGAs, called augmentation varieties, associated to Legendrian tangles. The augmentation variety (with fixed boundary conditions), hence its mixed Hodge structure on the compactly supported cohomology, is a Legendrian isotopy invariant up to a normalization. This gives a generalization of ruling polynomials in the following sense: the point-counting/weight (or E-) polynomial of the variety, up to a normalized factor, is the ruling polynomial. This tangle approach in particular provides a generalization and a more natural proof to the previous known results of M.Henry and D.Rutherford. It also leads naturally to a ruling decomposition of this variety, which then induces a spectral sequence converging to the MHS. As some applications, we show that the variety is of Hodge-Tate type, show a vanishing result on its cohomology, and provide an example-computation of the MHSs.</p><p>
|
203 |
Asymptotic analysis of extreme electrochemical transportChu, Kevin Taylor January 2005 (has links)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. / Includes bibliographical references (p. 237-244). / In the study of electrochemical transport processes, experimental exploration currently outpaces theoretical understanding of new phenomena. Classical electrochemical transport theory is not equipped to explain the behavior of electrochemical systems in the extreme operating conditions required by modern devices. In this thesis, we extend the classical theory to examine the response of two electrochemical systems that form the basis for novel electrochemical devices. We first examine the DC response of an electrochemical thin film, such as the separator in a micro-battery, driven by current applied through reactive electrodes. The model system consists of a binary electrolyte between parallel-plate electrodes, each possessing a compact Stern layer which mediates Faradaic reactions with Butler-Volmer kinetics. Our analysis differs from previous studies in two significant ways. First, we impose the full nonlinear, reactive boundary conditions appropriate for electrolytic/galvanic cells. / (cont.) Since surface effects become important for physically small systems, the use of reactive boundary conditions is critical in order to gain insight into the behavior of actual electrochemical thin films that are sandwiched between reactive electrodes, especially at high current densities. For instance, our analysis shows that reaction rate constants and the Stern-layer capacitance have a strong influence on the response of the thin film. Second, we analyze the system at high current densities (far beyond the classical diffusion-limited current) which may be important for high power-density applications. At high currents, we obtain previously unknown characterizations of two interesting features at the cathode end of the cell: (i) a nested boundary layer structure and (ii) an extended space charge region. Next, we study the response of a metal (i.e., polarizable) colloid sphere in an electrolyte solution over a range of applied electric fields. / (cont.) This problem, which underlies novel electrokinetically driven microfluidic devices, has traditionally been analyzed using circuit models which neglect bulk concentration variations that arise due to double layer charging. Our analysis, in contrast, is based on the Nernst-Planck equations which explicitly allow for bulk concentration gradients. A key feature of our analysis is the use of surface conservation laws to provide effective boundary conditions that couple the double layer charging dynamics, surface transport processes, and bulk transport processes. The formulation and derivation of these surface conservation laws via boundary layer analysis is one of the main contributions of this thesis. For steady applied fields, our analysis shows that bulk concentrations gradients become significant at high applied fields and affect both bulk and double layer transport processes. We also find that surface transport becomes important for strong applied fields as a result of enhanced absorption of ions by the double layer. / (cont.) Unlike existing theoretical studies which focus on weak applied fields (so that both of these effects remain weak), we explore the response of the system to strong applied fields where both bulk concentration gradients and surface transport contribute at leading order. For the unsteady problem at applied fields that are not too strong, we find that diffusion processes, which are necessary for the system to relax to steady-state, are suppressed at leading-order but appear as higher-order corrections. This result is derived in a novel way using time-dependent matched asymptotic analysis. Unfortunately, the dynamic response of the system to large applied fields seems to introduce several complications that make the analysis (both mathematical and numerical) quite challenging; the resolution of these challenges is left for future work. Both of these problems require the use of novel techniques of asymptotic analysis (e.g., multiple parameter asymptotic expansions, surface conservation laws, and time-dependent asymptotic matching) and advanced numerical methods (e.g., pseudospectral methods, Newton-Kantorovich method, and direct matrix calculation of Jacobians) which may be applicable elsewhere. / by Kevin Taylor Chu. / Ph.D.
|
204 |
On the equivalence of two continuous homology theoriesGiever, John Bertram, 1919- January 1948 (has links)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1948. / Vita. / Includes bibliographical references (leaf 44). / by John Bertram Giever. / Ph.D.
|
205 |
Scaling limits of random plane partitions and six-vertex modelsDimitrov, Evgeni (Evgeni Simeonov) January 2018 (has links)
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2018. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 235-239). / We present a collection of results about the scaling limits of several models from integrable probability. Our first result concerns the asymptotic behavior of the bottom slice of a Hall-Littlewood random plane partition. We show the latter concentrates around a limit shape and in two different scaling regimes identify the fluctuations around this shape with the GUE Tracy- Widom distribution and the narrow wedge initial data solution to the Kardar-Parisi-Zhang (KPZ) equation. The second result concerns the limiting behavior of a class of six-vertex models in the quadrant, and we obtain the GUE-corners process as a scaling limit for this class near the boundary. Our final result, joint with Ivan Corwin, demonstrates the (long predicted) transversal 2/3 critical exponent for the height functions of the stochastic sixvertex model and asymmetric simple exclusion process (ASEP). The algebraic parts of our arguments involve the construction and use of degenerations and modifications of the Macdonald difference operators to obtain rich families of observables for the models we consider. These formulas are in terms of multiple contour integrals and provide a direct access to quantities of interest. The analytic parts of our arguments include the detailed asymptotic analysis of Fredholm determinants and contour integrals through steepest descent methods. An important aspect of our approach, is the combination of exact formulas with more probabilistic arguments, based on various Gibbs properties enjoyed by the models we study. / by Evgeni Dimitrov. / Ph. D.
|
206 |
Bouncing and walking droplets : towards a hydrodynamic pilot-wave theoryMolác̆ek, Jan, Ph. D. Massachusetts Institute of Technology January 2013 (has links)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Department of Mathematics, 2013. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 197-205). / Coalescence of a liquid drop with a liquid bath can be prevented by vibration of the bath. In a certain parameter regime, a purely vertical bouncing motion may ensue. In another, this bouncing state is destabilized by the droplet's wavefield, leading to drop motion with a horizontal component called walking. The walking drops are of particular scientific interest because Couder and coworkers have demonstrated that they exhibit many phenomena reminiscent of microscopic quantum particles. Nevertheless, prior to this work, no quantitative theoretical model had been developed to rationalize and inform the experiments before our work. In this thesis, we develop a hierarchy of theoretical models of increasing complexity in order to describe the drop's vertical and horizontal motion in the relevant parameter range. Modeling the drop-bath interaction via a linear spring is found lacking; therefore, a logarithmic spring model is developed. We first introduce this model in the context of a drop impacting a rigid substrate, and demonstrate its accuracy by comparison with existing numerical and experimental data. We then extend the model to the case of impact on a liquid substrate, and apply it to rationalize the dependence of the bouncing droplet's behaviour on the system parameters. The theoretical developments have motivated further experiments, which have in turn lead to refinements of the theory. We proceed by modeling the evolution of the standing waves created by impact on the bath, which enables us to predict the onset of walking and the dependence of the walking speed on the system parameters. New complex walking states are predicted, and subsequently validated by our detailed experimental study. A trajectory equation for the horizontal motion is obtained by averaging over the vertical bouncing. / by Jan Molác̆ek. / Ph.D.
|
207 |
A computer-aided combinatorial analysis of the game of cribbageHoff, Edwin Kevin January 1992 (has links)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1992. / Includes bibliographical references (p. 160). / by Edwin Kevin Hoff. / Ph.D.
|
208 |
New bounds on optimal binary search trees / New bounds on optimal BSTs treesHarmon, Dion (Dion Kane) January 2006 (has links)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2006. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Includes bibliographical references (p. 153-156). / Binary search trees (BSTs) are a class of simple data structures used to store and access keys from an ordered set. They have been around for about half a century. Despite their ubiquitous use in practical programs, surprisingly little is known about their optimal performance. No polynomial time algorithm is known to compute the best BST for a given sequence of key accesses, and before our work, no o(log n)-competitive online BST data structures were known to exist. In this thesis, we describe tango trees, a novel O(log log n)-competitive BST algorithm. We also describe a new geometric problem equivalent to computing optimal offline BSTs that gives a number of interesting results. A greedy algorithm for the geometric problem is shown to be equivalent to an offline BST algorithm posed by Munro in 2000. We give evidence that suggests Munro's algorithm is dynamically optimal, and strongly suggests it can be made online. The geometric model also lets us prove that a linear access algorithm described by Munro in 2000 is optimal within a constant factor. Finally, we use the geometric model to describe a new class of lower bounds that includes both of the major earlier lower bounds for the performance of offline BSTs, and construct an optimal bound in this new class. / by Dion Harmon. / Ph.D.
|
209 |
Random tilings : gap probabilities, local and global asymptotics / Gap probabilities, local and global asymptoticsKnizel, Alisa January 2017 (has links)
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2017. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 119-125). / In the thesis we explore and develop two different approaches to the study of random tiling models. First, we consider tilings of a hexagon by rombi, viewed as 3D random stepped surfaces with a measure proportional to q-volume. Such model is closely related to q-Hahn orthogonal polynomial ensembles, and we use this connection to obtain results about the local behavior of this model. In terms of the q-Hahn orthogonal polynomial ensemble, our goal is to show that the one-interval gap probability function can be expressed through a solution of the asymmetric q-Painleve V equation. The case of the q-Hahn ensemble we consider is the most general case of the orthogonal polynomial ensembles that have been studied in this context. Our approach is based on the analysis of q-connections on P1 with a particular singularity structure. It requires a new derivation of a q-difference equation of Sakai's hierarchy [75] of type A(1)/2. We also calculate its Lax pair. Following [7], we introduce the notion of the [tau]-function of a q-connection and its isomonodromy transformations. We show that the gap probability function of the q-Hahn ensemble can be viewed as the [tau]-function for an associated q-connection and its isomonodromy transformations. Second, in collaboration with Alexey Bufetov we consider asymptotics of a domino tiling model on a class of domains which we call rectangular Aztec diamonds. We prove the Law of Large Numbers for the corresponding height functions and provide explicit formulas for the limit. For a special class of examples, an explicit parametrization of the frozen boundary is given. It turns out to be an algebraic curve with very special properties. Moreover, we establish the convergence of the fluctuations of the height functions to the Gaussian Free Field in appropriate coordinates. Our main tool is a recently developed moment method for discrete particle systems. / by Alisa Knizel. / Ph. D.
|
210 |
Modules over regular algebras and quantum planesAjitabh, Kaushal January 1994 (has links)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1994. / Includes bibliographical references (leaves 95-96). / by Kaushal Ajitabh. / Ph.D.
|
Page generated in 0.0681 seconds