Open Access. Powered by Scholars. Published by Universities.®
- Discipline
Articles 1 - 3 of 3
Full-Text Articles in Mathematics
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.
Structure Of Number Theoretic Graphs, Lee Trent
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 …