20210601, 17:44  #1 
"Ben"
Feb 2007
2·1,789 Posts 
Direct snfs forms
Just added detection of "direct" snfs form inputs. That is, inputs where you can pretty much read off the polynomial directly from the input form. These were not typically captured previously. So this saves a couple steps manually making such job files.
Examples: Code:
./yafu "snfs(13*2^4009*2^320+7*2^240+19*2^1604*2^801,32717555830082386925317613091345787199194165241204621073526723676886675820072245521*19605264019130155507)" v threads 16 plan normal YAFU Version 2.02 Built with Intel Compiler 1910 Using GMPECM 7.0.4, Powered by GMP 6.2.0 Detected Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz Detected L1 = 32768 bytes, L2 = 28835840 bytes, CL = 64 bytes Using 1 random witness for RabinMiller PRP checks Cached 664579 primes; max prime is 9999991 =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== >> nfs: checking for job file  job file found, testing for matching input nfs: number in job file does not match input nfs: checking for poly file  no poly file found nfs: commencing nfs on c122: 33569248415129811665526930012155831078095433751596918070282988900994800986617737545708867025812396101514741187342002814975 nfs: searching for brent special forms... nfs: searching for homogeneous cunningham special forms... nfs: searching for XYYXF special forms... nfs: searching for direct special forms... nfs: input divides +13*(16^20)^5 9*(16^20)^4 +7*(16^20)^3 +19*(16^20)^2 4*(16^20)^1 1 gen: ======================================================== gen: considering the following polynomials: gen: ======================================================== n: 641436320109396268259430619008759807131526101843354640317753393883989482393993802566301352791414234147 # m=16^20, difficulty: 121.53, anorm: 1.12e+35, rnorm: 9.05e+30 # size = 1.402e08, alpha = 1.512, combined = 1.887e08, rroots = 3 type: snfs size: 121 skew: 0.5987 c5: 13 c4: 9 c3: 7 c2: 19 c1: 4 c0: 1 Y1: 1 Y0: 1208925819614629174706176 m: 1208925819614629174706176 nfs: found 1 polynomial nfs: guessing snfs difficulty 121 is roughly equal to gnfs difficulty 98 nfs: creating ggnfs job parameters for input of size 98 Code:
./yafu "factor(9999999999999999999999334000000000000000000000028899999999999999999999999829999999999999999999999999)" v threads 1 noecm YAFU Version 2.02 Built with Intel Compiler 1910 Using GMPECM 7.0.4, Powered by GMP 6.2.0 Detected Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz Detected L1 = 32768 bytes, L2 = 28835840 bytes, CL = 64 bytes Using 1 random witness for RabinMiller PRP checks Cached 664579 primes; max prime is 9999991 =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== >> fac: check tune params contained invalid parameter(s), ignoring tune info. fac: factoring 9999999999999999999999334000000000000000000000028899999999999999999999999829999999999999999999999999 fac: using pretesting plan: noecm fac: check tune params contained invalid parameter(s), ignoring tune info. fac: no tune info: using qs/gnfs crossover of 100 digits fac: no tune info: using qs/snfs crossover of 75 digits div: primes less than 10000 fmt: 1000000 iterations rho: x^2 + 3, starting 1000 iterations on C100 rho: found prp7 factor = 3543469 rho: x^2 + 3, starting 1000 iterations on C94 rho: found prp8 factor = 45580291 rho: x^2 + 3, starting 1000 iterations on C86 rho: x^2 + 2, starting 1000 iterations on C86 rho: x^2 + 1, starting 1000 iterations on C86 fac: check tune params contained invalid parameter(s), ignoring tune info. nfs: searching for brent special forms... nfs: searching for homogeneous cunningham special forms... nfs: searching for XYYXF special forms... nfs: searching for direct special forms... nfs: input divides +1*(10^25)^4 666*(10^25)^3 +289*(10^25)^2 17*(10^25)^1 1 pm1: starting B1 = 150K, B2 = gmpecm default on C86 pm1: Process took 0.0584 seconds. fac: check tune params contained invalid parameter(s), ignoring tune info. nfs: checking for job file  no job file found nfs: checking for poly file  no poly file found nfs: commencing nfs on c86: 61914770686800656125505930979997766631694057899870434433829533842136976634123771991881 nfs: searching for brent special forms... nfs: searching for homogeneous cunningham special forms... nfs: searching for XYYXF special forms... nfs: searching for direct special forms... nfs: input divides +1*(10^25)^4 666*(10^25)^3 +289*(10^25)^2 17*(10^25)^1 1 gen: ======================================================== gen: considering the following polynomials: gen: ======================================================== n: 61914770686800656125505930979997766631694057899870434433829533842136976634123771991881 # m=10^25, difficulty: 100.00, anorm: 2.77e+28, rnorm: 2.90e+31 # size = 5.593e11, alpha = 1.813, combined = 2.099e07, rroots = 4 type: snfs size: 100 skew: 1.0000 c4: 1 c3: 666 c2: 289 c1: 17 c0: 1 Y1: 1 Y0: 10000000000000000000000000 m: 10000000000000000000000000 nfs: found 1 polynomial nfs: guessing snfs difficulty 100 is roughly equal to gnfs difficulty 86 nfs: creating ggnfs job parameters for input of size 86 If you find problems, let me know! 
20210601, 20:27  #2  
"Robert Gerbicz"
Oct 2005
Hungary
2×3^{2}×83 Posts 
Quote:
Code:
b=4241; x=b^15; N=(902367*x^52361274*x^4+32179627*x^345454704*x^2+545121457701*x+16647954129297)/36417887568782; here: N=2845698521590897599731052163780756835626547090174423156196551512719279710975995403760676077231555545205129814718057858125077817757698456020942647063040810983317817174888693652939639675270545305480797905567918514779509784793290767821115821962754061292368813910491877; 

20210601, 21:06  #3  
"Ben"
Feb 2007
2·1,789 Posts 
Quote:
No it will not find the form if you input the number N. But the divisor won't help the snfs factorization anyway. Using the snfs function where you have a known cofactor works, assuming the form has coefficients and a common root within the searched range. Example: Code:
./yafu v YAFU Version 2.02 Built with Intel Compiler 1910 Using GMPECM 7.0.4, Powered by GMP 6.2.0 Detected Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz Detected L1 = 32768 bytes, L2 = 28835840 bytes, CL = 64 bytes Using 1 random witness for RabinMiller PRP checks Cached 664579 primes; max prime is 9999991 =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== >> b=19; >> p=47; >> x=b^p; >> n=9*x^5+23*x^4+323*x^3454*x^2+5451*x+1665; >> d=3*192906267301850772899297; >> n%(d) ans = 0 >> nd=n/d; >> snfs(n,nd) nfs: checking for job file  no job file found nfs: checking for poly file  no poly file found nfs: commencing nfs on c302: 28929353833910349156154010698815713226803099925433685649613461283715976229514304309575976836924796025232885142965411814653873497056380016793518642408444034056322709226413962353940514759592094942319707873354504562148132632691169933791644033904282017352009446026164216272932659599612974636379289104929191 nfs: searching for brent special forms... nfs: searching for homogeneous cunningham special forms... nfs: searching for XYYXF special forms... nfs: searching for direct special forms... nfs: input divides +9*(19^47)^5 +23*(19^47)^4 +323*(19^47)^3 454*(19^47)^2 +5451*(19^47)^1 +1665 gen: ======================================================== gen: considering the following polynomials: gen: ======================================================== n: 49988619237277966190234329257259140440899622151400697320093692058616152260169527330871763353144537223313695441988961818261571160552292078938444979436043123040202077806351054467182057184865822904896007261470044455421662350324169146879997859604586714760643825714163652640798304301 # m=19^47, difficulty: 301.46, anorm: 1.15e+37, rnorm: 4.34e+66 # size = 6.472e21, alpha = 0.154, combined = 3.061e16, rroots = 1 type: snfs size: 301 skew: 2.8408 c5: 9 c4: 23 c3: 323 c2: 454 c1: 5451 c0: 1665 Y1: 1 Y0: 1263046223881900339210386091365390321169375020004522243688539 m: 1263046223881900339210386091365390321169375020004522243688539 nfs: found 1 polynomial nfs: guessing snfs difficulty 301 is roughly equal to gnfs difficulty 198 nfs: creating ggnfs job parameters for input of size 198 Last fiddled with by bsquared on 20210601 at 21:34 Reason: example using snfs and cofactor  snfs command in bold 

20210601, 21:41  #4  
"Robert Gerbicz"
Oct 2005
Hungary
10111010110_{2} Posts 
Quote:
Let me work out, but it is possible to find the above polynom. 

20210602, 02:07  #5 
"Robert Gerbicz"
Oct 2005
Hungary
1494_{10} Posts 
OK, here it is a solution, thought that it is a much easier code.
In a few seconds: Code:
gerbicz@gerbiczMS7972:~/gmp6.1.2$ ./f 2845698521590897599731052163780756835626547090174423156196551512719279710975995403760676077231555545205129814718057858125077817757698456020942647063040810983317817174888693652939639675270545305480797905567918514779509784793290767821115821962754061292368813910491877 ***************************************************** x=4241^25;deg=3;poly=(902367*x^34444563441915093212449207534996982070906874*x^2+114010921263991489401601995275917169592405105128353302198129369378579755075113723*x^1+1407723512456934353557265154597492792077356943043282604751822138598*x^0)/36417887568782 ***************************************************** x=4241^26;deg=3;poly=(902367*x^318849393557161910313997089155922200962716052634*x^2+2050609664738773311687855016794263561579735205652077889953032886122055139741156506089563*x^1+107379698900697559380092466655657505709885900532636286791653730679329879671558*x^0)/2777918935878326969093422 ***************************************************** x=4241^15;deg=5;poly=(902367*x^52361274*x^4+32179627*x^345454704*x^2+545121457701*x^1+16647954129297*x^0)/36417887568782 done the search. The idea was that you can find these polynoms with the trick: N/b^(e*k) is so close to r=coeff[k]/d that you can discover it with continued fractions, one serious bottleneck was that g=gcd(coeff[k],d)>1 is possible, so even if you know r you still don't know coeff[k] and d. One neat example for this is your N: Code:
? x=19^47;deg=5;poly=(9*x^5+23*x^4+323*x^3454*x^2+5451*x^1+1665*x^0)/578718801905552318697891 %91 = 49988619237277966190234329257259140440899622151400697320093692058616152260169527330871763353144537223313695441988961818261571160552292078938444979436043123040202077806351054467182057184865822904896007261470044455421662350324169146879997859604586714760643825714163652640798304301 ? ? gcd(578718801905552318697891,9) %92 = 3 
20210602, 13:37  #6  
"Ben"
Feb 2007
2×1,789 Posts 
Quote:
Now I need to figure out how/when to use this in yafu (assuming you are ok with that, of course). The SNFS formdetection code runs for every input, most of which, across all the users of yafu, aren't even SNFSable. So I need to balance runtime with usefulness. The rest of the detection code (XYYX, a*b^n + c, a^n+b^n) all runs in about 100 milliseconds. Fortunately I think I can reduce several of the constants in your code to achieve this since SNFS is primarily of benefit with pretty small coefficients and degree between 4 and 6. I could probably also make an option to more fully search all snfs spaces if desired. Anyway, fantastic code, thanks again. 

20210602, 20:59  #7 
"Robert Gerbicz"
Oct 2005
Hungary
2726_{8} Posts 

