View Single Post
Old 2004-08-11, 01:54   #2
wblipp's Avatar
May 2003
New Haven

3·787 Posts

Originally Posted by scottsaxman
help me understand the similarities, differences, and relationships of the various math DC projects.
There are several large projects looking for prime numbers of special types and several large projects looking to factor numbers of special types – and many small projects of both types. The prime search projects usually attempt factorization because that’s a fast way of eliminating candidates.

People flow among these various projects all the time and tool builders are usually eager to build multi-purpose tools when that’s appropriate, so there is no shortage of information and skill sharing.

Factoring usually starts with trial factoring by small divisors. Sometimes, such as Mersenne numbers, the factors are known have special structure so trial factoring can take advantage of that. Some projects, such as Sierpinski and Reisel searches, lend themselves to massively parallel trial factoring that is conceptually similar to the Sieve of Eratosthenes. The trial factoring stage in these projects is usually called sieving.

After trial factoring, methods of factoring the depend on the size of the factors are used. The usual methods here are P-1, P+1, and ECM factoring. Sometimes there are speedups available the take advantage of special structure of the numbers being tested – such as Mersenne numbers. Many of the factoring projects are centered around ECM and use standard tools to implement an ecmserver and ecmclient.

After that, there are methods that depend on the size of the number being factored. The usual methods here are Quadratic Sieve and Number Field Sieve. Both of these methods generate a large number of “relations” and then use a linear algebra stage to find combinations of the relations that may lead to factors. Number Field Sieve can handle larger composites, but large composites require lots of processing power to find lots of relations. This search for relations is also called sieving.

NFSNET is the largest open community using the Number Field Sieve to factor large numbers. It’s different from most of the other projects in that it is not devoted to numbers of a particular form. It picks numbers form other projects on the basis of mathematical interest, with a qualifier that the numbers should have had sufficient work by the other methods to be reasonably certain those methods are unlikely to succeed in factoring the number. Usually this means a complete set of ECM curves for 50 digit factors and some ECM work for 55 digit factors.

wblipp is offline