Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
Thesis.pdf (739.78 KB)
ETD Abstract Container
Abstract Header
An application of the LLL algorithm to integer factorization
Author Info
Pineda, Gerwin
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=osu1531350449773791
Abstract Details
Year and Degree
2018, Master of Mathematical Sciences, Ohio State University, Mathematical Sciences.
Abstract
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) log
2
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.
Committee
Ghaith Hiary (Advisor)
James Cogdell (Committee Member)
Pages
65 p.
Subject Headings
Mathematics
Keywords
Integer factorization, LLL algorithm
Recommended Citations
Refworks
EndNote
RIS
Mendeley
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)
Abstract Footer
Document number:
osu1531350449773791
Download Count:
976
Copyright Info
© 2018, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.