Mathematics Commons^™

The Square Discrete Exponentiation Map, A Wood

Mathematical Sciences Technical Reports (MSTR)

We will examine the square discrete exponentiation map and its properties. The square discrete exponentiation map is a variation on a commonly seen problem in cryptographic algorithms. This paper focuses on understanding the underlying structure of the functional graphs generated by this map. Specifically, this paper focuses on explaining the in-degree of graphs of safe primes, which are primes of the form p = 2q + 1, where q is also prime.

Algebraic Solutions To Overdefined Systems With Applications To Cryptanalysis, Eric Crockett

Mathematical Sciences Technical Reports (MSTR)

Cryptographic algorithms are based on a wide variety of difficult problems in mathematics. One of these problems is finding a solution to a system of multivariate quadratic equations (MQ). A generalization of this problem is to find a solution to a system of higher order non-linear equations. Both of these problems are NP-hard over any field. Many cryptosystems such as AES, Serpent, Toyocrypt, and others can be reduced to some form of the MQ problem. In this paper we analyze the relinearization and XL algorithms for solving overdetermined systems of non-linear equations, as well as two variations of the XL …

The Digraph Of The Square Mapping On Elliptic Curves, Katrina Glaeser

Mathematical Sciences Technical Reports (MSTR)

Consider a subgroup of an elliptic curve generated by a point P of order n. It is possible to match any point Q to an integer k (mod n) such that Q = kP using a brute force method. By observing patterns in the digraph of the squaring map on the integers modulo n it is possible to perform this matching. These techniques can be applied to solving the Elliptic Curve Discrete Log Problem given a complete graph of the square mapping k P -> k^2 P for the elliptic curve points.

Operations Research Methods For Optimization In Radiation Oncology, M Ehrgott, Allen Holder

Mathematical Sciences Technical Reports (MSTR)

Operations Research has a successful tradition of applying mathematical analysis to a wide range of applications, with one of the burgeoning areas of growth being in medical physics. The original application was in the optimal design of the influence map for a radiotherapy treatment, a problem that has continued to receive attention. However, operations research has been applied to other clinical problems like patient scheduling, vault design, and image alignment. The overriding theme of this article is to present how techniques in operations research apply to clinical problems, which we accomplish in three parts. First, we present the perspective from …

Flattening A Cone, Sean A. Broughton

Mathematical Sciences Technical Reports (MSTR)

We want to manufacture a cut-off slanted cone from a flat sheet of metal. If the cone were a normal right cone we know that we would simply cut out a sector of a circle and roll it up. However the cone is slanted. We want to know what the flattened shape looks like so that we can cut it out and roll it up to closely approximate correct final shape. We also want to minimize the amount of wasted metal after the shape is cut out.

The problem, and it generalizations may be solved analytically but the analytical solution …

Solving The P-Median Problem With Insights From Discrete Vector Quantization, Gino J. Lim, Allen Holder, Josh Reese

Mathematical Sciences Technical Reports (MSTR)

The goals of this paper are twofold. First, we formally equate the p-median problem from facility location to the optimal design of a vector quantizer. Second, we use the equivalence to show that the Maranzana Algorithm can be interpreted as a projected Lloyd Algorithm, a fact that improves complexity. Numerical results verify significant improvements in run-time.

A Decomposition Of The Pure Parsimony Problem, Allen Holder, Thomas M. Langley

Mathematical Sciences Technical Reports (MSTR)

We partially order a collection of genotypes so that we can represent the problem of inferring the least number of haplotypes in terms of substructures we call g-lattices. This representation allows us to prove that if the genotypes partition into chains with certain structure, then the NP-Hard problem can be solved efficiently. Even without the specified structure, the decomposition shows how to separate the underlying integer programming model into smaller models.

A Clustering Approach For Optimizing Beam Angles In Imrt Planning, Gino J. Lim, Allen Holder, Josh Reese

Mathematical Sciences Technical Reports (MSTR)

