SNFS factoring for neophytes?

[CRGreathouse]

I would like to factor a special-form number of 537 bits (which, as I understand, is quite doable with SNFS). I've run 1000 curves at B1 = 10^6 so the number seems to have no small factors. What is the easiest way to factor the number?

I have ggnfs, factmsieve.py, yafu, cado-nfs, etc. but I haven't used any of them for a long time and I'm not sure about syntax, and so forth. I'm even a little hazy on the right way to form a good poly but I'll manage I think.

[Batalov]

You could be done in 1 core-day with this SNFS.

The only trick is to build a polynomial. If it is of an obligatory ugly degree, then the fun starts, otherwise it should be a press play and forget. (I am not using the .py script, but .pl will do everything for you. You can leave limits and other parameters off the .poly file it will fill them in.) What is the general form of the number? PM if you want to keep it secret - I am reliable! ;-)

[bsquared]

Originally Posted by CRGreathouse

I would like to factor a special-form number of 537 bits (which, as I understand, is quite doable with SNFS). I've run 1000 curves at B1 = 10^6 so the number seems to have no small factors. What is the easiest way to factor the number?

I have ggnfs, factmsieve.py, yafu, cado-nfs, etc. but I haven't used any of them for a long time and I'm not sure about syntax, and so forth. I'm even a little hazy on the right way to form a good poly but I'll manage I think.

With yafu, if you can manage the polynomial then create a file like the following named, for example, snfs.job. These coefficients are obviously for a gnfs job in this example but you get the picture. If the snfs difficulty is greater than the decimal size of the number then you'll need to provide that as well.

n: 1279722376069429882674916783738587645201002727982137842794710157040169036868965821113429393
skew: 222414.44
type: snfs
size: NNN
c0: 1055355831583822265944960
c1: 110053741356789971224
c2: 155632423969639
c3: -2603265818
c4: 6120
Y0: -3802720129719817966849
Y1: 269924026471

Assuming you also have the ggnfs lattice siever executables, add the following line to a yafu.ini file (in the same directory as the yafu executable) assuming you haven't already:

ggnfs_dir=..\relative\path\to\your\ggnfs\directory

Then run (an X threaded job) with

yafu-x64.exe "nfs(the number)" -j snfs.job -threads X

and yafu will do the rest.

[CRGreathouse]

Originally Posted by Batalov

The only trick is to build a polynomial. If it is of an obligatory ugly degree, then the fun starts, otherwise it should be a press play and forget. (I am not using the .py script, but .pl will do everything for you. You can leave limits and other parameters off the .poly file it will fill them in.) What is the general form of the number? PM if you want to keep it secret - I am reliable! ;-)

Nothing secret, it's 84^84 - 83^83.

[Batalov]

Ok, let's try this. (I will use the compositeness of 84 to get a slightly better poly)

84^84 - 83^83 
2^168*21^84 - 83^83   
#let's multiply by 21 to get a degrees divisible by 5
2^168*21^85 - 21*83^83
8*(2^33*21^17)^5 - 21*83^3*(83^16)^5

So I guess, a t.poly like

n: 434052638949540480062453005064516466387568940273504907959561408643897140840774339200963955774565218462487550271836485609508404988323997310781276887844297986477749
skew: 17.2
type: snfs
size: 162
c5: 8
c0: -12007527
Y1: 5072820298953863752478356399681
Y0: -258058321049377015072521738780672

If you multiply by an extra 83^2, then c5 will be 8*83^2, c0 will be -21, Y1 will be 83x larger, and skew will be 83x smaller... Hmmm, could be faster or could be slower in sieving. Maybe a wash. E values estimated by msieve are almost identical: this is because the coefficients for the other poly are smaller but the resultant is ~4 digits larger.

[henryzz]

At what size for snfs does a quartic become optimal?

[Batalov]

For this size it could work, but some trial sieving is needed to decide. The poly would look like this:

n: 434052638949540480062453005064516466387568940273504907959561408643897140840774339200963955774565218462487550271836485609508404988323997310781276887844297986477749
skew: 0.331
type: snfs
size: 162
c4: 83
c0: -1
Y1: 19982045332214679702896737836182611234883
Y0: -25695969452033992329379379343259582070784

[CRGreathouse]

Originally Posted by bsquared

Then run (an X threaded job) with

yafu-x64.exe "nfs(the number)" -j snfs.job -threads X

and yafu will do the rest.

-j isn't working:

> ./yafu-linux64 "nfs(84^84-83^83)" -j snfs.job -threads 2
invalid option -j

I can't find any documentation, and the usual command line options --help, -?, etc. don't work.

[bsquared]

Sorry

-job

[CRGreathouse]

Well, that works. But neither of the above polys seem to work:

> yafu-x64 "nfs(84^84-83^83)" -job test.job


nfs: checking for data file
nfs: commencing nfs on c162: 434052638949540480062453005064516466387568940273504
90795956140864389714084077433920096395577456521846248755027183648560950840498832
3997310781276887844297986477749
nfs: continuing with sieving - could not determine last special q; using default
 startq
nfs: commencing rational side lattice sieving over range: 2500000 - 2660000
Error: m is not a common root of the polynomials:
c0: -1
c1: 0
c2: 0
c3: 0
c4: 83
Y0: 0
Y1: 19982045332214679702896737836182611234883
n: 43405263894954048006245300506451646638756894027350490795956140864389714084077
43392009639557745652184624875502718364856095084049883239973107812768878442979864
77749
Received signal -1... please wait

(this one on Windows rather than Linux)

[bsquared]

Y0 not set correctly?