Number Theory Commons^™

Determinants And Invertibility In Finite Modular Systems, Osasu Omobude

Discovery Day - Daytona Beach

This project investigates determinants and matrix invertibility in finite modular systems, focusing on matrices over Zn. Using the Hill cipher as context, it examines the algebraic conditions under which a matrix is invertible in modular arithmetic. In particular, the project studies how the determinant determines invertibility, showing that a matrix over Zn is invertible if and only if its determinant is coprime with n.   The project further compares invertibility over the real numbers with invertibility over modular systems, highlighting the distinction between prime moduli Zp and composite moduli. In the prime case, matrices behave similarly to those over fields, where …

A New Parallel-In-Time Direct Inverse Method For Nonlinear Differential Equations, Nail K. Yamaleev, Subhash Paudel

Mathematics & Statistics Faculty Publications

We propose a new method for parallelization of the first-order backward difference discretization (BDF1) of the first-order time derivative in nonlinear partial differential equations, such as conservation law equations. The time derivative term is discretized by using the method of lines based on the implicit BDF1 scheme, while the inviscid and viscous terms are approximated by conventional 2nd-order central discretizations of the 1st- and 2nd-order derivatives in each spatial direction. The global system of nonlinear discrete equations in the space-time domain is solved by the Newton method for all time levels simultaneously. For the BDF1 discretization, this all-at-once system at …

Algorithms For Order Statistics In Farey Sequences: A Computational Study, Connor Weyers

School of Computing: Dissertations, Theses, and Student Research

Farey sequences are the sets of irreducible fractions in increasing order with denominator less or equal to some integer n. They are a well-known concept in number theory problems and are related to many other concepts in number theory including integer factoring, Fibonacci sequences, and Riemann’s Zeta function. In this paper, we investigate some known algorithms to solve certain problems in Farey sequences from a computational perspective. In particular, we implement established algorithms that have not been previously implemented with the goal of creating a package that can be used more broadly. We also develop a new algorithm for rational …

An Algorithm And Computation To Verify Legendre's Conjecture Up 7 · 1013, Jonathan Sorenson, Jonathan Webster

Computer Science and Software Engineering