In this paper we introduce a p-median problem based clustering heuristic for selecting efficient beam angles for intensity-modulated radiation therapy. The essence of the method described here is the clustering of beam angles according to probability that an angle will be observed in the final solution and similarities among different angles and the selection of a representative angle from each of the p resulting cluster cells. We conduct experiments using several combinations of modeling parameters to find the conditions where the heuristic best performs. We found a combination of such parameters that outperformed all other parameters on three of the …

Statistical Investigation Of Structure In The Discrete Logarithm, Andrew Hoffman

Mathematical Sciences Technical Reports (MSTR)

The absence of an efficient algorithm to solve the Discrete Logarithm Problem is often exploited in cryptography. While exponentiation with a modulus is extremely fast with a modern computer, the inverse is decidedly not. At the present time, the best algorithms assume that the inverse mapping is completely random. Yet there is at least some structure, and to uncover additional structure that may be useful in constructing or refining algorithms, statistical methods are employed to compare modular exponential mappings to random mappings. More concretely, structure will be defined by representing the mappings as functional graphs and using parameters from graph …

Discrete Logarithm Over Composite Moduli, Marcus L. Mace

Mathematical Sciences Technical Reports (MSTR)

In an age of digital information, security is of utmost importance. Many encryption schemes, such as the Diffie-Hellman Key Agreement and RSA Cryptosystem, use a function which maps x to y by a modular power map with generator g. The inverse of this function - trying to find x from y - is called the discrete logarithm problem. In most cases, n is a prime number. In some cases, however, n may be a composite number. In particular, we will look at when n = p^b for a prime p. We will show different techniques of obtaining graphs of this …

Structural Properties Of Power Digraphs Modulo N, Joseph Kramer-Miller

Mathematical Sciences Technical Reports (MSTR)

We define G(n, k) to be a directed graph whose set of vertices is {0, 1, ..., n−1} and whose set of edges is defined by a modular relation. We say that G(n, k) is symmetric of order m if we can partition G(n, k) into subgraphs, each containing m components, such that all the components in a subgraph are isomorphic. We develop necessary and sufficient conditions for G(n, k) to contain symmetry when n is odd and square-free. Additionally, we use group theory to describe the structural properties of the subgraph of G(n, k) containing only those vertices relatively …

Do The Coefficients Of A Modular Form Really "Encode Arithmetic Data"?, Ken Mcmurdy, Hari Ravindran

Mathematical Sciences Technical Reports (MSTR)

Language and terminology are so critical to the understanding of modern math- ematics that it is often difficult for even very good mathematicians from different fields to discuss their work in any detail. As a result, common phrases often evolve within each discipline which attempt to capture the avor of some impor- tant idea while avoiding technicality and jargon. For example, when algebraic number theorists are asked why they are so interested in modular forms, it has become common to say with enthusiasm that the coefficients of a modular form "encode arithmetic data". If pressed further, one might go on …

Radiotherapy Optimal Design: An Academic Radiotherapy Treatment Design System, R Acosta, W Brick, A Hanna, Allen Holder, D Lara, G Mcquillen, D Nevin, P Uhlig, B Salter

Mathematical Sciences Technical Reports (MSTR)

Optimally designing radiotherapy and radiosurgery treatments to increase the likelihood of a successful recovery from cancer is an important application of operations research. Researchers have been hindered by the lack of academic software that supports head-to-head comparisons of different techniques, and this article addresses the inherent difficulties of designing and implementing an academic treatment planning system. In particular, this article details the algorithms and the software design of Radiotherapy optimAl Design (RAD).

A Statistical Look At Maps Of The Discrete Logarithm, Nathan Lindle

Mathematical Sciences Technical Reports (MSTR)

Cryptography is being used today more than it ever has in the past. Millions of transactions are being conducted every hour using encrypted channels, most of which use the Internet as their medium. It is taken for granted by the average user that these transaction are secure, but mathematicians and computer scientists alike are constantly testing the algorithms being used. Several of these cryptosystems use the transformation

g^x = y (mod n)

The appeal of this transformation is that it is quite simple to calculate gx mod n; exponentiation by squaring is fairly simple and quick even using …

