Direct snfs forms

[bsquared]

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:

./yafu "snfs(13*2^400-9*2^320+7*2^240+19*2^160-4*2^80-1,32717555830082386925317613091345787199194165241204621073526723676886675820072245521*19605264019130155507)" -v -threads 16 -plan normal


YAFU Version 2.02
Built with Intel Compiler 1910
Using GMP-ECM 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 Rabin-Miller 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.402e-08, alpha = 1.512, combined = 1.887e-08, 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

./yafu "factor(9999999999999999999999334000000000000000000000028899999999999999999999999829999999999999999999999999)" -v -threads 1 -noecm


YAFU Version 2.02
Built with Intel Compiler 1910
Using GMP-ECM 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 Rabin-Miller 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 = gmp-ecm 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.593e-11, alpha = 1.813, combined = 2.099e-07, 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

For now, it looks for all m=b^p, b=2..19, p=2..(75*log(10)/log(b)), with abs(coefficients) < 10000 and at least degree 4.

If you find problems, let me know!

[R. Gerbicz]

Originally Posted by bsquared

Just added detection of "direct" snfs form inputs.
...
For now, it looks for all m=b^p, b=2..19, p=2..(75*log(10)/log(b)), with abs(coefficients) < 10000 and at least degree 4.

What about the N=n/d numbers? For example:

b=4241;
x=b^15;
N=(902367*x^5-2361274*x^4+32179627*x^3-45454704*x^2+545121457701*x+16647954129297)/36417887568782;
here:
N=2845698521590897599731052163780756835626547090174423156196551512719279710975995403760676077231555545205129814718057858125077817757698456020942647063040810983317817174888693652939639675270545305480797905567918514779509784793290767821115821962754061292368813910491877;

factord.com also can't find the polynom for N.

[bsquared]

Originally Posted by R. Gerbicz

What about the N=n/d numbers? For example:

b=4241;
x=b^15;
N=(902367*x^5-2361274*x^4+32179627*x^3-45454704*x^2+545121457701*x+16647954129297)/36417887568782;
here:
N=2845698521590897599731052163780756835626547090174423156196551512719279710975995403760676077231555545205129814718057858125077817757698456020942647063040810983317817174888693652939639675270545305480797905567918514779509784793290767821115821962754061292368813910491877;

factord.com also can't find the polynom for N.

[edit] Will have to check on if the divisors matter. But anyway, in your example b and the coefficient values are outside the bounds I check.

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:

./yafu -v


YAFU Version 2.02
Built with Intel Compiler 1910
Using GMP-ECM 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 Rabin-Miller 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^3-454*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.472e-21, alpha = 0.154, combined = 3.061e-16, 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

[R. Gerbicz]

Originally Posted by bsquared

[edit] Will have to check on if the divisors matter. But anyway, in your example b and the coefficient values are outside the bounds I check.

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.

Right, that divisor doesn't speed up the factorisation, but here the problem is how to find that polynom if the user gives N=n/d and not the better form n.
Let me work out, but it is possible to find the above polynom.

[R. Gerbicz]

OK, here it is a solution, thought that it is a much easier code.
In a few seconds:

gerbicz@gerbicz-MS-7972:~/gmp-6.1.2$ ./f
2845698521590897599731052163780756835626547090174423156196551512719279710975995403760676077231555545205129814718057858125077817757698456020942647063040810983317817174888693652939639675270545305480797905567918514779509784793290767821115821962754061292368813910491877
*****************************************************
x=4241^25;deg=3;poly=(902367*x^3-4444563441915093212449207534996982070906874*x^2+114010921263991489401601995275917169592405105128353302198129369378579755075113723*x^1+1407723512456934353557265154597492792077356943043282604751822138598*x^0)/36417887568782

*****************************************************
x=4241^26;deg=3;poly=(902367*x^3-18849393557161910313997089155922200962716052634*x^2+2050609664738773311687855016794263561579735205652077889953032886122055139741156506089563*x^1+107379698900697559380092466655657505709885900532636286791653730679329879671558*x^0)/2777918935878326969093422

*****************************************************
x=4241^15;deg=5;poly=(902367*x^5-2361274*x^4+32179627*x^3-45454704*x^2+545121457701*x^1+16647954129297*x^0)/36417887568782

done the search.

OK, that deg=3 isn't that interesting, but due to the much larger allowed coefficients it could find easily that also [you can derive it from the deg=5 solution, but ofcourse the code hasn't used it].
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:

? x=19^47;deg=5;poly=(9*x^5+23*x^4+323*x^3-454*x^2+5451*x^1+1665*x^0)/578718801905552318697891
%91 = 49988619237277966190234329257259140440899622151400697320093692058616152260169527330871763353144537223313695441988961818261571160552292078938444979436043123040202077806351054467182057184865822904896007261470044455421662350324169146879997859604586714760643825714163652640798304301
? 
? gcd(578718801905552318697891,9)
%92 = 3