We state a general purpose algorithm for quickly finding primes in evenly divided sub-intervals. Legendre’s conjecture claims that for every positive integer n, there exists a prime between n² and (n + 1)². Oppermann’s conjecture subsumes Legendre’s conjecture by claiming there are primes between n2 and n(n + 1) and also between n(n + 1) and (n + 1)². Using Cramér’s conjecture as the basis for a heuristic run-time analysis, we show that our algorithm can verify Oppermann’s conjecture, and hence also Legendre’s conjecture, for all n ≤ N in time O(N log N log …

Murmurations And Root Numbers, Alexey Pozdnyakov

University Scholar Projects

We report on a machine learning investigation of large datasets of elliptic curves and L-functions. This leads to the discovery of murmurations, an unexpected correlation between the root numbers and Dirichlet coefficients of L-functions. We provide a formal definition of murmurations, describe the connection with 1-level density, and provide three examples for which the murmuration phenomenon has been rigorously proven. Using our understanding of murmurations, we then build new machine learning models in search of a polynomial time algorithm for predicting root numbers. Based on our models and several heuristic arguments, we conclude that it is unlikely for …

Inexact Fixed-Point Proximity Algorithm For The ℓ₀ Sparse Regularization Problem, Ronglong Fang, Yuesheng Xu, Mingsong Yan

Mathematics & Statistics Faculty Publications

We study inexact fixed-point proximity algorithms for solving a class of sparse regularization problems involving the ℓ₀ norm. Specifically, the ℓ₀ model has an objective function that is the sum of a convex fidelity term and a Moreau envelope of the ℓ₀ norm regularization term. Such an ℓ₀ model is non-convex. Existing exact algorithms for solving the problems require the availability of closed-form formulas for the proximity operator of convex functions involved in the objective function. When such formulas are not available, numerical computation of the proximity operator becomes inevitable. This leads to inexact iteration algorithms. We investigate in this …

The Vulnerabilities To The Rsa Algorithm And Future Alternative Algorithms To Improve Security, James Johnson

Cybersecurity Undergraduate Research Showcase

The RSA encryption algorithm has secured many large systems, including bank systems, data encryption in emails, several online transactions, etc. Benefiting from the use of asymmetric cryptography and properties of number theory, RSA was widely regarded as one of most difficult algorithms to decrypt without a key, especially since by brute force, breaking the algorithm would take thousands of years. However, in recent times, research has shown that RSA is getting closer to being efficiently decrypted classically, using algebraic methods, (fully cracked through limited bits) in which elliptic-curve cryptography has been thought of as the alternative that is stronger than …

A Visual Tour Of Dynamical Systems On Color Space, Jonathan Maltsman

HMC Senior Theses

We can think of a pixel as a particle in three dimensional space, where its x, y and z coordinates correspond to its level of red, green, and blue, respectively. Just as a particle’s motion is guided by physical rules like gravity, we can construct rules to guide a pixel’s motion through color space. We can develop striking visuals by applying these rules, called dynamical systems, onto images using animation engines. This project explores a number of these systems while exposing the underlying algebraic structure of color space. We also build and demonstrate a Visual DJ circuit board for …

Provably Weak Instances Of Plwe Revisited, Again, Katherine Mendel

CSB and SJU Distinguished Thesis

Learning with Errors has emerged as a promising possibility for postquantum cryptography. Variants known as RLWE and PLWE have been shown to be more efficient, but the increased structure can leave them vulnerable to attacks for certain instantiations. This work aims to identify specific cases where proposed cryptographic schemes based on PLWE work particularly poorly under a specific attack.

Introduction To Discrete Mathematics: An Oer For Ma-471, Mathieu Sassolas

Open Educational Resources

The first objective of this book is to define and discuss the meaning of truth in mathematics. We explore logics, both propositional and first-order , and the construction of proofs, both formally and human-targeted. Using the proof tools, this book then explores some very fundamental definitions of mathematics through set theory. This theory is then put in practice in several applications. The particular (but quite widespread) case of equivalence and order relations is studied with detail. Then we introduces sequences and proofs by induction, followed by number theory. Finally, a small introduction to combinatorics is …

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 …

The Generalized Riemann Hypothesis And Applications To Primality Testing, Peter Hall

University Scholar Projects

The Riemann Hypothesis, posed in 1859 by Bernhard Riemann, is about zeros
of the Riemann zeta-function in the complex plane. The zeta-function can be repre-
sented as a sum over positive integers n of terms 1/ns when s is a complex number
with real part greater than 1. It may also be represented in this region as a prod-
uct over the primes called an Euler product. These definitions of the zeta-function
allow us to find other representations that are valid in more of the complex plane,
including a product representation over its zeros. The Riemann Hypothesis says that
all …

Computational Thinking In Mathematics And Computer Science: What Programming Does To Your Head, Al Cuoco, E. Paul Goldenberg

Journal of Humanistic Mathematics

How you think about a phenomenon certainly influences how you create a program to model it. The main point of this essay is that the influence goes both ways: creating programs influences how you think. The programs we are talking about are not just the ones we write for a computer. Programs can be implemented on a computer or with physical devices or in your mind. The implementation can bring your ideas to life. Often, though, the implementation and the ideas develop in tandem, each acting as a mirror on the other. We describe an example of how programming and …

Arecibo Message, Joshua P. Tan

Open Educational Resources

This two week assignment asks students to interpret and analyze the 1974 Arecibo Message sent by Drake and Sagan. Week 1 introduces the concepts behind the construction of the message and engages with a critical analysis of the architecture and the contents of the message. Week 2 asks students to develop software in a Jupyter Notebook (available for free from the Anaconda Python Distribution) to interpret messages that were similar to those produced by Drake and Sagan.

Pascal's Triangle Modulo N And Its Applications To Efficient Computation Of Binomial Coefficients, Zachary Warneke

Honors Program: Senior Projects (Public)

In this thesis, Pascal's Triangle modulo n will be explored for n prime and n a prime power. Using the results from the case when n is prime, a novel proof of Lucas' Theorem is given. Additionally, using both the results from the exploration of Pascal's Triangle here, as well as previous results, an efficient algorithm for computation of binomial coefficients modulo n (a choose b mod n) is described, and its time complexity is analyzed and compared to naive methods. In particular, the efficient algorithm runs in O(n log(a)) time (as opposed to …

Modern Cryptography, Samuel Lopez

Electronic Theses, Projects, and Dissertations

We live in an age where we willingly provide our social security number, credit card information, home address and countless other sensitive information over the Internet. Whether you are buying a phone case from Amazon, sending in an on-line job application, or logging into your on-line bank account, you trust that the sensitive data you enter is secure. As our technology and computing power become more sophisticated, so do the tools used by potential hackers to our information. In this paper, the underlying mathematics within ciphers will be looked at to understand the security of modern ciphers.

An extremely important …

Secure Multiparty Protocol For Differentially-Private Data Release, Anthony Harris

Boise State University Theses and Dissertations

In the era where big data is the new norm, a higher emphasis has been placed on models which guarantees the release and exchange of data. The need for privacy-preserving data arose as more sophisticated data-mining techniques led to breaches of sensitive information. In this thesis, we present a secure multiparty protocol for the purpose of integrating multiple datasets simultaneously such that the contents of each dataset is not revealed to any of the data owners, and the contents of the integrated data do not compromise individual’s privacy. We utilize privacy by simulation to prove that the protocol is privacy-preserving, …

Quantum Attacks On Modern Cryptography And Post-Quantum Cryptosystems, Zachary Marron

Senior Honors Theses

Cryptography is a critical technology in the modern computing industry, but the security of many cryptosystems relies on the difficulty of mathematical problems such as integer factorization and discrete logarithms. Large quantum computers can solve these problems efficiently, enabling the effective cryptanalysis of many common cryptosystems using such algorithms as Shor’s and Grover’s. If data integrity and security are to be preserved in the future, the algorithms that are vulnerable to quantum cryptanalytic techniques must be phased out in favor of quantum-proof cryptosystems. While quantum computer technology is still developing and is not yet capable of breaking commercial encryption, these …

The Rsa Cryptosystem, Rodrigo Iglesias

Williams Honors College, Honors Research Projects

This paper intends to present an overview of the RSA cryptosystem. Cryptosystems are mathematical algorithms that disguise information so that only the people for whom the information is intended can read it. The invention of the RSA cryptosystem in 1977 was a significant event in the history of cryptosystems. We will describe in detail how the RSA cryptosystem works and then illustrate the process with a realistic example using fictional characters. In addition, we will discuss how cryptosystems worked prior to the invention of RSA and the advantage of using RSA over any of the previous cryptosystems. This will help …

Efficiently Representing The Integer Factorization Problem Using Binary Decision Diagrams, David Skidmore

All Graduate Plan B and other Reports, Spring 1920 to Spring 2023

Let p be a prime positive integer and let α be a positive integer greater than 1. A method is given to reduce the problem of finding a nontrivial factorization of α to the problem of finding a solution to a system of modulo p polynomial congruences where each variable in the system is constrained to the set {0,...,p − 1}. In the case that p = 2 it is shown that each polynomial in the system can be represented by an ordered binary decision diagram with size less than 20.25log₂(α)³ + 16.5log₂(α)² + …

Shortest Path Problem Under Triangular Fuzzy Neutrosophic Information, Florentin Smarandache, Said Broumi, Assia Bakali, Mohamed Talea, Luige Vladareanu

Branch Mathematics and Statistics Faculty and Staff Publications

In this paper, we develop a new approach to deal with neutrosphic shortest path problem in a network in which each edge weight (or length) is represented as triangular fuzzy neutrosophic number. The proposed algorithm also gives the shortest path length from source node to destination node using ranking function. Finally, an illustrative example is also included to demonstrate our proposed approach.

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 …

Cayley Graphs Of Semigroups And Applications To Hashing, Bianca Sosnovski

Dissertations, Theses, and Capstone Projects

In 1994, Tillich and Zemor proposed a scheme for a family of hash functions that uses products of matrices in groups of the form $SL_2(F_{2^n})$. In 2009, Grassl et al. developed an attack to obtain collisions for palindromic bit strings by exploring a connection between the Tillich-Zemor functions and maximal length chains in the Euclidean algorithm for polynomials over $F_2$.

In this work, we present a new proposal for hash functions based on Cayley graphs of semigroups. In our proposed hash function, the noncommutative semigroup of linear functions under composition is considered as platform for the scheme. We will also …

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 …

Tabulating Pseudoprimes And Tabulating Liars, Andrew Shallue

Scholarship

This paper explores the asymptotic complexity of two problems related to the Miller-Rabin-Selfridge primality test. The first problem is to tabulate strong pseudoprimes to a single fixed base $a$. It is now proven that tabulating up to $x$ requires $O(x)$ arithmetic operations and $O(x\log{x})$ bits of space. The second problem is to find all strong liars and witnesses, given a fixed odd composite $n$. This appears to be unstudied, and a randomized algorithm is presented that requires an expected $O((\log{n})^2 + |S(n)|)$ operations (here $S(n)$ is the set of strong liars). Although interesting in their own right, a notable application …

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 …

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

Rose-Hulman Undergraduate Research Publications

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 …

Constructing Carmichael Numbers Through Improved Subset-Product Algorithms, W.R. Alford, Jon Grantham, Steven Hayman, Andrew Shallue

Scholarship

style="color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">We have constructed a Carmichael number with 10,333,229,505 prime factors, and have also constructed Carmichael numbers with style="color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;"> prime factors for every style="color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;"> between 3 and 19,565,220. These computations are the product of implementations of two new algorithms for the subset product problem that exploit the non-uniform distribution of primes style="color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">with the property that …