Python Driver for GGNFS and MSIEVE

[RichD]

Originally Posted by Walter Nissen

There are some of these in the aforementioned
http://upforthecount.com/math/nnp.html
E.g. , letting np ( n ) = n^n + (n+1)^(n+1)

@Walter

A little off topic, but if you want to add more factors to your table you might want to check out factordb.com. As an example, take a look at this page compared to yours.

Note: The data base list the expression in reverse order.

[Walter Nissen]

The script at version 0.76 seems to permit integer division .
Among other deficiencies , this makes it impossible to run with a
calculated skew < 1 .
This line seems to work much better :

poly_p['skew'] = (abs( poly_p['coeff']['c0'] / float ( poly_p['coeff']['c'
                                                                   + str(poly_p['degree'])]) ) ** (1.0 / poly_p['degree']))

I believe due to functional binding this code performs the abs() before the exponentiation .
Some coders might prefer to make that explicit with another pair of ()'s .
If the skew is < .005 , the next line will display a zero instead of the correct value .

Disclaimer : I've never coded a line in python ; this is the first time I've ever munged one .
But it does seem to work .

Brian , many thanks to you and others for the useful facilities I've found here .

[Brian Gladman]

Originally Posted by Walter Nissen

The script at version 0.76 seems to permit integer division .
Among other deficiencies , this makes it impossible to run with a
calculated skew < 1 .
This line seems to work much better :

poly_p['skew'] = (abs( poly_p['coeff']['c0'] / float ( poly_p['coeff']['c'
                                                                   + str(poly_p['degree'])]) ) ** (1.0 / poly_p['degree']))

I believe due to functional binding this code performs the abs() before the exponentiation .
Some coders might prefer to make that explicit with another pair of ()'s .
If the skew is < .005 , the next line will display a zero instead of the correct value .

Disclaimer : I've never coded a line in python ; this is the first time I've ever munged one .
But it does seem to work .

Brian , many thanks to you and others for the useful facilities I've found here .

Thank you for your kind words. Unfortunately this line works correctly in Python 3.x but not in 2.x. Here is a version that should avoid this problem.

On another issue, with all the experience that is now available I have been hoping to be able to improve the sieving estimates in the script. I did look at this myself but it really needs to be done by someone who has a better understanding than I do of the parameters needed for estimates and how they contribute. I can change the script if anyone is willing to describe how such estimates should be computed.

[Walter Nissen]

Originally Posted by Brian Gladman

I have been hoping to be able to improve the sieving estimates in the script. I did look at this myself but it really needs to be done by someone who has a better understanding than I do of the parameters needed for estimates and how they contribute.

Thanks for the mysteriously improved script .
When I was experimenting with np ( 83 ) at SNFS difficulty 168 I tried
lpbr = 25 , 26 , and 27 , with lpba = lpbr .
Version 0.76 didn't react to the difference and chose
estimated minimum relations = 10e6 for all 3 .
I recreated this using the new v. 0.86 and attach the console logs
which show the 3 polys and , 3 times , the same e. m. r.
That can't possibly be right , can it ?

[Brian Gladman]

Originally Posted by Walter Nissen

Thanks for the mysteriously improved script .
When I was experimenting with np ( 83 ) at SNFS difficulty 168 I tried
lpbr = 25 , 26 , and 27 , with lpba = lpbr .
Version 0.76 didn't react to the difference and chose
estimated minimum relations = 10e6 for all 3 .
I recreated this using the new v. 0.86 and attach the console logs
which show the 3 polys and , 3 times , the same e. m. r.
That can't possibly be right , can it ?

