Analyzing Probabilistic Algorithms for Integer Factorization and Discrete Logarithm Computations

Austin Beard and Dr. Shi Bai, Department of Mathematical Sciences, Florida Atlantic University, 777 Glades Rd, Boca Raton, FL 33431

Cryptography is foundational to the security and privacy of the information and communication systems we use on a daily basis. With origins dating back thousands of years, it has been widely used in practice since World War I. With the development of modern computers, cryptography has become an essential tool for securing digital data. One important form of modern cryptography is the so-called public-key cryptographic system. In such systems, a paired public key and secret key are used. Anyone can encrypt a message using a public key, but only the party who owns the paired secret key can decrypt the message.

Public-key cryptography bases its security on conjectured hard computational problems in mathematics such as the integer factorization and the discrete logarithm problems. Such mathematical problems guarantee that it is computationally infeasible for the adversaries, who do not know the correct secret key, to break the scheme. Thus, it is crucial to understand the intrinsic difficulty of these mathematical problems, which is the focus of this project. This project is an ongoing effort to conduct a theoretical and heuristic analysis of probabilistic algorithms, with a particular focus on Pollard’s Rho algorithm and its variants for integer factorization and discrete logarithm computations. Numerical experiments are to be conducted to understand the practical behavior of Pollard’s Rho method. Detailed investigation will be conducted to understand the empirical impacts by using different parameters, such as initial input values and various pseudorandom functions in Pollard’s Rho method. Theoretical analysis will be conducted to understand the underlying principles. By doing such analysis, we can better understand the efficiency of probabilistic algorithms. In turn, such investigation has the potential to help identify strengths and weaknesses in current cryptosystems, and possibly suggest more efficient parameters.

Additional Abstract Information

Presenter: Austin Beard

Institution: Florida Atlantic University

Type: Poster

Subject: Mathematics

Status: Approved

Time and Location

Session: Poster 8
Date/Time: Tue 5:00pm-6:00pm
Session Number: 5579