Factoring Integers Using Newton's Method in the Dyadics

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.