my code found this polynom also.

[bsquared]

Originally Posted by R. Gerbicz

OK, here it is a solution, thought that it is a much easier code.
In a few seconds:

gerbicz@gerbicz-MS-7972:~/gmp-6.1.2$ ./f
2845698521590897599731052163780756835626547090174423156196551512719279710975995403760676077231555545205129814718057858125077817757698456020942647063040810983317817174888693652939639675270545305480797905567918514779509784793290767821115821962754061292368813910491877
*****************************************************
x=4241^25;deg=3;poly=(902367*x^3-4444563441915093212449207534996982070906874*x^2+114010921263991489401601995275917169592405105128353302198129369378579755075113723*x^1+1407723512456934353557265154597492792077356943043282604751822138598*x^0)/36417887568782

*****************************************************
x=4241^26;deg=3;poly=(902367*x^3-18849393557161910313997089155922200962716052634*x^2+2050609664738773311687855016794263561579735205652077889953032886122055139741156506089563*x^1+107379698900697559380092466655657505709885900532636286791653730679329879671558*x^0)/2777918935878326969093422

*****************************************************
x=4241^15;deg=5;poly=(902367*x^5-2361274*x^4+32179627*x^3-45454704*x^2+545121457701*x^1+16647954129297*x^0)/36417887568782

done the search.

OK, that deg=3 isn't that interesting, but due to the much larger allowed coefficients it could find easily that also [you can derive it from the deg=5 solution, but ofcourse the code hasn't used it].
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:

? x=19^47;deg=5;poly=(9*x^5+23*x^4+323*x^3-454*x^2+5451*x^1+1665*x^0)/578718801905552318697891
%91 = 49988619237277966190234329257259140440899622151400697320093692058616152260169527330871763353144537223313695441988961818261571160552292078938444979436043123040202077806351054467182057184865822904896007261470044455421662350324169146879997859604586714760643825714163652640798304301
? 
? gcd(578718801905552318697891,9)
%92 = 3

my code found this polynom also.

This is very cool, thank you!

Now I need to figure out how/when to use this in yafu (assuming you are ok with that, of course). The SNFS form-detection code runs for every input, most of which, across all the users of yafu, aren't even SNFSable. So I need to balance run-time 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.

[R. Gerbicz]

Originally Posted by bsquared

This is very cool, thank you!

Now I need to figure out how/when to use this in yafu (assuming you are ok with that, of course).

Yes, you can use/modify etc. the code.

[R. Gerbicz]

A small bug, on line=76 we need:

while(mpz_sgn(S)!=0){

since in the next line we'll divide by S
[in most cases we won't reach S=0 so the full continued fraction expansion because we exit much earlier].

[Max0526]

Originally Posted by bsquared

n: 61914770686800656125505930979997766631694057899870434433829533842136976634123771991881
# m=10^25, difficulty: 100.00, anorm: -2.77e+28, rnorm: 2.90e+31
# size = 5.593e-11, alpha = 1.813, combined = 2.099e-07, 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

For now, it looks for all m=b^p, b=2..19, p=2..(75*log(10)/log(b)), with abs(coefficients) < 10000 and at least degree 4.

If you find problems, let me know!

Tiny improvements (2.4%) if we consider the skew and the spin, and we are not afraid to factor a negative number instead of a positive:

Line 1 : {'c4': '1', 'c3': '-666', 'c2': '289', 'c1': '-17', 'c0': '-1', 'Y1': '-1', 'Y0': '10000000000000000000000000'}

n: 61914770686800656125505930979997766631694057899870434433829533842136976634123771991881
# e = 2.13041438e-07
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.14939383e-07
skew: 2.35224
type: gnfs
c4: 1
c3: 21
c2: -232
c1: 143
c0: 394
Y1: 10000000000000000000000000
Y0: 9999999999999999999999999

[bur]

Very interesting feature, thanks.

[wreck]

I give a small test to the number 10,1050L, but it seems like it could not recognize the form.

YAFU Version 2.07
Built with Microsoft Visual Studio 1928
Using GMP-ECM 7.0.4, Powered by MPIR 3.0.0
Detected Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
Detected L1 = 32768 bytes, L2 = 6291456 bytes, CL = 64 bytes
Using 1 random witness for Rabin-Miller 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*k-1

unrecognized variable or function 'k'
>> k=53


k = 53

>> h=2*k-1


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(A-B,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!

If possible, the following polynomial should be generated.

c8: 1
c7: 10
c6: -30
c5: -600
c4: -1200
c3: 7000
c2: 32000
c1: 40000
c0: 10000
Y1: 100000000000000000
Y0: -100000000000000000000000000000000001