Number Theory Commons^™

Structure Of Number Theoretic Graphs, Lee Trent

Mathematical Sciences Technical Reports (MSTR)

The tools of graph theory can be used to investigate the structure
imposed on the integers by various relations. Here we investigate two
kinds of graphs. The first, a square product graph, takes for its vertices
the integers 1 through n, and draws edges between numbers whose product
is a square. The second, a square product graph, has the same vertex set,
and draws edges between numbers whose sum is a square.
We investigate the structure of these graphs. For square product
graphs, we provide a rather complete characterization of their structure as
a union of disjoint complete graphs. For …

Probability Distributions For Elliptic Curves In The Cgl Hash Function, Dhruv Bhatia, Kara Fagerstrom, Max Watson

Mathematical Sciences Technical Reports (MSTR)

Hash functions map data of arbitrary length to data of predetermined length. Good hash functions are hard to predict, making them useful in cryptography. We are interested in the elliptic curve CGL hash function, which maps a bitstring to an elliptic curve by traversing an inputdetermined path through an isogeny graph. The nodes of an isogeny graph are elliptic curves, and the edges are special maps betwixt elliptic curves called isogenies. Knowing which hash values are most likely informs us of potential security weaknesses in the hash function. We use stochastic matrices to compute the expected probability distributions of the …

Algorithmic Factorization Of Polynomials Over Number Fields, Christian Schulz

Mathematical Sciences Technical Reports (MSTR)

The problem of exact polynomial factorization, in other words expressing a polynomial as a product of irreducible polynomials over some field, has applications in algebraic number theory. Although some algorithms for factorization over algebraic number fields are known, few are taught such general algorithms, as their use is mainly as part of the code of various computer algebra systems. This thesis provides a summary of one such algorithm, which the author has also fully implemented at https://github.com/Whirligig231/number-field-factorization, along with an analysis of the runtime of this algorithm. Let k be the product of the degrees of the adjoined elements used …

Counting Solutions To Discrete Non-Algebraic Equations Modulo Prime Powers, Abigail Mann

Mathematical Sciences Technical Reports (MSTR)

As society becomes more reliant on computers, cryptographic security becomes increasingly important. Current encryption schemes include the ElGamal signature scheme, which depends on the complexity of the discrete logarithm problem. It is thought that the functions that such schemes use have inverses that are computationally intractable. In relation to this, we are interested in counting the solutions to a generalization of the discrete logarithm problem modulo a prime power. This is achieved by interpolating to p-adic functions, and using Hensel's lemma, or other methods in the case of singular lifting, and the Chinese Remainder Theorem.

Statistical Analysis Of Binary Functional Graphs Of The Discrete Logarithm, Mitchell Orzech

Mathematical Sciences Technical Reports (MSTR)

The increased use of cryptography to protect our personal information makes us want to understand the security of cryptosystems. The security of many cryptosystems relies on solving the discrete logarithm, which is thought to be relatively difficult. Therefore, we focus on the statistical analysis of certain properties of the graph of the discrete logarithm. We discovered the expected value and variance of a certain property of the graph and compare the expected value to experimental data. Our finding did not coincide with our intuition of the data following a Gaussian distribution given a large sample size. Thus, we found the …

Deconstructing The Welch Equation Using P-Adic Methods, Abigail Mann, Adelyn Yeoh

Mathematical Sciences Technical Reports (MSTR)

The Welch map x -> g^x-1+c is similar to the discrete exponential map x -> g^x, which is used in many cryptographic applications including the ElGamal signature scheme. This paper analyzes the number of solutions to the Welch equation: g^x-1+c = x (mod p^e) where p is a prime, and looks at other patterns of the equation that could possibly exploited in a similar cryptographic system. Since the equation is modulo p^e, where p is a prime number, p-adic methods of analysis are used in counting the number of solutions modulo p …

The Elliptic Curve Discrete Logarithm And Functional Graphs, Christopher J. Evans

Mathematical Sciences Technical Reports (MSTR)

The discrete logarithm problem, and its adaptation to elliptic curves, called the elliptic curve discrete logarithm problem (ECDLP) is an open problem in the field of number theory, and its applications to modern cryptographic algorithms are numerous. This paper focuses on a statistical analysis of a modification to the ECDLP, called the x-ECDLP, where one is only given the xcoordinate of a point, instead of the entire point. Focusing only on elliptic curves whose field of definition is smaller than the number of points, this paper attempts to find a statistical indication of underlying structure (or lack thereof) in the …

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 …

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 …

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 …

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 …

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 …

Ramanujan-Like Congreuences Of The Distinct Partition Function, Ian Blumenfeld, Christi Carlstead, Mimi Cukier, Wesley Terway

Mathematical Sciences Technical Reports (MSTR)

In his work with the partition function, Ramanujan observed several congruences of the form p(An + B) = 0 (mod m). We adapt this form to several congruences of the distinct partition function, p2(n). We show that one can determine all ordered pairs of integers (A;B) for which p₂(An + B)=0 (mod 2) and show families of congruences modulo 4. Finally, we offer a proof of a congruence modulo 5 satisfied by the distinct partition function.

Simultaneous Rational Approximations And Related Diophantine Equations, John Rickert

Mathematical Sciences Technical Reports (MSTR)

In this paper we consider simultaneous approximations to algebraic numbers a₁,...,a_m .