The Discrete Logarithm Problem And Ternary Functional Graphs, Max F. Brugger, Christina A. Frederick

Mathematical Sciences Technical Reports (MSTR)

Encryption is essential to the security of transactions and communications, but the algorithms on which they rely might not be as secure as we all assume. In this paper, we investigate the randomness of the discrete exponentiation function used frequently in encryption. We show how we used exponential generating functions to gain theoretical data for mapping statistics in ternary functional graphs. Then, we compare mapping statistics of discrete exponentiation functional graphs, for a range of primes, with mapping statistics of the respective ternary functional graphs.

The Barycenter Of The Numerical Range Of A Matrix, Sean A. Broughton, Roger G. Lautzenheiser, Thomas Werne

Mathematical Sciences Technical Reports (MSTR)

The numerical range W(A) of an nxn matrix A is the totality of the scalar products <Ax,x> as x varies over all unit vectors in Cⁿ The barycenter (center of mass) of the numerical range is defined geometrically as the center of mass of W(A) considered as a planar lamina with variable density and also as a limit of sample averages (<Ax₁,x₁>+...+<Ax_N,x_N>)/N. Under a wide range the sampling schemes it is shown that the barycenter is the average of the spectrum …

Isomorphisms Of Elliptic Curves Over Extensions Of Finite Fields, Mathew Niemerg

Mathematical Sciences Technical Reports (MSTR)

Our main interest lies in exploring isomorphisms of elliptic curves. In particular, we focus on two curves defined over a base field and look at which extension fields the curves are isomorphic over. Elliptic curves have a fascinating structure behind them. This structure allows for much to be explored and studied.

Foundations Of Generalized Cwatsets, Jesse Beder

Mathematical Sciences Technical Reports (MSTR)

We present a new, abstract definition for a generalized cwatset that produces notions of subcwatset and quotient cwatset that behave naturally. We use small cancellation theory to prove a result analogous to the statement that every group is isomorphic to some permutation group.

On The Action Of Weight-Preserving Sets, Matthew Badger

Mathematical Sciences Technical Reports (MSTR)

We introduce weight-preserving sets of binary words. Any transformation that respects the row and column weights of a 0-1 matrix can be decomposed as a composition of two types of action on the matrix. We conjecture that weight-preserving sets perform only one type of action, permutations of rows and columns; i.e., weight-preserving sets are cwatsets.

Big Cwatsets And Hamming Code, Matthew Davis, Thomas M. Langley, Norah Mazel

Mathematical Sciences Technical Reports (MSTR)

In contrast to Lagrange's Theorem in Finite Group Theory, we show that the ratio of the largest proper cwatset of degree d to the size of binary d-space approaches 1 as d approaches infinity. We show how to explicitly construct large cwatsets as cosets of Hamming Codes, and discuss many open questions that arise.

Thermal Imaging Of Circular Inclusions Within A Two-Dimensional Region, Shannon Talbott, Hilary Spring

Mathematical Sciences Technical Reports (MSTR)

The ability to study the interior of an object without destroying it is an important industrial tool. One method of recent interest is steady-state thermal or impedance imaging. In this paper we will use the steady-state heat equation to locate one or more circular inclusions within a two-dimensional region, where the boundaries of the inclusions have partially disbonded from the surrounding material; this disbond is modelled as between the heat flux and jump discontinuity at the disbonded interface.

Time-Dependent Thermal Imaging Of Circular Inclusions, Donald L. Brouwn, Mark Hubenthal

Mathematical Sciences Technical Reports (MSTR)

This paper considers the inverse problem of locating one or more circular inclusions in a two-dimensional domain using thermal boundary data, specifically, the input heat flux and measured boundary temperature. The forward problem is governed by the heat equation. We show how the position and size of such defects can be recovered using the boundary data and various approximations of the solution to the forward problem. We also consider the stability of the algorithm involved to recover the defects.

Mapping The Discrete Logarithm, Daniel R. Cloutier

Mathematical Sciences Technical Reports (MSTR)

