View Single Post
Old 2016-04-13, 22:29   #1
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

32·227 Posts
Default Fix for homogeneous cunningham polynomials

There's a bug when generating polynomials for homogeneous cunninghams when the exponent is 3 mod 9. The output and patch are below.

Code:
[run2]$ ./yafu "snfs(5^363+2^363,(5^363+2^363)/6519688039274771132541586808949835731598026808260954407545663352272665467834944837697544304318703178091)" -v


04/13/16 15:00:05 v1.34.5 @ kepler.fullerton.edu, System/Build Info: 
Using GMP-ECM, Powered by GMP
detected       Intel(R) Xeon(R) CPU E5-2640 v2 @ 2.00GHz
detected L1 = 32768 bytes, L2 = 20971520 bytes, CL = 64 bytes
measured cpu frequency ~= 1999.996480
using 1 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> nfs: checking for job file - no job file found
nfs: checking for poly file - no poly file found
nfs: commencing nfs on c254: 53224498000101883998875671453091360603082459178883520011563126148080110359319401703562961046591961274351135564659444067264932271199483366269899657782473819937788934964381898123727236116280879626600144692606058555100496276291602987078318839032955554307933
nfs: searching for brent special forms...
nfs: searching for homogeneous cunningham special forms...
nfs: input divides 5^363 + 2^363
nfs: degree 4 difficulty = 169.15, degree 6 difficulty = 169.15
nfs: choosing degree 6
Error: M=4300025188223594595309656442600295024216898130994737385523477749109759023110557848680345052942551609934208827807812699535729803021130612686745818987096 is not a root of f(x) % N
n = 8163657168790303629576150586545483327946777039370429262487058053450469093312703415470092044482556899348692284734040373484919496043553620202252773170263
f(x) = + 25*x^6 + 0*x^5 + 0*x^4 - -10*x^3 + 0*x^2 + 0*x^1 + 1*x^0 
Remainder is 8163657168790303629576150586545483327946777039370429262487058053450469093312703415470092044482556899348692284734040373484919496043553620202252773170260

nfs: no snfs polynomial with small coefficients found
nfs: failed to find snfs polynomial!
Code:
--- snfs.c.orig 2016-04-13 15:17:50.054719451 -0700
+++ snfs.c      2016-04-13 15:21:00.308381619 -0700
@@ -1309,7 +1309,8 @@
             mpz_set_si(polys->c[3], -poly->coeff2);
             mpz_mul(polys->c[3], polys->c[3], poly->base1);
             mpz_mul(polys->c[3], polys->c[3], poly->base2);
-            mpz_set_ui(polys->c[0], 1);
+            mpz_set(polys->c[0], poly->base2);
+            mpz_mul(polys->c[0], polys->c[0], poly->base2);
 
             polys->poly->skew = pow(mpz_get_d(poly->base1) / mpz_get_d(poly->base2), -1. / 3.);
             polys->difficulty = log10(mpz_get_d(m)) * (6. * k + 2);
frmky is offline   Reply With Quote