Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Cryptography (4)
- Discrete Logarithm (2)
- Algebraic number theory (1)
- Aperiodic tile sets (1)
- Arbitrary dimensional tilings (1)
-
- Blum-Micali (1)
- Clustering (1)
- Computation (1)
- Computational complexity (1)
- Discrete Lambert Map (1)
- ElGamal Discrete Signature Scheme (1)
- Factorization (1)
- Graph (1)
- Greedy algorithm (1)
- Lattices (1)
- Multivariate Quadratic Equations (1)
- NP complete (1)
- Network (1)
- Non-periodic tilings (1)
- Number fields (1)
- Overdetermined System (1)
- Polynomials (1)
- Pseudorandom (1)
- Quantum Computation (1)
- Quantum computing (1)
- Random Permutations (1)
- Set covering problem (1)
- Square Discrete Exponentiation Map (1)
- Toyocrypt (1)
- Turing machine (1)
- Publication
- Publication Type
Articles 1 - 13 of 13
Full-Text Articles in Entire DC Network
Wang Tilings In Arbitrary Dimensions, Ian Tassin
Wang Tilings In Arbitrary Dimensions, Ian Tassin
Rose-Hulman Undergraduate Mathematics Journal
This paper makes a new observation about arbitrary dimensional Wang Tilings,
demonstrating that any d -dimensional tile set that can tile periodically along d − 1 axes must be able to tile periodically along all axes.
This work also summarizes work on Wang Tiles up to the present day, including
definitions for various aspects of Wang Tilings such as periodicity and the validity of a tiling. Additionally, we extend the familiar 2D definitions for Wang Tiles and associated properties into arbitrary dimensional spaces. While there has been previous discussion of arbitrary dimensional Wang Tiles in other works, it has been …
Human And Technical Factors In The Adoption Of Quantum Cryptographic Algorithms, Alyssa Pinkston
Human And Technical Factors In The Adoption Of Quantum Cryptographic Algorithms, Alyssa Pinkston
Mathematical Sciences Technical Reports (MSTR)
The purpose of this research is to understand what factors would cause users to choose quantum key distribution (QKD) over other methods of cryptography. An Advanced Encryption Standard (AES) key can be exchanged through communication using the Rivest, Shamir, Adleman (RSA) cryptographic algorithm, QKD, or post-quantum cryptography (PQC). QKD relies on quantum physics where RSA and PQC use complex mathematics to encrypt data. The BB84 quantum cryptographic protocol involves communication over a quantum channel and a public channel. The quantum channel can be technically attacked by beamsplitting or intercept/resend. QKD, like other forms of cryptography, is vulnerable to social attacks …
Applying Hallgren’S Algorithm For Solving Pell’S Equation To Finding The Irrational Slope Of The Launch Of A Billiard Ball, Sangheon Choi
Applying Hallgren’S Algorithm For Solving Pell’S Equation To Finding The Irrational Slope Of The Launch Of A Billiard Ball, Sangheon Choi
Mathematical Sciences Technical Reports (MSTR)
This thesis is an exploration of Quantum Computing applied to Pell’s equation in an attempt to find solutions to the Billiard Ball Problem. Pell’s equation is a Diophantine equation in the form of x2 − ny2 = 1, where n is a given positive nonsquare integer, and integer solutions are sought for x and y. We will be applying Hallgren’s algorithm for finding irrational periods in functions, in the context of billiard balls and their movement on a friction-less unit square billiard table. Our central research question has been the following: Given the cutting sequence of the billiard …
Analysis Of A Quantum Attack On The Blum-Micali Pseudorandom Number Generator, Tingfei Feng
Analysis Of A Quantum Attack On The Blum-Micali Pseudorandom Number Generator, Tingfei Feng
Mathematical Sciences Technical Reports (MSTR)
In 2012, Guedes, Assis, and Lula proposed a quantum attack on a pseudorandom number generator named the Blum-Micali Pseudorandom number generator. They claimed that the quantum attack can outperform classical attacks super-polynomially. However, this paper shows that the quantum attack cannot get the correct seed and provides another corrected algorithm that is in exponential time but still faster than the classical attack. Since the original classical attacks are in exponential time, the Blum-Micali pseudorandom number generator would be still quantum resistant.
The Primitive Root Problem: A Problem In Bqp, Shixin Wu
The Primitive Root Problem: A Problem In Bqp, Shixin Wu
Mathematical Sciences Technical Reports (MSTR)
Shor’s algorithm proves that the discrete logarithm problem is in BQP. Based on his algorithm, we prove that the primitive root problem, a problem that verifies if some integer g is a primitive root modulo p where p is the largest prime number smaller than 2n for a given n, which is assumed to be harder than the discrete logarithm problem, is in BQP by using an oracle quantum Turing machine.
Computer Program Simulation Of A Quantum Turing Machine With Circuit Model, Shixin Wu
Computer Program Simulation Of A Quantum Turing Machine With Circuit Model, Shixin Wu
Mathematical Sciences Technical Reports (MSTR)
Molina and Watrous present a variation of the method to simulate a quantum Turing machine employed in Yao’s 1995 publication “Quantum Circuit Complexity”. We use a computer program to implement their method with linear algebra and an additional unitary operator defined to complete the details. Their method is verified to be correct on a quantum Turing machine.
Algorithmic Factorization Of Polynomials Over Number Fields, Christian Schulz
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 …
Variance Of Clusterings On Graphs, Thomas Vlado Mulc
Variance Of Clusterings On Graphs, Thomas Vlado Mulc
Mathematical Sciences Technical Reports (MSTR)
Graphs that represent data often have structures or characteristics that can represent some relationships in the data. One of these structures is clusters or community structures. Most clustering algorithms for graphs are deterministic, which means they will output the same clustering each time. We investigated a few stochastic algorithms, and look into the consistency of their clusterings.
Structure And Randomness Of The Discrete Lambert Map, Jingjing Chen, Mark Lotts
Structure And Randomness Of The Discrete Lambert Map, Jingjing Chen, Mark Lotts
Mathematical Sciences Technical Reports (MSTR)
We investigate the structure and cryptographic applications of the Discrete Lambert Map (DLM). The mapping is closely related to the Discrete Log Problem, but has received far less attention since it is considered to be a more complicated map that is likely even harder to invert. However, this mapping is quite important because it underlies the security of the ElGamal Digital Signature Scheme. Using functional graphs induced by this mapping, we were able to find non-random properties that could potentially be used to exploit the ElGamal DSS.
The Square Discrete Exponentiation Map, A Wood
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
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 …
Statistical Investigation Of Structure In The Discrete Logarithm, Andrew Hoffman
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 …
Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer
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, …