Factoring Integers Using Newton's Method in the Dyadics
Loading...
Links to Files
Permanent Link
Author/Creator
Author/Creator ORCID
Date
2019-01-01
Type of Work
Department
Computer Science and Electrical Engineering
Program
Computer Science
Citation of Original Publication
Rights
Distribution Rights granted to UMBC by the author.
Access limited to the UMBC community. Item may possibly be obtained via Interlibrary Loan thorugh a local library, pending author/copyright holder's permission.
This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
Access limited to the UMBC community. Item may possibly be obtained via Interlibrary Loan thorugh a local library, pending author/copyright holder's permission.
This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
Subjects
Abstract
Here we expand upon the work done by Lomonaco (2013) for division of Generic Integers (an abstraction of Dyadic Integers), by extending Newton's Method for the Dyadics to find the roots of functions of Generic Integers, enabling us to compute the quotient of Generic Integers. We use this Division Algorithm as a basis for an implementation of Lomonaco's Boolean Factoring Algorithm, using a Default Representation of Generic Integers. We then implement the Algorithm using a Matrix Representation of Generic Integers, suggested by Lomonaco as a 'Top-Down Approach' that could lead to more efficient storage and usage. This led to a much improved Variant of the Boolean Factoring Algorithm, drastically decreasing the runtime. Finally, we improved the Algorithm further by using a 'Generic Prime,' which uses the Matrix Representation of Generic Integers more intelligently for Factoring Applications. Using Generic Primes for the Boolean Factoring Algorithm, we were able to factor semiprimes with 54 bits, though the time that it took was still not competitive with industry standards.