Pascal's OPN roadblock files - Page 90

charybdis · 2021-11-05, 02:47

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.

ThomRuley · 2021-11-05, 02:58

Thanks. ELI18 may have to do.

ThomRuley · 2021-11-09, 15:29

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

ThomRuley · 2021-11-17, 03:14

Anybody working on (14275963305110219876269575868443201054709206526952694749229865347248013990032567493253^3-1)/(14275963305110219876269575868443201054709206526952694749229865347248013990032567493253-1)?

Brownfox · 2021-11-17, 09:35

Working on 865901231558393743256873067633607^7-1 from the t2200 file.

Does anyone have an eta on the mwrb2200 file?

ThomRuley · 2021-11-18, 01:25

Any idea how we could get composites from the mwrb2100 file into the NFS@home project? Looks like they are mostly doing Cunningham numbers.

VBCurtis · 2021-11-18, 05:17

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.

ThomRuley · 2021-11-20, 04:05

Running ECM on 4125099241766702497828754545051526255358191877622953835963928559535525025242323612793829455850360980990732729168762413572946726127^3-1
from the t2200 file

ThomRuley · 2021-11-25, 00:54

NFS on 360980990732729168762413572946726127^3-1

henryzz · 2021-12-09, 07:46

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.

ThomRuley · 2021-12-09, 14:38

Doing NFS on
1081672954980883937823519435159294073908053165384014957017126080441634206366526402801546970966516852463114309334417201930703365066107885524444981307329120297949290506001623023282214841^2-1

2021-11-05, 02:47	#980
charybdis Apr 2020 2·3³·13 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 31479823396757x^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.69d 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-17, 09:35	#984
Brownfox Dec 2017 73 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-20, 04:05	#987
ThomRuley May 2003 291₁₀ Posts	Running ECM on 4125099241766702497828754545051526255358191877622953835963928559535525025242323612793829455850360980990732729168762413572946726127^3-1 from the t2200 file Last fiddled with by ThomRuley on 2021-11-20 at 04:05

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Passive Pascal	Xyzzy	GPU Computing	1	2017-05-17 20:22
Tesla P100 — 5.4 DP TeraFLOPS — Pascal	Mark Rose	GPU Computing	52	2016-07-02 12:11
Nvidia Pascal, a third of DP	firejuggler	GPU Computing	12	2016-02-23 06:55
Calculating perfect numbers in Pascal	Elhueno	Homework Help	5	2008-06-12 16:37
Factorization attempt to a c163 - a new Odd Perfect Number roadblock	jchein1	Factoring	30	2005-05-30 14:43

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 123₁₆ 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 3·97 Posts	Anybody working on (14275963305110219876269575868443201054709206526952694749229865347248013990032567493253^3-1)/(14275963305110219876269575868443201054709206526952694749229865347248013990032567493253-1)?

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 5,279 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-25, 00:54	#988
ThomRuley May 2003 291₁₀ Posts	NFS on 360980990732729168762413572946726127^3-1

2021-12-09, 07:46	#989
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 13540₈ 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