mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operation Kibibit

Reply
 
Thread Tools
Old 2012-12-14, 21:08   #45
debrouxl
 
debrouxl's Avatar
 
Sep 2009

977 Posts
Default

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

jasonp:
Quote:
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.

Quote:
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.
debrouxl is offline   Reply With Quote
Old 2012-12-14, 21:15   #46
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

13·191 Posts
Default

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.

Last fiddled with by firejuggler on 2012-12-14 at 21:17
firejuggler is offline   Reply With Quote
Old 2012-12-15, 02:01   #47
bai
 
May 2011

23 Posts
Default

Quote:
Originally Posted by poily View Post
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?

Code:
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.

Last fiddled with by bai on 2012-12-15 at 02:05
bai is offline   Reply With Quote
Old 2012-12-15, 03:20   #48
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22·883 Posts
Default

I get
Code:
skew 1650176.00, size 6.274e-20, alpha -9.489, combined = 3.183e-19 rroots = 4
jasonp is offline   Reply With Quote
Old 2012-12-15, 13:52   #49
poily
 
Nov 2010

2·52 Posts
Default

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

Quote:
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.

Quote:
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.

Quote:
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.
poily is offline   Reply With Quote
Old 2012-12-15, 14:05   #50
debrouxl
 
debrouxl's Avatar
 
Sep 2009

977 Posts
Default

Quote:
Quote:
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.
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
debrouxl is offline   Reply With Quote
Old 2012-12-15, 17:33   #51
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

13·191 Posts
Default

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.
firejuggler is offline   Reply With Quote
Old 2012-12-15, 17:44   #52
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22×883 Posts
Default

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)
jasonp is offline   Reply With Quote
Old 2012-12-15, 18:54   #53
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

13×191 Posts
Default

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
Attached Files
File Type: zip msieve.dat.m.zip (310.2 KB, 101 views)

Last fiddled with by firejuggler on 2012-12-15 at 19:08
firejuggler is offline   Reply With Quote
Old 2012-12-17, 09:05   #54
poily
 
Nov 2010

628 Posts
Default

This batch resulted in the following best so far polynomial:
Code:
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).
poily is offline   Reply With Quote
Old 2012-12-17, 10:30   #55
bai
 
May 2011

101112 Posts
Default

Quote:
Originally Posted by poily View Post
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,
Code:
433000028380920 9931515945117268997291 3136213832380463342922092847039625251389592
The size optimized polynomial in cado is,
Code:
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
bai is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Volunteers needed axn GPU Computing 28 2012-05-28 12:05
call for volunteers: RSA768 polynomial selection jasonp Operation Kibibit 200 2011-11-05 21:31
Call for help Wacky NFSNET Discussion 13 2005-07-14 00:25
Volunteers needed! Xyzzy Hardware 23 2003-04-18 23:27
We need two volunteers... Xyzzy PrimeNet 8 2003-02-27 02:26

All times are UTC. The time now is 14:49.

Sat Dec 5 14:49:24 UTC 2020 up 2 days, 11 hrs, 0 users, load averages: 1.54, 1.67, 1.64

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.