Size optimization - Page 2

Sleepy · 2011-10-18, 08:21

Thanks! I'll keep a look out for it! So does that mean that Stage 1 would run less effectively, i.e. takes a lot of time for a hit, because too much of the search space is cut out for a 1024 bit GNFS? Or does it mean that the hit did not satisfy certain conditions thus is a rubbish result?

jasonp · 2011-10-18, 14:41

Any hits that are printed are guaranteed to be correct, the only question is how fast you can generate them. Actually reducing the search space may not affect the speed all that much, it just means that more time gets spent initializing a hashtable and less spent reusing the result.

I'm not sure anyone has a good feel for whether 1024-bit inputs are small enough for degree-7 to be effective; stage 1 would be much easier but almost nothing would survive the size optimization in stage 2, especially with lots of skew.

debrouxl · 2011-10-19, 06:22

After putting the following wild guesses

Code:

 	{270, 1.00E+035, 1.00E+036, 0},
 	{275, 3.00E+036, 3.00E+037, 0},

in gnfs/poly/poly_skew.c, I ran polynomial selection on RSA-896 for ~12h of CPU time. ~8000 polys were generated, the one with highest e score is:

Code:

R0: -363029228278845980470106681391851560187883004
R1: 4053299083004753978612029
A0: 4995054090860139669606932598077822957128370347757781755767335
A1: 8733487242188076789625588491652063428050868326602056
A2: -7481081371421389762205810150886156242318117226
A3: 312421614480666145327244548538242179
A4: 203782189164926047972499845439
A5: -5167674237407467
A6: 180
skew 659113113.10, size 1.251e-20, alpha -9.738, combined = 8.655e-20 rroots = 4

Would polynomial selection on numbers larger than RSA-768 benefit from deadline_per_coeff > 3200 ?
After the RSA-768 stage 1 hits are boiled down (in another topic), should we perform polynomial selection on all RSA numbers between 210 and 310 digits inclusive, as (maybe ?) a ways to narrow down the parameters in msieve ? I guess it would take a number of core-years, so only clusters and grids would run through the work efficiently, wouldn't they ?

Sleepy · 2011-10-20, 10:27

I see... Thanks!:) So the support code refers to hashtable functions and the parameters initialization made before the search and not about some calculations that will cause the result to be wrong.

Quote:

Okay, I fixed a few problems in the size optimization (the code's notion of 'infinitely large size' needed updating to cope with 1024-bit inputs :)

Are there any other such constants and values of parameters that one might also need to watch out for and adjust accordingly? ;)

2011-10-19, 06:22	#14
debrouxl Sep 2009 977 Posts	After putting the following wild guesses Code: {270, 1.00E+035, 1.00E+036, 0}, {275, 3.00E+036, 3.00E+037, 0}, in gnfs/poly/poly_skew.c, I ran polynomial selection on RSA-896 for ~12h of CPU time. ~8000 polys were generated, the one with highest e score is: Code: R0: -363029228278845980470106681391851560187883004 R1: 4053299083004753978612029 A0: 4995054090860139669606932598077822957128370347757781755767335 A1: 8733487242188076789625588491652063428050868326602056 A2: -7481081371421389762205810150886156242318117226 A3: 312421614480666145327244548538242179 A4: 203782189164926047972499845439 A5: -5167674237407467 A6: 180 skew 659113113.10, size 1.251e-20, alpha -9.738, combined = 8.655e-20 rroots = 4 Would polynomial selection on numbers larger than RSA-768 benefit from deadline_per_coeff > 3200 ? After the RSA-768 stage 1 hits are boiled down (in another topic), should we perform polynomial selection on all RSA numbers between 210 and 310 digits inclusive, as (maybe ?) a ways to narrow down the parameters in msieve ? I guess it would take a number of core-years, so only clusters and grids would run through the work efficiently, wouldn't they ?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
gcc optimization/intrinsics	R.D. Silverman	Factoring	12	2015-09-15 08:51
Program optimization	henryzz	Programming	17	2012-09-26 13:21
Possible optimization for GIMPS	alpertron	Math	3	2012-08-13 16:08
NFS Optimization	R.D. Silverman	Factoring	91	2010-01-24 20:48
ASM Optimization	Cyclamen Persicum	Hardware	4	2004-05-26 07:51

2011-10-18, 08:21	#12
Sleepy May 2011 17₁₆ Posts	Thanks! I'll keep a look out for it! So does that mean that Stage 1 would run less effectively, i.e. takes a lot of time for a hit, because too much of the search space is cut out for a 1024 bit GNFS? Or does it mean that the hit did not satisfy certain conditions thus is a rubbish result?

2011-10-18, 14:41	#13
jasonp Tribal Bullet Oct 2004 6725₈ Posts	Any hits that are printed are guaranteed to be correct, the only question is how fast you can generate them. Actually reducing the search space may not affect the speed all that much, it just means that more time gets spent initializing a hashtable and less spent reusing the result. I'm not sure anyone has a good feel for whether 1024-bit inputs are small enough for degree-7 to be effective; stage 1 would be much easier but almost nothing would survive the size optimization in stage 2, especially with lots of skew.