Register FAQ Search Today's Posts Mark Forums Read

 2021-11-05, 02:47 #980 charybdis     Apr 2020 11·53 Posts Depends how much detail you want NFS has three stages. 1. Polynomial selection. You need to find two polynomials f(x) and g(x) that have a common root modulo N, the number you want to factor. In general smaller coefficients are better. Almost always g(x) (the "rational polynomial") will be linear, and f(x) (the "algebraic polynomial") will have higher degree, usually 4, 5 or 6. SNFS is when the form of the number naturally gives you such polynomials: for the number we're discussing here, these are 31479823396757*x^6-1 and x-31479823396757^3, which have common root 31479823396757^3 mod N. GNFS is for numbers that don't have a special form, and the polynomials must be found by computer search. There are algorithms for this that are used by msieve and CADO. The "c6" and "c0" lines in the polynomial file are the coefficients of the algebraic polynomial; I omitted c5 to c1 because those are all zero. The rational polynomial coefficients are Y1 and Y0. 2. Sieving. This consists of finding some large number of "relations". In some sense these are like equations in a large number of variables, such that if enough are found, the resulting system of equations can be solved. I like LaurV's explanation here. There are lots of different parameters that control sieving: this is what rlim/alim, lpbr/lpba etc are doing. 3. Postprocessing. This is where the relations are combined together and the system of equations is solved. Each solution to the equations has a 50% chance of finding the factors. SNFS is much faster than GNFS for numbers of the same size (where, as I mentioned above, it's the size of the original number that matters for SNFS). A rough approximation is that SNFS of d digits is equivalent to GNFS of 0.69*d digits, but this doesn't hold when the SNFS polynomial has large coefficients or the "wrong" degree for the size of the number. GNFS difficulty roughly doubles every 5.5 digits. This thread has some more detailed mathematical explanations if you're interested. These are very much not ELI5, though maybe some are ELI18. Last fiddled with by charybdis on 2021-11-05 at 02:48
 2021-11-05, 02:58 #981 ThomRuley     May 2003 3×97 Posts Thanks. ELI18 may have to do.
 2021-11-09, 15:29 #982 ThomRuley     May 2003 3×97 Posts I decided to start working through the t2200 file for now. I finished (4704006414025977517737010367874433^7 -1)/(4704006414025977517737010367874433-1) yesterday Wrapping up (164840458433247831545380402768066382125607140850350063^5-1)/(164840458433247831545380402768066382125607140850350063-1) in about an hour If no one is working on it, (55861871484788877230142332670582003900341141786568666929551231846127870452424196830136166348296553690709766995700853633762202956955812747696231496996184865884037^1-1)/(55861871484788877230142332670582003900341141786568666929551231846127870452424196830136166348296553690709766995700853633762202956955812747696231496996184865884037-1) is next
 2021-11-17, 03:14 #983 ThomRuley     May 2003 4438 Posts Anybody working on (14275963305110219876269575868443201054709206526952694749229865347248013990032567493253^3-1)/(14275963305110219876269575868443201054709206526952694749229865347248013990032567493253-1)?
 2021-11-17, 09:35 #984 Brownfox     Dec 2017 10010002 Posts Working on 865901231558393743256873067633607^7-1 from the t2200 file. Does anyone have an eta on the mwrb2200 file? Last fiddled with by Brownfox on 2021-11-17 at 09:37 Reason: Copy paste error
 2021-11-18, 01:25 #985 ThomRuley     May 2003 3×97 Posts Any idea how we could get composites from the mwrb2100 file into the NFS@home project? Looks like they are mostly doing Cunningham numbers.
 2021-11-18, 05:17 #986 VBCurtis     "Curtis" Feb 2005 Riverside, CA 25·7·23 Posts Have you looked at the nfs@home subforum? ECM-pretest a candidate to at least the usual depth, test-sieve on the appropriate siever to determine Q-range, and post the job. The size and parameter restrictions for each queue are posted at the top of each job thread. 14e jobs are discouraged, as those can be done by individuals. We could use a few jobs on 15e-small and 15e queues, as the supply of fully ECM'ed jobs has been thin this fall. The 16e queue has plenty of supply, so jobs bigger than SNFS280/GNFS190 should maybe not be a priority just now.
 2021-11-20, 04:05 #987 ThomRuley     May 2003 1001000112 Posts Running ECM on 4125099241766702497828754545051526255358191877622953835963928559535525025242323612793829455850360980990732729168762413572946726127^3-1 from the t2200 file Last fiddled with by ThomRuley on 2021-11-20 at 04:05
 2021-11-25, 00:54 #988 ThomRuley     May 2003 3×97 Posts NFS on 360980990732729168762413572946726127^3-1
 2021-12-09, 07:46 #989 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 2·52·7·17 Posts Factored 27395631932423126416280468114484772969719691^5-1 = 189154696133147386176672097383548374232144932815203800132031*64907774502078970767431379988664735283415090789411354660519660702380962469214511919669812448020431 This was a top 5 hit composite for eliminating 127. Should have been factored long ago if it wasn't a quartic.
 2021-12-09, 14:38 #990 ThomRuley     May 2003 3×97 Posts Doing NFS on 1081672954980883937823519435159294073908053165384014957017126080441634206366526402801546970966516852463114309334417201930703365066107885524444981307329120297949290506001623023282214841^2-1

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy GPU Computing 1 2017-05-17 20:22 Mark Rose GPU Computing 52 2016-07-02 12:11 firejuggler GPU Computing 12 2016-02-23 06:55 Elhueno Homework Help 5 2008-06-12 16:37 jchein1 Factoring 30 2005-05-30 14:43

All times are UTC. The time now is 22:18.

Sun Jan 16 22:18:20 UTC 2022 up 177 days, 16:47, 0 users, load averages: 0.62, 1.02, 1.08