NFS@Home Project Goals
Message boards :
NFS Discussion :
NFS@Home Project Goals
Message board moderation
Author | Message |
---|---|
Send message Joined: 26 Sep 09 Posts: 218 Credit: 22,841,893 RAC: 180 |
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) |
Send message Joined: 26 Sep 09 Posts: 218 Credit: 22,841,893 RAC: 180 |
Placeholder for corrections. 24/12/2017: To be updated soon but the main has been updated. |
Send message Joined: 26 Sep 09 Posts: 218 Credit: 22,841,893 RAC: 180 |
lasievef_small work list: Stats Page: https://escatter11.fullerton.edu/nfs/crunching_fs.php 16e_small - GNFS 9-2,323 GNFS 199 AS 19560:i590 GNFS 203 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 |
Send message Joined: 26 Sep 09 Posts: 218 Credit: 22,841,893 RAC: 180 |
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! |
Send message Joined: 26 Sep 09 Posts: 218 Credit: 22,841,893 RAC: 180 |
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. |