NFS@Home Project Goals

Message boards : NFS Discussion : NFS@Home Project Goals
Message board moderation

AuthorMessage
Gigacruncher [TSBTs Pirate]
Volunteer moderator

Joined: 26 Sep 09
Posts: 210
Credit: 21,644,403
RAC: 12,081
Message 1374 - Posted: 20 Apr 2014, 12:11:12 UTC

The goal of NFS@Home is to factor large numbers using the Number Field Sieve algorithm. After setting up two polynomials and various parameters, the project participants "sieve" the polynomials to find values of two variables, called "relations," such that the values of both polynomials are completely factored. Each workunit finds a small number of relations and returns them. Once these are returned, the relations are combined together into one large file then start the "postprocessing." The postprocessing involves combining primes from the relations to eliminate as many as possible, constructing a matrix from those remaining, solving this matrix, then performing square roots of the products of the relations indicated by the solutions to the matrix. The end result is the factors of the number.

NFS@Home is interested in the continued development of open source, publicly available tools for large integer factorization. Over the past couple of years, the capability of open source tools, in particular the lattice sieve of the GGNFS suite and the program msieve, have dramatically improved.

Integer factorization is interesting both mathematical and practical perspectives. Mathematically, for instance, the calculation of multiplicative functions in number theory for a particular number require the factors of the number. Likewise, the integer factorization of particular numbers can aid in the proof that an associated number is prime. Practically, many public key algorithms, including the RSA algorithm, rely on the fact that the publicly available modulus cannot be factored. If it is factored, the private key can be easily calculated. Until quite recently, RSA-512, which uses a 512-bit modulus (155 digits), was used. As recently demonstrated by factoring the Texas Instruments calculator keys, these are no longer secure.

NFS@Home BOINC project makes it easy for the public to participate in state-of-the-art factorizations. The project interests is to see how far we can push the envelope and perhaps become competitive with the larger university projects running on clusters, and perhaps even collaborating on a really large factorization.

The numbers (to push for the state-of-art) are chosen from the Cunningham project. The project is named after Allan Joseph Champneys Cunningham, who published the first version of the factor tables together with Herbert J. Woodall in 1925. This project is one of the oldest continuously ongoing projects in computational number theory, and is currently maintained by Sam Wagstaff at Purdue University.

Concerning target size there are five sievers (application) available:

lasieved - very small numbers, uses less than 0.5 GB memory, work may be infrequently available: yes / no
lasievee_small - small numbers, uses up to 0.8 GB memory: yes / no
lasievee - medium numbers, uses up to 1 GB memory: yes / no
lasievef_small - large numbers, uses up to 1 GB memory: yes / no
lasieve5f - huge numbers, uses up to 1.25 GB memory: yes / no

How's the credit distributed per target wu?

lasieved (14e credit):36 credits per wu
lasievee_small (15e_small credit): 44 credits per wu
lasievee (15e_small credit) : 44 credits per wu
lasievef_small (16e_small credit): 50 credits per wu
lasieve5f (16e credit) : 130 credits per wu

d-14
e-15
f-16

Why the difference in credits?

The more valuable calculation gets more credit. Especially for 16e Lattice Sieve V5, the extra credit also awards for the large memory usage.

lasieved: each workunit managing 16k Q values
lasievee_small: each workunit managing 4k Q values
lasievee: each workunit managing 4k Q values
lasievef_small: each workunit managing 1k Q values
lasieve5f: each workunit managing 2k Q values

What project uses what application?

lasieved - Oddperfect, n^n+(n+1)^(n+1), Fibonacci, Lucas, Cunningham, Cullen and Woodall for SNFS difficulty below 260 (Most of the jobs best on this queue are those traditionally done with 30LP)
lasievee - Cunningham, Oddperfect, Fibonacci, Lucas or other for SNFS difficulty above 250 to ~280.
lasievee_small: All projects, within "Candidates for 15e_small should use lims no higher than 134M and Q-range no more than 180M (example: 30M-210M). "
lasievef_small: all projects, sum of the lims must not exceed 450M, up to SNFS 296+.
lasieve5f - push the state of art for very difficulty factorizations, above SNFS difficulty of 300.

The limits depends upon the boundaries chosen for the poly and characteristics of the number being factored.

Stats Pages per Application/Siever

Detailed status of lasieved (14e Lattice Sieve): https://escatter11.fullerton.edu/nfs/crunching.php
Detailed status of lasievee_small (15e Lattice Sieve for smaller numbers): https://escatter11.fullerton.edu/nfs/crunching_es.php
Detailed status of lasievee (15e Lattice Sieve): https://escatter11.fullerton.edu/nfs/crunching_e.php
Detailed status of lasievef_small (16e Lattice Sieve for smaller numbers): https://escatter11.fullerton.edu/nfs/crunching_fs.php
Detailed status of lasieve5f (16e Lattice Sieve V5): Not available

