ARL scientists demo factors integers at faster pace, computing architectures have more options in SWaP-constrained environments
NewsMarch 14, 2018
ABERDEEN PROVING GROUND, Md. Scientists at the U.S. Army Research Laboratory (ARL) are leveraging emerging brain-like computer architectures for an age-old number-theoretic problem known as integer factorization. The resulting factor is that Army scientists are opening up a new solution space that moves away from traditional computing architectures and towards devices that are able to operate within extreme size, weight, and power (SWaP)-constrained environments.
"With more computing power in the battlefield, we can process information and solve computationally-hard problems quicker," says Dr. John V. "Vinnie" Monaco, an ARL computer scientist. "Programming the type of devices that fit this criteria, for example, brain-inspired computers, is challenging, and cracking crypto codes is just one application that shows we know how to do this."
Public key encryption is a method of secure communication used widely today, based on the RSA algorithm developed by Rivest, Shamir, and Adleman in 1978. The security of the RSA algorithm relies on the difficulty of factoring a large composite integer N, the public key, which is distributed by the receiver to anyone who wants to send an encrypted message. If N can be factored into its prime components, then the private key, needed to decrypt the message, can be recovered. However, the difficulty in factoring large integers quickly becomes apparent.
As the size of N increases by a single digit, the time it would take to factor N by trying all possible combinations of prime factors is approximately doubled. Dr. Manuel Vindiola and Dr. Monaco demonstrated how brain-like computers lend a speedup to the currently best known algorithms for factoring integers. The team of researchers have devised a way to factor large composite integers by harnessing the massive parallelism of novel computer architectures that mimic the functioning of the mammalian brain. So called neuromorphic computers operate under vastly different principles than conventional computers, such as laptops and mobile devices, all based on an architecture described by John von Neumann in 1945.
The speedup acquired by the ARL researchers is due to the formulation of a method for integer factorization with the help of a neuromorphic co-processor. The current fastest algorithms for factoring integers consist primarily of two stages, sieving and a matrix reduction, and the sieving stage comprises most of the computational effort.
Sieving involves searching for many integers that satisfy a certain property called B-smooth, integers that don't contain a prime factor greater than B. Monaco and Vindiola were able to construct a neural network that discovers B-smooth numbers quicker and with greater accuracy than on a von Neumann architecture. Their algorithm leverages the massive parallelism of brain-inspired computers and the innate ability of individual neurons to perform arithmetic operations, such as addition. As neuromorphic architectures continue to increase in size and speed, not limited by Moore's Law, their ability to tackle larger integer factorization problems also grows. In their work, it's estimated that 1024-bit keys could be broken in about a year, a task once thought to be out of reach. For comparison, the current record, a 232 decimal digit number (RSA-768) took about 2,000 years of computing time over the course of several years.
This work also opens the door to new research areas of emerging computer architectures, in terms of algorithm design and function representation, alongside low-power machine learning and artificial intelligence applications. "Encrypted messages in warfare often have an expiration date, when their contents become un-actionable," Monaco explains. "There is an urgency to decrypt enemy communications, especially those at the field level, since these expire the quickest, compared to communication at higher echelons. In field conditions, power and connectivity are extremely limited. This is a strong motivating factor for using a brain-inspired computer for such a task where conventional computers are not practical."
The article referenced appears in print in March 2018: J. V. Monaco and M. M. Vindiola, Factoring Integers With a Brain-Inspired Computer, in IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 65, no. 3, pp. 1051-1062, March 2018, doi: 10.1109/TCSI.2017.2771533. A preliminary version of this work won Best Paper Award in the 50th IEEE International Symposium on Circuits and Systems, Integer factorization with a neuromorphic sieve, 2017 IEEE International Symposium on Circuits and Systems (ISCAS).
