Skip to Main Content
 

Global Search Box

 
 
 
 

Files

ETD Abstract Container

Abstract Header

An application of the LLL algorithm to integer factorization

Abstract Details

2018, Master of Mathematical Sciences, Ohio State University, Mathematical Sciences.
Solving the shortest vector problem algorithmically gained a boom with the publication of the LLL algorithm in 1982. Many problems can be reformulated as finding the shortest vector in a lattice, and the LLL can provide very good approximations to their true solutions. One of these problems is the factorization of a large integer given partial information about one of its factors. Coppersmith describes a novel method to do this in [4], which enables the factorization of a large integer N in polynomial time in log N, provided that (1/4) log2 N of the high order bits of one of the factors of N are given. However, in practice, this might require guessing some of the middle bits of the partially known factor and then apply the Coppersmith separately for each guess. In this thesis, we explore the LLL algorithm and how much information the Coppersmith method needs to factor N in one run. We also study the parameters of the Coppersmith algorithm with the hope of reducing the amount of information needed by it. We provide the Mathematica code for the various computations that we did, as well as instructive examples.
Ghaith Hiary (Advisor)
James Cogdell (Committee Member)
65 p.

Recommended Citations

Citations

  • Pineda, G. (2018). An application of the LLL algorithm to integer factorization [Master's thesis, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1531350449773791

    APA Style (7th edition)

  • Pineda, Gerwin. An application of the LLL algorithm to integer factorization. 2018. Ohio State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1531350449773791.

    MLA Style (8th edition)

  • Pineda, Gerwin. "An application of the LLL algorithm to integer factorization." Master's thesis, Ohio State University, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=osu1531350449773791

    Chicago Manual of Style (17th edition)