The discrete logarithm is a problem that surfaces frequently in the field of cryptog- raphy as a result of using the transformation g^a mod n. This paper focuses on a prime modulus, p, for which it is shown that the basic structure of the functional graph is largely dependent on an interaction between g and p-1. In fact, there are precisely as many different functional graph structures as there are divisors of p-1. This paper extracts two of these structures, permutations and binary functional graphs. Estimates exist for the shape of a random permutation, but …

Reconstruction Of Partially Conductive Cracks Using Boundary Data, David Mccune, Janine Haugh

Mathematical Sciences Technical Reports (MSTR)

This paper develops an algorithm for finding one or more non-insulated, pair-wise disjoint, linear cracks in a two dimensional region using boundary measurements.

The Birational Isomorphism Types Of Smooth Real Elliptic Curves, Sean A. Broughton

Mathematical Sciences Technical Reports (MSTR)

In this note we determine all birational isomorphism types of real elliptic curves and show that it is the same as the orbit space of smooth cubic real curves in real projective space under linear projective equivalence. There are two families, each depending polynomially on a real parameter in a open subinterval of R. We further show that the complexification of a real elliptic curve has exactly two real forms. Thus the real elliptic curves come in pairs which are isomorphic over C. Finally, the map taking a real elliptic curve to its j-invariant maps the two families …

Reconstruction Of An Unknown Boundary Portion From Cauchy Data In N-Dimensions, Kurt M. Bryan, Lester Caudill

Mathematical Sciences Technical Reports (MSTR)

We consider the inverse problem of determining the shape of some inacces­ sible portion of the boundary of a region in n dimensions from Cauchy data for the heat equation on an accessible portion of the boundary. The inverse problem is quite ill-posed, and nonlinear. We develop a Newton-like algorithm for solving the problem, with a simple and efficient means for computing the required derivatives, develop methods for regularizing the process, and provide computational examples

Determining The Length Of A One-Dimensional Bar, Natalya Yarlikina, Holly Walrath

Mathematical Sciences Technical Reports (MSTR)

In this paper we examine the inverse problem of determining the length of a one-dimensional bar from thermal measurements (temperature and heat flux) at one end of the bar (the "accessible" end); the other inaccessible end of the bar is assumed to be moving. We develop two different approaches to estimating the length of the bar, and show how one approach can also be adapted to find unknown boundary conditions at the inaccessible end of the bar.

When Abelian Groups Split, Rachel M. Thomas, Robert C. Rhoades

Mathematical Sciences Technical Reports (MSTR)

Let S be a hyperbolic surface tiled by kaleidoscopic triangles. Let R_e denote the set of fixed points by the reflection in an edge, e, of a triangle. We say that R_e is separating if S-R_e has two components. Once we have a tiling, we can define a group of orientation preserving transformations, G. We develop a method for determining when a reflection is separating using the group algebra of G. Using this method we give necessary and sufficient conditions for a mirror to be separating when G is abelian. We also conjecture, that …

Hyperbolic Billiard Paths, Rebecca Lehman, Chad White

Mathematical Sciences Technical Reports (MSTR)

A useful way to investigate closed geodesics on a kaleidoscopically tiled surface is to look at the billiard path described by a closed geodesic on a single tile. When looking at billiard paths it is possible to ignore surfaces and restrict ourselves to the tiling of the hyperbolic plane. We classify the smallest billiard paths by wordlength and parity. We also demonstrate the existence of orientable paths and investigate conjectures about the billiard spectrum for the (2, 3, 7)-tiling.

Pigeon-Holing Monodromy Groups, Niles G. Johnson

Mathematical Sciences Technical Reports (MSTR)

A simple tiling on a sphere can be used to construct a tiling on a d-fold branched cover of the sphere. By lifting a so-called equatorial tiling on the sphere, the lifted tiling is locally kaleidoscopic, yielding an attractive tiling on the surface. This construction is via a correspondence between loops around vertices on the sphere and paths across tiles on the cover. The branched cover and lifted tiling give rise to an associated monodromy group in the symmetric group on d symbols. This monodromy group provides a beautiful connection between the cover and its base space. Our investigation …