Answers are grounded in this paper and cite their sources.
The bound to factor large integers is dominated by the computational effort to discover numbers that are B-smooth, i.e., integers whose largest prime factor does not exceed B. Smooth numbers are traditionally discovered by sieving a polynomial sequence, whereby the logarithmic sum of prime factors of each polynomial value is compared to a threshold. On a von Neumann architecture, this requires a large block of memory for the sieving interval and frequent memory updates, resulting in O(ln ln B) amortized time complexity to check each value for smoothness. This paper presents a neuromorphic sieve that achieves a constant-time check for smoothness by reversing the roles of space and time from the von Neumann architecture and exploiting two characteristic properties of brain-inspired computation: massive parallelism and constant time synaptic integration. The effects on sieving performance of two common neuromorphic architectural constraints are examined: limited synaptic weight resolution, which forces the factor base to be quantized, and maximum indegree, which forces the factor base to be partitioned. Strategies for dealing with both constraints are introduced and the approach is validated by modifying msieve, which implements the multiple polynomial quadratic sieve, to use the IBM Neurosynaptic System as a coprocessor for integer factorization.
No takes yet. Share an insight, caveat, or question.
Monaco et al. (2017) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: