Factoring IntegersThe Factoring Problem Given an integer Solution An algorithm for factoring integers on general purpose machines or special purpose hardware for factoring.
Though the factoring problem is easy to state, the solution is
not easy. Here, by easy we mean computationally
efficient. Abiding by the general complexity theory
convention, a solution will be called easy or
computationally efficient if the running time of the solution
algorithm is of a polynomial order in terms of the input size
Factoring AlgorithmsReference: Wikipedia [Most of the links point to Wikipedia articles] Special-Purpose Algorithms A special-purpose factoring algorithm's running time depends on the properties of its unknown factors: size, special form, etc. Exactly what the running time depends on varies between algorithms.
General-Purpose Algorithms A general-purpose factoring algorithm's running time depends solely on the size of the integer to be factored. These are mostly based on congruence-of-squares method.
Quick Comparison Chart
Notation:
Factoring HardwareReference: Journal articles and conference proceedings [Most of the links point to different section of this document for details] The best algorithms for factoring, till date, are Elliptic Curve Method (for small prime factors) and General Number Field Sieve (for arbitrary numbers without any known/anticipated structure). While ECM relies on fast elliptic curve point multiplication and fast finite field arithmetic, the Number Field Sieve depends heavily on relation generation (sieving by primes for smoothness verification) and fast linear algebra over GF(2). Most of the special purpose hardware for factoring has been proposed to facilitate either of these three areas of computation. We will discuss some of the following in the scope of this project. Hardware from the Past
Modern Day Sieving Hardware
Hardware for NFS: Relation Collection
Hardware for NFS: Linear Algebra
Hardware of the Future
|