mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-11-05, 02:47   #980
charybdis
 
charybdis's Avatar
 
Apr 2020

10418 Posts
Default

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
charybdis is offline   Reply With Quote
Old 2021-11-05, 02:58   #981
ThomRuley
 
ThomRuley's Avatar
 
May 2003

10616 Posts
Default

Thanks. ELI18 may have to do.
ThomRuley is offline   Reply With Quote
Old 2021-11-09, 15:29   #982
ThomRuley
 
ThomRuley's Avatar
 
May 2003

4068 Posts
Default

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 is offline   Reply With Quote
Old 2021-11-17, 03:14   #983
ThomRuley
 
ThomRuley's Avatar
 
May 2003

2·131 Posts
Default

Anybody working on (14275963305110219876269575868443201054709206526952694749229865347248013990032567493253^3-1)/(14275963305110219876269575868443201054709206526952694749229865347248013990032567493253-1)?
ThomRuley is offline   Reply With Quote
Old 2021-11-17, 09:35   #984
Brownfox
 
Brownfox's Avatar
 
Dec 2017

71 Posts
Default

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
Brownfox is offline   Reply With Quote
Old 2021-11-18, 01:25   #985
ThomRuley
 
ThomRuley's Avatar
 
May 2003

2×131 Posts
Default

Any idea how we could get composites from the mwrb2100 file into the NFS@home project? Looks like they are mostly doing Cunningham numbers.
ThomRuley is offline   Reply With Quote
Old 2021-11-18, 05:17   #986
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

117138 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2021-11-20, 04:05   #987
ThomRuley
 
ThomRuley's Avatar
 
May 2003

2·131 Posts
Default

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

Last fiddled with by ThomRuley on 2021-11-20 at 04:05
ThomRuley is offline   Reply With Quote
Old 2021-11-25, 00:54   #988
ThomRuley
 
ThomRuley's Avatar
 
May 2003

10616 Posts
Default

NFS on 360980990732729168762413572946726127^3-1
ThomRuley is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 05:29.


Tue Nov 30 05:29:15 UTC 2021 up 129 days, 23:58, 0 users, load averages: 0.74, 1.07, 1.28

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.