New polynomial finder discussion
 

Whats the maximum composite size for poly selection?

As a test i tried the c180 from [URL="http://www.mersenneforum.org/showthread.php?t=10365"]5^421-1[/URL] but get:[CODE]error: no parameters for 180 digit inputs[/CODE]

Sander, the poly selection code only has parameters for GNFS < 160 digits (they're copied from GGNFS, and the parameters are the same except for a little scaling). The largest input I'm bothering with right now is RSA140, there's a huge amount of optimization still needed.

I know this is my usual complaint, but is there any possibility with the -v option of having slightly more feedback than '5% done (processed 140 blocks)' ?

It looks as if you do stage 1 and stage 2 sequentially, and if I abort stage 1 it doesn't bother doing stage 2 so I end up trying to sieve with a polynomial with R1=1; maybe it's unreasonable to expect aborting early to work well, but I'd like restarting from an aborted stage 1 to run stage 2 on the candidates.

I don't think I quite understand the parameters
 

I ran

[code] ../msieve -v -np 1,1000000 35322125576541579190013421927694098754444936841051035382674099467379332502218767269754262503999046427
[/code]

and got

[code]
Msieve v. 1.39
Sun Nov 23 14:03:52 2008
random seeds: 579b6d77 b649d7b1
factoring 35322125576541579190013421927694098754444936841051035382674099467379332502218767269754262503999046427 (101 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (101-digit input)
commencing number field sieve polynomial selection
time limit set to 0.38 hours
100% done (processed 6960 blocks)
polynomial selection complete
R0: -326478091260962589
R1: 1
A0: -1016023020301895
A1: 4362619536512986
A2: -5580476429702764
A3: -459145250104252
A4: 196381134611400
A5: 9523062108000
size score = 1.495554e-10, Murphy alpha = -4.225643, combined = 6.116832e-10
elapsed time 00:23:06
[/code]

which surprises me slightly because A5 is not in the range 1,1000000 and I was expecting R1 != 1.

Questions / remarks:

1.) msieve seems to elapse the time by "real" clock and not by CPU-time: So when I set my PC to standby (for example overnight - my P4 is too loud to let it run) and switch it on next day, msieve assumes that the time limit has been reached and quits polynomial searching.

2.) I just tried to use a msieve-polynomial for ggnfs-lasieve4I1?e and got "pleas specify a skewness". How do I calculate the skewness?

3.) feature request: Please implement a feature / option to output polynomials in ggnfs format and to read ggnfs-formatted polynomials (for example when postprocessing).

[QUOTE=Andi47;150344]2.) I just tried to use a msieve-polynomial for ggnfs-lasieve4I1?e and got "pleas specify a skewness". How do I calculate the skewness?[/QUOTE]I was just about to ask, can you also calculate/print the skew of the polynomial?

Sorry that I skipped some details:

- if you build from source with no makefile arguments, you get the old (known working) nonskewed-polynomial selector, which is very sucky. To get the new polynomial finder you need to run make with GMP=1 or ECM=1 (which expects the GMP library to be available, and allows the new poly finder to get built). It isn't difficult to remove the dependency on GMP, there isn't much multiprecision arithmetic at this stage. Assuming that happens at some point, the new poly finder will get built by default.

- regardless of the polynomial that is selected, all polynomials that are found get appended to msieve.dat.p, and the output includes the polynomial skew. Appending in GGNFS lattice siever format is a good idea.

[QUOTE=jasonp;150356]Sorry that I skipped some details:

- if you build from source with no makefile arguments, you get the old (known working) nonskewed-polynomial selector, which is very sucky. To get the new polynomial finder you need to run make with ECM=1 (which includes GMP, and allows the new poly finder to get built).

- regardless of the polynomial that is selected, all polynomials that are found get written to msieve.dat.p, and the output includes the polynomial skew[/QUOTE]

Do I understand correctly, that in msieve.log...

[code]Sun Nov 23 08:39:11 2008
Sun Nov 23 08:39:11 2008
Sun Nov 23 08:39:11 2008 Msieve v. 1.39
Sun Nov 23 08:39:11 2008 random seeds: 4458042c 89fa2708
Sun Nov 23 08:39:11 2008 factoring 223647331337501130642693578497501842426733748444730351702780813709242741096431450273917668186036117236877146296909317487 (120 digits)
Sun Nov 23 08:39:14 2008 searching for 15-digit factors
Sun Nov 23 08:39:17 2008 commencing number field sieve (120-digit input)
Sun Nov 23 08:39:17 2008 commencing number field sieve polynomial selection
Sun Nov 23 08:39:17 2008 time limit set to 3.75 hours
Sun Nov 23 08:39:17 2008 searching leading coefficients from 4349 to 37114
Sun Nov 23 14:58:44 2008 polynomial selection complete
Sun Nov 23 14:58:44 2008 R0: -137806723240087021239057
Sun Nov 23 14:58:44 2008 R1: 5526556814339
Sun Nov 23 14:58:44 2008 A0: -5558888226976215535514572574080
Sun Nov 23 14:58:44 2008 A1: 39678464140799797940413876
Sun Nov 23 14:58:44 2008 A2: 91932264615385941392
Sun Nov 23 14:58:44 2008 A3: -861252344721509
Sun Nov 23 14:58:44 2008 A4: -212993220
Sun Nov 23 14:58:44 2008 A5: 4500
Sun Nov 23 14:58:44 2008 size score = 2.231815e-012, Murphy alpha = -6.452200, combined = 1.917387e-011
Sun Nov 23 14:58:44 2008 elapsed time 06:19:33
[/code]

...this polynomial is the best one which msieve has found?

Can you please include the skew to msieve.log, so that we don't have to search for the poly in msieve.dat.p? (there are quite a number of polynomials there)

Yes, that's the best one found. Printing the skew is easy, I'll throw it in.

Does GGNFS also need the value of M when given a non-monic rational polynomial, or is M calculated?

thanks. Benchmark (using gnfs-lasieve4I13e for sieving) is running.

I should also mention that there's no need to build up candidates and then run stage 2 separately; the library runs stage 2 after every candidate is found.