mersenneforum.org (https://www.mersenneforum.org/index.php)
-   -   Overview of DC Projects? (https://www.mersenneforum.org/showthread.php?t=2883)

 scottsaxman 2004-08-11 00:46

Overview of DC Projects?

Hi, there. I'm relatively new with respect to running NFSNET's client, and I'm having a hard time getting my mind wrapped around the many different math-related DC projects. Could someone help me get a bigger picture? It seems like there are several projects sieving using the same program (LLR), and more still that are using different programs. Is there more than one DC project that is effectively working on finding the same thing? Is there a lot of overlap between the projects?

I realize that competition can be very useful, but how much more efficiency could be achieved by sharing information with everyone? Or, is there anything to be gained by sharing information?

I realize these questions are somewhat vague, but I appreciate any response that will help me understand the similarities, differences, and relationships of the various math DC projects.

Scott

 wblipp 2004-08-11 01:54

[QUOTE=scottsaxman]help me understand the similarities, differences, and relationships of the various math DC projects.[/QUOTE]

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.

William

 scottsaxman 2004-08-11 02:37

So, if I might further impose on you, could you perhaps enlighten me as to which projects are "more important," or "more promising" than others? I'm sure that the answer varies greatly based on who you ask, and please realize that I respect all the people who have devoted time, energy, and resources to developing these projects as well as those who participate in the projects. What I am really trying to understand is which projects, if any, are more likely than others to produce a tangible benefit by way of new or improved machines or products or advance the understanding of mathematics in a meaningful way? I am not sure if some projects are simply looking for interesting numbers of a certain form just to have more numbers, somewhat like collecting shot glasses from different states or countries just because you like them, but not expecting them to ever lead to anything more than some good memories of all the vacations you took.

If anyone would also care to comment on risk vs. reward, such as that the Operation Billion Digits is a huge computational risk, given the low likelihood of success, but would represent a tremendous advancement should such a number be found, that'd be interesting as well.