For a (much) more technical description of the NFS, see:
- Wikipedia article (http://en.wikipedia.org/wiki/Number_field_sieve)
- Briggs' Master's thesis (http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf)
ID: 1374 · Rating: 0 · rate: /
Gigacruncher [TSBTs Pirate]
Volunteer moderator

Joined: 26 Sep 09
Posts: 210
Credit: 21,644,403
RAC: 12,081
Message 1375 - Posted: 20 Apr 2014, 12:12:45 UTC

Placeholder for corrections.

24/12/2017: To be updated soon but the main has been updated.
ID: 1375 · Rating: 0 · rate: /
Gigacruncher [TSBTs Pirate]
Volunteer moderator

Joined: 26 Sep 09
Posts: 210
Credit: 21,644,403
RAC: 12,081
Message 2358 - Posted: 14 Jan 2023, 12:56:49 UTC

lasievef_small work list:

Stats Page: https://escatter11.fullerton.edu/nfs/crunching_fs.php

16e_small - GNFS
C204_147_118 Enqueued
3+2,1866M GNFS 197 Enqueued
11+4,292 GNFS 198 Enqueued
9-2,323 GNFS 199
AS 19560:i590 GNFS 203
6,505- GNFS 202 Enqueued
11+9,649L GNFS 201
AS 11040:i10244 GNFS 201

16e_small - SNFS

2,2634L SNFS 264(quartic)
2,2658M SNFS 267(quartic)
7,395- SNFS 268(quartic)
7,395+ SNFS 268(quartic)
4129^79- SNFS 285
4219^79- SNFS 286
W967 SNFS 295
13*2^946-1 SNFS 285 Enqueued
6,1002M SNFS 259 (quartic) Enqueued
ID: 2358 · Rating: 0 · rate: /
Gigacruncher [TSBTs Pirate]
Volunteer moderator

Joined: 26 Sep 09
Posts: 210
Credit: 21,644,403
RAC: 12,081
Message 2359 - Posted: 15 Jan 2023, 11:00:09 UTC

NFS@Home has a partnership with yoyo@Home (https://www.rechenkraft.net/yoyo/) where some of the integers are ECM'ed to its optimal before being fed onto the NFS@Home sievers. This happens when a factor is not found.

yoyo@Home progress, per project, can be follow up at the following address:

https://www.rechenkraft.net/yoyo/y_status_ecm.php

We would like to thank all yoyo@Home users too for their work, keep the factors coming!
ID: 2359 · Rating: 0 · rate: /
Gigacruncher [TSBTs Pirate]
Volunteer moderator

Joined: 26 Sep 09
Posts: 210
Credit: 21,644,403
RAC: 12,081
Message 2360 - Posted: 15 Jan 2023, 11:11:14 UTC

State-of-the-art factorizations

Siever to use is: lasieve5f (16e credit, 16e Lattice Sieve V5 ),130 credits per wu.

Long time goals: "Gang of 31"

```2_2222L   C228   SNFS 334 Done by yoyo@Home (Jan. 8, 2023)
2_2278M   C234   SNFS 343 Done by yoyo@Home (May. 17, 2023)
2_1151+   C236   SNFS 347 (yoyo@Home doing ECM)
2_2206L   C243   SNFS 332 Done by NFS@Home (Mar. 10, 2023)
2_1136+   C247   SNFS 342 Done by Wagstaff ECMNET (Sep. 30, 2023)
2_1139+   C248   SNFS 323 (yoyo@Home doing ECM)
2_2246L   C253   SNFS 338 Done yoyo@Home (Oct. 25, 2023 p78.c176) (charybdis is tackling the c176 done Oct 30, 2023)
2_2266L   C255   SNFS 341 (yoyo@Home doing ECM)
2_1108+   C271   SNFS 334 Done by NFS@Home (Apr. 10, 2023)
2_2354M   C271   SNFS 354 (yoyo@Home doing ECM)
2_2306L   C287   SNFS 347 (yoyo@Home doing ECM)
2_1097+   C288   SNFS 331 Done by NFS@Home (Dec. 19, 2022)
2_2222M   C289   SNFS 334 Done by NFS@Home (May 2, 2023)
2_2342M   C291   SNFS 353 (yoyo@Home doing ECM)
2_2302L   C293   SNFS 347 (yoyo@Home doing ECM)
2_2318M   C296   SNFS 349 (yoyo@Home doing ECM)
2_1163+   C297   SNFS 350 (yoyo@Home doing ECM)
2_2194M   C301   SNFS 331 Done by NFS@Home (Feb. 4, 2023)
2_2194L   C304   SNFS 331 Done by NFS@Home (Jan. 11, 2023)
2_2378L   C305   SNFS 358 (yoyo@Home doing ECM)
2_1153+   C306   SNFS 347 (yoyo@Home doing ECM)
2_2374L   C309   SNFS 358 (yoyo@Home doing ECM)
2_1124+   C311   SNFS 338 (yoyo@Home doing ECM)
2_2354L   C314   SNFS 354 (yoyo@Home doing ECM)
2_1147+   C317   SNFS 345 (yoyo@Home doing ECM)
2_1159+   C318   SNFS 349 (yoyo@Home doing ECM)
2_1168+   C326   SNFS 352 (yoyo@Home doing ECM)
2_2398M   C326   SNFS 361 (yoyo@Home doing ECM)
2_1129+   C330   SNFS 340 (yoyo@Home doing ECM)
2_1187+   C334   SNFS 358 (yoyo@Home doing ECM)
2_1123+   C338   SNFS 338 (yoyo@Home doing ECM)
```

Some of the above integers have been enqueued at https://www.rechenkraft.net/yoyo/y_status_ecm.php#tabs-2, tab Cunningham.
ID: 2360 · Rating: 0 · rate: /

Message boards : NFS Discussion : NFS@Home Project Goals

Home | My Account | Message Boards