Call for volunteers: RSA896

[debrouxl]

firejuggler: your best poly isn't good, it has pretty low E value

jasonp:

The patch makes all the MPI processes wait at a barrier when poly selection is finishing, and my experience with OpenMPI is that this is a computationally expensive operation. I suspect that's what is burning up 100% CPU.

Meh.

Unfortunately there's no real way around that, if you wanted processes to stop waiting on each other then you wouldn't be using barrier synchronization; put another way, MPI is a poor substitute for a distributed client-server architecture :)

Indeed.
Several weeks ago, for factoring a 512-bit RSA key under a "tight" deadline (well, I hadn't fully taken into account how much easier it had become since 2009, and the fact that in the end, I had 40 cores of varying power ^^), I spent several hours starting to assemble a simple client-server work reservation system, speaking HTTP GET & PUT, in Perl (CPAN lists a number of modules for dealing with HTTP).
The initial results were good, but the task was easy enough that I ended up just invoking ggnfs-lasieve4I14e in sh scripts instead of finishing the reservation system.

[firejuggler]

I know my poly isn't good, it's just a quasi-note to myself that 'I can do it'. I will make another run, a bit longer and see what come out of it.

[bai]

Originally Posted by poily

Bai, I used E.sage from the public CADO repository and got almost the same Murphy e values as msieve shows. Do you compute it somehow different now?

poily, thanks for noting it. Yes, there is some difference when computing the Dickman function. It might explain the difference between the E-score in msieve/cado when the skewness is large. I'll keep you updated.

Btw: on your 02 Dec 12 batch, we had a better poly in terms of cado E-score. What's its score in msieve?

Y1: 9931515945117268997291
Y0: -3136213832380525741156980143018262150146233
c6: 433000028380920
c5: -16322847463557673445083
c4: 259713520920507700049024012254
c3: 313991938835577956615333794603976847
c2: -745313305236683785443677828883521154358049
c1: -8720107683218999638110247380980954223758742214
c0: 177258901573455869908310457463881265392025516480999800
skew: 1650176.000
# lognorm: 79.02, alpha: -9.49 (proj: -2.31), E: 69.53, nr: 4
# MurphyE(Bf=10000000,Bg=5000000,area=1.00e+16)=4.33e-19

Anyway, if we can observe a correlation between the scores in msieve and cado, then it's safe to just record a few top polynomials found by both.

[jasonp]

I get

skew 1650176.00, size 6.274e-20, alpha -9.489, combined = 3.183e-19 rroots = 4

[poily]

I agree with debrouxl that the MPI-ed polynomial selection should be included in some form in the mainline msieve. I'm tired of doing the trivial patchwork for every new major msieve revision ;)

The patch makes all the MPI processes wait at a barrier when poly selection is finishing, and my experience with OpenMPI is that this is a computationally expensive operation. I suspect that's what is burning up 100% CPU.

Actually looks like the problem is in MPI_Gather which is there to collect the results from all the processors and select the best after the polynomial selection is complete. I suggest we remove this stage at all making each of the MPI processes save it's own fb-file allowing the user to select the best.

Btw: on your 02 Dec 12 batch, we had a better poly in terms of cado E-score.

Hmm, looks like CADO does better size optimization not only the root sieve. What was the original hit that produced that polynomial? And what size norm was it of after the size optimization? I wonder what msieve can do with it if we try to tune relevant parameters a bit.

Anyway, if we can observe a correlation between the scores in msieve and cado, then it's safe to just record a few top polynomials found by both.

Tbh, I'd prefer both of the tools show the same values, it's exact science after all.

[debrouxl]

Actually looks like the problem is in MPI_Gather which is there to collect the results from all the processors and select the best after the polynomial selection is complete. I suggest we remove this stage at all making each of the MPI processes save it's own fb-file allowing the user to select the best.

Amusingly, that's what I had just done locally, by replacing #ifdef HAVE_MPI by #if 0 in the hunk modifying gnfs/poly/poly.c

[firejuggler]

Did a longer run, around 11k hits in 15 hours, will update when -nps "stage2_norm=1e100"
will have ran.
Is there an easy way to sort by field under windows? trying to do it with Librecalc/excel is doing poorly.

[jasonp]

Get a windows port of the unix sort utility, and then try

sort -g -k 11 <file>

to sort in ascending numerical order based on field 11 (the last)

[firejuggler]

ok... so cygwin is no good.
I have value from 1.007815e+34 to 1.348243e+36 and the sort don't give me the +34 and a handfull of +35 I need.
grblbl managed somehow with Librecalc, will post my hit. 11700+ hit, starting at 3e13

[poily]

This batch resulted in the following best so far polynomial:

Mon Dec 17 04:01:41 2012  R0: -5382714938488690441209883907451379700210334                                           
Mon Dec 17 04:01:41 2012  R1: 16663482999754897882819                                                                
Mon Dec 17 04:01:41 2012  A0: -55149587676457221661976298276728946108324308303659979586785                           
Mon Dec 17 04:01:41 2012  A1: 2084363501398641733507654116431852917627220374513244                                   
Mon Dec 17 04:01:41 2012  A2: 115328708937118208864934751144873150311335660                                          
Mon Dec 17 04:01:41 2012  A3: -3417129234272571170820957161968499682                                                 
Mon Dec 17 04:01:41 2012  A4: -7825764054023217154734470955                                                          
Mon Dec 17 04:01:41 2012  A5: 1089651465313173279574                                                                 
Mon Dec 17 04:01:41 2012  A6: 16940008971600                                                                         
Mon Dec 17 04:01:41 2012  skew 43447739.22, size 4.643e-20, alpha -11.010, combined = 2.483e-19 rroots = 2

I'm still not sure how I've missed the 3.183e-19 one, maybe that's because I take only 50-100 size optimized values (with norms 1e32-*e33). I'll try to restart root optimization with 1000 best size norms (probably, 1e32-*e34).

[bai]

Originally Posted by poily

What was the original hit that produced that polynomial? And what size norm was it of after the size optimization? I wonder what msieve can do with it if we try to tune relevant parameters a bit.

The raw polynomial is this one,

433000028380920 9931515945117268997291 3136213832380463342922092847039625251389592

The size optimized polynomial in cado is,

Y1: 9931515945117268997291
Y0: -3136213832380526651668430475424366552787822
c6: 433000028380920
c5: -16561029521169279633163
c4: 267250423315714655877175299839
c3: 217372220497467849979460290451947353
c2: -818449055340804222519290511517032253432988
c1: -162909026138981074398068520700268950925476629841
c0: 139263538137801830327982923308744587295054517282499033
skew: 1619456.000
# lognorm: 78.88, alpha: -0.83 (proj: -2.31), E: 78.05, nr: 4
# MurphyE(Bf=10000000,Bg=5000000,area=1.00e+16)=3.54e-20