Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Rose-Hulman Institute of Technology

Discipline
Keyword
Publication Year
Publication
Publication Type

Articles 61 - 74 of 74

Full-Text Articles in Discrete Mathematics and Combinatorics

Discrete Logarithm Over Composite Moduli, Marcus L. Mace Jul 2009

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 …

Go to article

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

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 …

Go to article

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

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.

Go to article

On The Action Of Weight-Preserving Sets, Matthew Badger Nov 2005

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.

Go to article

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

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.

Go to article

Mapping The Discrete Logarithm, Daniel R. Cloutier Jul 2005

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 ga 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 …

Go to article

Fixed Point And Two-Cycles Of The Discrete Logarithm, Joshua Holden Oct 2002

Fixed Point And Two-Cycles Of The Discrete Logarithm, Joshua Holden

Mathematical Sciences Technical Reports (MSTR)

We explore some questions related to one of Brizolis: does every prime p have a pair (g, h) such that h is a fixed point for the discrete logarithm with base g? We extend this question to ask about not only fixed points but also two-cycles. Campbell and Pomerance have not only answered the fixed point question for sufficiently large p but have also rigorously estimated the number of such pairs given certain conditions on g and h. We attempt to give heuristics for similar estimates given other conditions on g and h and also in the case …

Go to article

Applications Of Graph Theory To Separability, Stephen Young Jan 2002

Applications Of Graph Theory To Separability, Stephen Young

Mathematical Sciences Technical Reports (MSTR)

Let S be a surface with a triangular tiling T. Let R be a reflection a side of one of the triangles; so that R is an orientation reversing isometry of the surface. Define M = {s in S |S : Rs = s}. We then say that the surface S separates along the reflection R if S-R has two components. This paper considers the applications of graph theoretic methods to determining whether a reflection is separating or not and compares the algorithmic efficiency of these methods to the current known methods.

Go to article

Automorphic Subsets Of The N-Dimensional Cube Are Translations Of Cwatsets, Matthew Lepinski Apr 1999

Automorphic Subsets Of The N-Dimensional Cube Are Translations Of Cwatsets, Matthew Lepinski

Mathematical Sciences Technical Reports (MSTR)

It is known that automorphic subsets are generalizations of cwatsets. In this paper we show that an automorphic subset is the translation of some cwatset, and therefore that each automorphic subset is internally isomorphic to a cwatset.

Go to article

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer Jul 1998

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer

Mathematical Sciences Technical Reports (MSTR)

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP­ complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, …

Go to article

The Link Between Scrambling Numbers And Derangements, Barry Balof, Eric Farmer, Jamie Kawabata May 1997

The Link Between Scrambling Numbers And Derangements, Barry Balof, Eric Farmer, Jamie Kawabata

Mathematical Sciences Technical Reports (MSTR)

The group equation abcdef = dabecf can be reduced to the equation xcde = dxec. In general, we are interested in how many variables are needed to represent group equations in which the right side is a permutation of the variables on the left side. Scrambling numbers capture this information about a permutation. In this paper we present several facts about scrambling numbers, and expose a striking relationship between permutations that cannot be reduced and derangements.

Go to article

Generalized Conjugacy Classes, Pramod N. Achar Feb 1997

Generalized Conjugacy Classes, Pramod N. Achar

Mathematical Sciences Technical Reports (MSTR)

Generalized conjugation is the action of a group on its underlying set given by (g,x) -> p(g)xg-1, where p is some fixed endomorphism of G. Here we study combinatorial properties of the sizes of the orbits of the preceding action. In particular, we reduce the problem to a simpler case if p has nontrivial kernel, or if it is an inner automorphism, and we give a construction that allows a partial analysis in the general case.

Go to article

Cwatsets: Weights, Cardinalities, And Generalizations, Richard Mohr May 1996

Cwatsets: Weights, Cardinalities, And Generalizations, Richard Mohr

Mathematical Sciences Technical Reports (MSTR)

This report provides an upper bound on the average weight of an element in a cwatset and discusses the ratio of the cardinality of a cwatset to the cardinality of the group containing the cwatset. The concept of a generalized cwatset is also introduced.

Go to article

Hypergraph Representations And Orders Of Cwatsets, Julie Kerr Mar 1993

Hypergraph Representations And Orders Of Cwatsets, Julie Kerr

Mathematical Sciences Technical Reports (MSTR)

We determine upper bounds on the order of cwatsets of odd order.

Go to article

First Prev