The estimated relations appear to be a lost cause. A lot of people complain about them but nobody has come up with anything better :-(

[fivemack]

A straight 3.5 / 6.5 / 13.5 would be better than estimating 10.0 each time.

Looking at about eighty factorisations in each range done with my equivalent script:

In the 120-130 digit range, using 26-bit large primes, I need on average 120000*log(N)-8000000 relations, and at most 150000*log(N)-11500000 (log to base 10 in either case)

In the 110-115-digit range, using 25-bit large primes, 70000*log(N)-4200000 works on average and -3900000 works all the time.

Is that helpful?

[Walter Nissen]

Originally Posted by Brian Gladman

The estimated relations appear to be a lost cause. A lot of people complain about them but nobody has come up with anything better :-(

The best tuition I have at hand on this subject is :

Originally Posted by fivemack

how did I decide which siever and which lp values to use? I start by picking the lp value, and I thought this was quite a small number so I would try lp=25. That means that I'd expect to need about three million relations. I'm aiming for two relations per Q, so in that case I'd want 1.5 million Q, so Q=1.5M to 3M would be where to start. So try alim=rlim=3M and see what happens; using siever-size = half of lp is probably sensible, so try 12e and 13e, and run '-c 1000' to get a little sample

12e: total yield: 762, q=3001001 (0.02178 sec/rel)
13e: total yield: 1770, q=3001001 (0.02185 sec/rel)

So 13e is about the same speed per relation and gets twice as many relations per Q; also, alim=3 million is a bit low (because I'm only getting 1.77 relations per Q), so try alim=4 million and 2M-4M ought to get at least enough.

This process works for any polynomial you might want to try sieving.

How about if I'd wanted lp=26. I'd want six million relations so try Q=3M to 6M, so sample at 6M.

6M, 12e: total yield: 1794, q=6001013 (0.01514 sec/rel)
6M, 13e: total yield: 3948, q=6001013 (0.01341 sec/rel)

But remember that I need twice as many relations at lp=26 as at lp=25, and I'm only getting them 50% faster, so lp=25 is definitely better. lp=27 would be very wrong for this size of number.

Based on my extremely extensive experience with factMsieve.py ,
being exactly 2 runs to which I've paid very much attention
( I can't seem to find lpba in the console output nor the files
left behind by the earlier "point-and-shoot" runs
) , it seems that the sieve , 11e thru 16e , and the lpba should
be chosen by short tables of simple thresholds based on
log10 ( N ) ~= # of digits .
Assuming factMsieve.py isn't going to do any testing , the same
can be said for minimum relations based on the choice for lpba .

Originally Posted by fivemack

But remember that I need twice as many relations at lp=26 as at lp=25, and I'm only getting them 50% faster, so lp=25 is definitely better. lp=27 would be very wrong for this size of number.

fivemack , if I read between your lines , I think maybe you are
saying that the time for sieving is so large and so dominates the
entire process that , for the most part , one can ignore dozens of
other issues and simply focus on how fast the sieving goes .
If I assume that , I don't grok your references to relations per
Q , so is that just a general rule of thumb , possibly to be
subjected to testing ?
In attacking np ( 84 ) = 84^84 + 85^85 , I tested the polys
you and I suggested and found yours a little faster .
I also tested alim , and chose a value considerably smaller than
you seemed to be suggesting .
I ended up with this .poly :

n: 2338982017797237791089936673052392178432960366851281820310933515219896907143162790825786825648557970330051538281665605839305766635119843459428683247822854186362127
c5: 84
c0: 1
Y0: 631134233006543551770782470703125
Y1: -516116642098754030145043477561344
lpbr: 25
lpba: 25
mfbr: 50
mfba: 50
alambda: 2.6
rlambda: 2.6
alim: 2000000
rlim: 2000000
type: snfs

And I was rewarded for my attention to detail with a seemingly
faster factorization than might be implied by my earlier runs .
The following excerpt of the console output allows one to observe
the timing of rel collection :

2011-10-08 13:37:20.60 C:\ac> findstr "sec/ od" 84.run
...
2011-10-02 22:55:46.93 C:\gg\84> dir /od
total yield: 74, q=1050031 (0.08509 sec/rel)
total yield: 87547, q=1050011 (0.09863 sec/rel)
total yield: 85693, q=1100009 (0.10105 sec/rel)
total yield: 9438, q=1155499 (0.10334 sec/rel)
2011-10-02 22:54:14.54 C:\gg\84> dir /od
total yield: 86851, q=1200007 (0.10274 sec/rel)
total yield: 86512, q=1150027 (0.10384 sec/rel)
total yield: 84639, q=1250003 (0.10465 sec/rel)
total yield: 84447, q=1300021 (0.10513 sec/rel)
total yield: 84807, q=1350001 (0.10400 sec/rel)
total yield: 85238, q=1400017 (0.10429 sec/rel)
total yield: 104, q=1450069 (0.11613 sec/rel)
2011-10-03  1:37:16.06 C:\gg\84> dir /od
total yield: 83823, q=1450019 (0.10698 sec/rel)
total yield: 83366, q=1500007 (0.10783 sec/rel)
total yield: 82294, q=1600033 (0.10675 sec/rel)
total yield: 82694, q=1550027 (0.10706 sec/rel)
total yield: 82818, q=1700021 (0.10681 sec/rel)
total yield: 82919, q=1650001 (0.10682 sec/rel)
total yield: 76126, q=1796947 (0.10840 sec/rel)
2011-10-03  8:48:00.79 C:\gg\84> dir /od
total yield: 81378, q=1800017 (0.11192 sec/rel)
total yield: 81815, q=1750009 (0.11138 sec/rel)
total yield: 1204, q=1800677 (0.10373 sec/rel)
2011-10-03 18:31:30.39 C:\gg\84> dir /od
total yield: 81419, q=1850021 (0.11047 sec/rel)
total yield: 81132, q=1900009 (0.11104 sec/rel)
total yield: 77290, q=1947223 (0.10908 sec/rel)
2011-10-03 18:47:17.23 C:\gg\84> dir /od
total yield: 79925, q=2000003 (0.11030 sec/rel)
total yield: 81551, q=1950017 (0.10884 sec/rel)
total yield: 2033, q=2051219 (0.11180 sec/rel)
2011-10-03 23:35:50.50 C:\gg\84> dir /od
total yield: 79055, q=2100001 (0.11233 sec/rel)
total yield: 79935, q=2050007 (0.11163 sec/rel)
total yield: 77130, q=2200013 (0.11411 sec/rel)
total yield: 79027, q=2150009 (0.11207 sec/rel)
total yield: 14209, q=2209061 (0.11640 sec/rel)
2011-10-03 23:47:13.71 C:\gg\84> dir /od
total yield: 76545, q=2300003 (0.11571 sec/rel)
total yield: 76983, q=2250013 (0.11644 sec/rel)
total yield: 75008, q=2350001 (0.11430 sec/rel)
total yield: 75378, q=2400001 (0.11511 sec/rel)
total yield: 74143, q=2450003 (0.11603 sec/rel)
total yield: 74033, q=2500009 (0.11623 sec/rel)
total yield: 28815, q=2570083 (0.12005 sec/rel)
2011-10-04  5:08:00.09 C:\gg\84> dir /od
total yield: 73092, q=2550001 (0.12790 sec/rel)
total yield: 73111, q=2600011 (0.12830 sec/rel)
total yield: 72295, q=2650007 (0.12229 sec/rel)
total yield: 71885, q=2700023 (0.12317 sec/rel)
total yield: 40616, q=2778877 (0.12906 sec/rel)
2011-10-04 13:20:36.56 C:\gg\84> dir /od
total yield: 70312, q=2750021 (0.13100 sec/rel)
total yield: 70339, q=2800001 (0.13147 sec/rel)
total yield: 68998, q=2900017 (0.13040 sec/rel)
total yield: 71464, q=2850013 (0.12833 sec/rel)
total yield: 3251, q=2952311 (0.13333 sec/rel)
2011-10-04 18:30:29.93 C:\gg\84> dir /od
total yield: 68521, q=2950001 (0.13495 sec/rel)
total yield: 68577, q=3000017 (0.13523 sec/rel)
total yield: 67693, q=3050009 (0.13112 sec/rel)
total yield: 67779, q=3100007 (0.13168 sec/rel)
total yield: 5294, q=3153743 (0.13263 sec/rel)
2011-10-04 22:17:23.12 C:\gg\84> dir /od
total yield: 67906, q=3200003 (0.13119 sec/rel)
total yield: 67897, q=3150001 (0.13237 sec/rel)
total yield: 67217, q=3250021 (0.12879 sec/rel)
total yield: 65390, q=3300001 (0.13294 sec/rel)
total yield: 64847, q=3400043 (0.13034 sec/rel)
total yield: 65594, q=3350021 (0.12939 sec/rel)
total yield: 29736, q=3422669 (0.12985 sec/rel)
2011-10-05  3:25:24.14 C:\gg\84> dir /od
total yield: 62932, q=3500017 (0.13281 sec/rel)
total yield: 65142, q=3450011 (0.13114 sec/rel)
total yield: 2797, q=3552179 (0.13309 sec/rel)
2011-10-05 11:40:18.26 C:\gg\84> dir /od
total yield: 63504, q=3550007 (0.13174 sec/rel)
total yield: 63920, q=3600001 (0.13211 sec/rel)
...
2011-10-08 16:18:25.75 C:\ac>

The console output consists of alternating copy/pastes from the actual run and dirs.
In there , the line before each dir command shows rels which were also
included in one of the next two lines , and those two following lines are
more likely to be too high because of my peeking .
( Perversely , the clock times shown on the dir commands are the
earlier times of the prompt , and _not_ the time of the dir .
)

It seems that my choice of minimum relations = 3500000 caused the
-nc1 run to fail repeatedly and ended up with 4039282 relations ,
and presumably , a large matrix .
It was 495 K almost-square :

matrix is 494943 x 495168

More details available AYR .

Looking forward to larger N , can a bad alim produce a bad matrix ?

[Brian Gladman]

Originally Posted by fivemack

A straight 3.5 / 6.5 / 13.5 would be better than estimating 10.0 each time.

Looking at about eighty factorisations in each range done with my equivalent script:

In the 120-130 digit range, using 26-bit large primes, I need on average 120000*log(N)-8000000 relations, and at most 150000*log(N)-11500000 (log to base 10 in either case)

In the 110-115-digit range, using 25-bit large primes, 70000*log(N)-4200000 works on average and -3900000 works all the time.

Is that helpful?

Hi Fivemack,

I'm sorry for the delay in my response but I have been taking a holiday.

Thank you for your data, whiich may well prove useful if I can work out all the details:

1. First, is this GNFS, not SNFS?

2. In the 115-120 digits gap, do I compute both estimates and use the LP bits giving the lower estimate?

[fivemack]

This is GNFS.

I only have data when I've had to run filtering more than once (so that I have a 'this doesn't suffice' as well as a 'this suffices'); and the parameters my tool uses for 115-120 digits are over-estimates and give enough relations for the first filtering to work. I've been using 26-bit from 115 digits upwards.

[ltd]

I have a small issue with the factmsieve script.

I have downloaded the latest SVN snapshots of MPIR, GGNFS and msieve and compiled them. To test if everything works well I have let them run the "smallSNFS" test from ggnfs using factmsieve.86 as script.

The tools worked without a problem and found the factors but factmsieve did not notice that a factor was found and triggered another sieving run. I stopped it as it continued to make one run after the other.

Similar behavior also with the RSA100 test.

Here is the part of the logfile:

Fri Oct 21 07:33:22 2011 -> gnfs-lasieve4I11e -k -o spairs.out.T1 -v -n 1 -r snfs_small.job.T1
Fri Oct 21 07:33:22 2011 -> gnfs-lasieve4I11e -k -o spairs.out.T2 -v -n 2 -r snfs_small.job.T2
Fri Oct 21 07:33:22 2011 -> gnfs-lasieve4I11e -k -o spairs.out.T3 -v -n 3 -r snfs_small.job.T3
Fri Oct 21 07:34:22 2011 Found 485973 relations, 349.7% of the estimated minimum (138949).
Fri Oct 21 07:34:22 2011 -> msieve -s tests\snfs_small\snfs_small.dat -l tests\snfs_small\snfs_small.log -i tests\snfs_small\snfs_small.ini -nf tests\snfs_small\snfs_small.fb -t 4 -nc1
Fri Oct 21 07:34:22 2011
Fri Oct 21 07:34:22 2011
Fri Oct 21 07:34:22 2011 Msieve v. 1.45
Fri Oct 21 07:34:22 2011 random seeds: ceb79420 de58afbf
Fri Oct 21 07:34:22 2011 factoring 113646869863729728683970721951103 (33 digits)
Fri Oct 21 07:34:22 2011 p7 factor: 3887047
Fri Oct 21 07:34:22 2011 p9 factor: 164511353
Fri Oct 21 07:34:22 2011 prp18 factor: 177722253954175633
Fri Oct 21 07:34:22 2011 elapsed time 00:00:00
Fri Oct 21 07:34:22 2011 LatSieveTime: 60.262
Fri Oct 21 07:34:22 2011 -> making sieve job for q = 352500 in 352500 .. 353125 as file snfs_small.job.T0
Fri Oct 21 07:34:22 2011 -> making sieve job for q = 353125 in 353125 .. 353750 as file snfs_small.job.T1
Fri Oct 21 07:34:22 2011 -> making sieve job for q = 353750 in 353750 .. 354375 as file snfs_small.job.T2
Fri Oct 21 07:34:22 2011 -> making sieve job for q = 354375 in 354375 .. 355000 as file snfs_small.job.T3
Fri Oct 21 07:34:22 2011 -> Lattice sieving rational q from 352500 to 355000.
Fri Oct 21 07:34:22 2011 -> gnfs-lasieve4I11e -k -o spairs.out.T0 -v -n 0 -r snfs_small.job.T0
Fri Oct 21 07:34:22 2011 -> gnfs-lasieve4I11e -k -o spairs.out.T1 -v -n 1 -r snfs_small.job.T1
Fri Oct 21 07:34:22 2011 -> gnfs-lasieve4I11e -k -o spairs.out.T2 -v -n 2 -r snfs_small.job.T2
Fri Oct 21 07:34:22 2011 -> gnfs-lasieve4I11e -k -o spairs.out.T3 -v -n 3 -r snfs_small.job.T3
Fri Oct 21 07:34:54 2011 -> Return value 0. Updating job file and terminating...
Fri Oct 21 07:34:54 2011 LatSieveTime: 32.134

[Brian Gladman]

It looks like msieve is not writing the *.cyc file that is used to determine whether msieve has factored the number or whether more sieving is needed. I don't know why this file is not being written - maybe Jason can advise on what may be causing this. It doesn't write a *.dep file either so this part of factmsieve.py fails as well.