Breaking up factoring problems.

Breaking up factoring problems

That an 81-digit number has now been factored isn't particularly surprising, although this sets a new record for the largest "hard" number yet cracked by a general-purpose factoring method. Rapidly improving computers and factoring algorithms made this inevitable (SN: 3/30/85, p. 202). The surprise is that it was done using eight linked microcomputers rather than a supercomputer or a factoring machine.

To find all the factors of 2.sup.269 + 1, mathematician Robert D. Silverman of the Mitre Corp. in Bedford, Mass., used a new version of the "quadratic sieve" factoring algorithm. His version, based on mathematical ideas suggested by Peter Montgomery of Systems Development Corp. in Santa Monica, Calif., breaks the problem down into several independent parts that can be run in parallel on separate computers. Silverman describes his method in an upcoming issue of MATHEMATICS OF COMPUTATION.

Using this enhanced method, eight Sun microcomputers took about 150 hours each to come up with a solution. Moreover, the computers completed the computations in their spare time, working in the evenings and on weekends.

Although a supercomputer could have done the job more quickly the use of microcomputers shows that large numbers can be factored reasonably quickly using inexpensive equipment. This may threaten the security of secret codes that rely on the difficulty of factoring large numbers (SN: 1/14/84, p. 20).