New polynomial finder discussion

smh · 2008-11-23, 11:05

Whats the maximum composite size for poly selection?

As a test i tried the c180 from 5^421-1 but get:

Code:

error: no parameters for 180 digit inputs

jasonp · 2008-11-23, 13:44

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.

fivemack · 2008-11-23, 14:07

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.

fivemack · 2008-11-23, 14:29

I ran

Code:

 ../msieve -v -np 1,1000000 35322125576541579190013421927694098754444936841051035382674099467379332502218767269754262503999046427

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

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

Andi47 · 2008-11-23, 14:42

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).

smh · 2008-11-23, 16:22

Quote:

Originally Posted by Andi47

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?

I was just about to ask, can you also calculate/print the skew of the polynomial?

jasonp · 2008-11-23, 17:09

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.

Andi47 · 2008-11-23, 17:14

Quote:

Originally Posted by jasonp

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

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

...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)

jasonp · 2008-11-23, 17:21

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?

Andi47 · 2008-11-23, 17:22

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

jasonp · 2008-11-23, 17:38

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.

2008-11-23, 11:05	#1
smh "Sander" Oct 2002 52.345322,5.52471 10010100101₂ Posts	New polynomial finder discussion Whats the maximum composite size for poly selection? As a test i tried the c180 from 5^421-1 but get: Code: error: no parameters for 180 digit inputs

2008-11-23, 17:09	#7
jasonp Tribal Bullet Oct 2004 3×1,181 Posts	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. Last fiddled with by jasonp on 2008-11-23 at 17:15

2008-11-23, 17:21	#9
jasonp Tribal Bullet Oct 2004 3×1,181 Posts	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? Last fiddled with by jasonp on 2008-11-23 at 17:23

2008-11-23, 17:22	#10
Andi47 Oct 2004 Austria 2482₁₀ Posts	thanks. Benchmark (using gnfs-lasieve4I13e for sieving) is running. Last fiddled with by Andi47 on 2008-11-23 at 17:22

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial Discriminant is n^k for an n-1 degree polynomial	carpetpool	Miscellaneous Math	14	2017-02-18 19:46
Polynomial algorithm	diep	Factoring	7	2012-09-29 12:09
Question about polynomial finder	jordis	Msieve	1	2009-01-10 17:58
[Need help] about Matrix Polynomial	buan	Homework Help	3	2007-07-17 15:07
Polynomial	R.D. Silverman	NFSNET Discussion	13	2005-09-16 20:07

2008-11-23, 13:44	#2
jasonp Tribal Bullet Oct 2004 3×1,181 Posts	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.

2008-11-23, 14:07	#3
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2³·11·73 Posts	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.

2008-11-23, 14:42	#5
Andi47 Oct 2004 Austria 2482₁₀ Posts	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).

2008-11-23, 17:38	#11
jasonp Tribal Bullet Oct 2004 110111010111₂ Posts	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.