20210602, 21:12  #8 
"Robert Gerbicz"
Oct 2005
Hungary
2×3^{2}×83 Posts 
A small bug, on line=76 we need:
Code:
while(mpz_sgn(S)!=0){ [in most cases we won't reach S=0 so the full continued fraction expansion because we exit much earlier]. 
20210623, 20:32  #9  
"Max"
Jun 2016
Toronto
2×3×151 Posts 
skew and spin options
Quote:
Code:
Line 1 : {'c4': '1', 'c3': '666', 'c2': '289', 'c1': '17', 'c0': '1', 'Y1': '1', 'Y0': '10000000000000000000000000'} n: 61914770686800656125505930979997766631694057899870434433829533842136976634123771991881 # e = 2.13041438e07 skew: 0.48272 type: gnfs c4: 1 c3: 666 c2: 289 c1: 17 c0: 1 Y1: 1 Y0: 10000000000000000000000000 Line 2 : {'c4': '1', 'c3': '21', 'c2': '232', 'c1': '143', 'c0': '394', 'Y1': '10000000000000000000000000', 'Y0': '9999999999999999999999999'} n: 61914770686800656125505930979997766631694057899870434433829533842136976634123771991881 # e = 2.14939383e07 skew: 2.35224 type: gnfs c4: 1 c3: 21 c2: 232 c1: 143 c0: 394 Y1: 10000000000000000000000000 Y0: 9999999999999999999999999 

20210625, 12:51  #10 
Aug 2020
79*6581e4;3*2539e3
18F_{16} Posts 
Very interesting feature, thanks.

20210929, 15:18  #11 
"Bo Chen"
Oct 2005
Wuhan,China
170_{10} Posts 
I give a small test to the number 10,1050L, but it seems like it could not recognize the form.
Code:
YAFU Version 2.07 Built with Microsoft Visual Studio 1928 Using GMPECM 7.0.4, Powered by MPIR 3.0.0 Detected Intel(R) Core(TM) i58265U CPU @ 1.60GHz Detected L1 = 32768 bytes, L2 = 6291456 bytes, CL = 64 bytes Using 1 random witness for RabinMiller PRP checks Cached 664579 primes; max prime is 9999991 =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== >> >> h=2*k1 unrecognized variable or function 'k' >> k=53 k = 53 >> h=2*k1 h = 105 >> A=10^(4*h)+5*10^(3*h)+7*10^(2*h)+5*10^h+1 A = 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 >> B=10^k*(10^(3*h) + 2*10^(2*h) + 2*10^h+1) B = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000 >> snfs(AB,62022219117754166952341475031298380517640406686430429600268991894589260116998200488692212488451811695692955587839332409016867970248948210018283201861849771124126045467738250852975190765346732381163112962249769016301) nfs: checking for job file  no job file found nfs: checking for poly file  no poly file found nfs: commencing nfs on c368: 99999999999999999999999999999999999999999999999999999000000000000000000000000000000000000000000000000000199999999999999999999999999999999999999999999999999998000000000000000000000000000000000000000000000000000199999999999999999999999999999999999999999999999999998000000000000000000000000000000000000000000000000000099999999999999999999999999999999999999999999999999999 nfs: searching for brent special forms... nfs: searching for homogeneous cunningham special forms... nfs: searching for XYYXF special forms... nfs: searching for direct special forms... nfs: snfs form detection took 0.109345 seconds nfs: couldn't find special form nfs: failed to find snfs polynomial! Code:
c8: 1 c7: 10 c6: 30 c5: 600 c4: 1200 c3: 7000 c2: 32000 c1: 40000 c0: 10000 Y1: 100000000000000000 Y0: 100000000000000000000000000000000001 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Exponents of particular forms  kriesel  kriesel  7  20210122 16:45 
Direct Graphics Memory Access  Xyzzy  GPU Computing  0  20201211 03:11 
Representation by quadratic forms  Raman  Math  0  20130104 00:29 
use direct IP instead of mersenne.org?  ixfd64  Software  7  20111126 13:40 
Minimum primes of various forms database?  jasong  Information & Answers  1  20071101 01:58 