Thread: YAFU 2.0
View Single Post
Old 2021-05-30, 12:53   #120
charybdis
 
charybdis's Avatar
 
Apr 2020

547 Posts
Default

There appears to be a bug in SNFS polynomial selection for (at least) the k*b^n+-1 and b^n+-k forms, for example:
Code:
$ yafu "snfs(1281979*2^520+1,615852095139018818180740532155742854813285752039357209617222174313731523072704248288595303399267379211703243385678043310396893565702501281889421988426549324889)"
Applying tune_info entry for LINUX64 - Intel(R) Core(TM) i5-8500 CPU @ 3.00GHz



YAFU Version 2.02
Built with GCC 9
Using GMP-ECM 7.0.5-dev, Powered by GMP 6.2.1
Detected Intel(R) Core(TM) i5-8500 CPU @ 3.00GHz
Detected L1 = 32768 bytes, L2 = 9437184 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) =======
=======               [email redacted]                  =======
=======     Type help at any time, or quit to quit      =======
===============================================================

>> nfs: checking for job file - no job file found
nfs: checking for poly file - no poly file found
nfs: commencing nfs on c163: 4400263219768289455901391102252782697640926698321207262715052435471611732354471854022013442787765424467619673990669619452785804526944371659099920107307694926331905
nfs: searching for brent special forms...
nfs: input divides 1281979*2^520 + 1
gen: ========================================================
gen: considering the following polynomials:
gen: ========================================================

Error: M=1361129467683753853853498429727072845824 is not a root of f(x) % N
n = 615852095139018818180740532155742854813285752039357209617222174313731523072704248288595303399267379211703243385678043310396893565702501281889421988426549324889
f(x) = + 1281979*x^4 + 0*x^3 + 0*x^2 + 0*x^1 - -1*x^0
Remainder is 615852095139018818180740532155742854813285752039357209617222174313731523072704248288595303399267379211703243385678043310396893565702501281889421988426549324887

Error: M=20282409603651670423947251286016 is not a root of f(x) % N
n = 615852095139018818180740532155742854813285752039357209617222174313731523072704248288595303399267379211703243385678043310396893565702501281889421988426549324889
f(x) = + 1281979*x^5 + 0*x^4 + 0*x^3 + 0*x^2 + 0*x^1 - -1*x^0
Remainder is 615852095139018818180740532155742854813285752039357209617222174313731523072704248288595303399267379211703243385678043310396893565702501281889421988426549324887

nfs: no snfs polynomial with small coefficients found
nfs: failed to find snfs polynomial!
Those remainders would suggest that YAFU is getting the sign of the constant term wrong. This is 2.02 but it doesn't look like anything relevant has changed in 2.03.

Also, I notice that the required ECM effort is not reduced when an SNFS special form is detected, necessitating a manual change to pretest_ratio.
charybdis is offline   Reply With Quote