Number Theory Commons^™

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

Contemporary Mathematical Approaches To Computability Theory, Luis Guilherme Mazzali De Almeida

Undergraduate Student Research Internships Conference

In this paper, I present an introduction to computability theory and adopt contemporary mathematical definitions of computable numbers and computable functions to prove important theorems in computability theory. I start by exploring the history of computability theory, as well as Turing Machines, undecidability, partial recursive functions, computable numbers, and computable real functions. I then prove important theorems in computability theory, such that the computable numbers form a field and that the computable real functions are continuous.

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 Theses

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 is the search …

Tabulating Pseudoprimes And Tabulating Liars, Andrew Shallue

Andrew Shallue

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

We have constructed a Carmichael number with 10,333,229,505 prime factors, and have also constructed Carmichael numbers with prime factors for every 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 with the property that divides a highly composite .

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

Andrew Shallue

We have constructed a Carmichael number with 10,333,229,505 prime factors, and have also constructed Carmichael numbers with  prime factors for every  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 with the property that  divides a highly composite .