call for volunteers: RSA768 polynomial selection

jasonp · 2011-04-21, 14:06

It turns out I need a large dataset for testing out some poly selection ideas, and also to look for problems in msieve's stage 2 root sieve, so I propose we get some volunteers to run msieve's polynomial selection on RSA768. I only have 4 cores at home, so I'll need some help.

If you're interested in helping out, you will need at least msieve v1.48; either the CPU or the GPU version will work fine, since I don't know which is faster anymore after many optimization passes by jrk and myself last year.

If you want all the output in the same directory, and have multiple cores, then create a worktodo.ini file containing only

Code:

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

all on one line, and for core X just run

Code:

msieve -v -l msieve.logX -nf msieve.fbX -s msieve.datX -np1 START,END

where START and END are the lower and upper limits for the range of A6 to search. This will only run stage 1, so if you have a GPU it will be fully utilized.

I don't think we need reservations; the search space is huge, and the piece of it that is explored is selected randomly when msieve starts. You can even give all your machines the same START and END, just make sure START is more than about 10000 or so and END is less than 10^9. Choose a range that is comfortable for you; I use blocks of 50k or so and that should take a few days. The memory use will be minimal, and it should scale nicely on a single machine. Feel free to email me the resulting msieve.datX.m file, it shouldn't be very large.

Thanks in advance...

ET_ · 2011-04-21, 15:47

I'm in...

Code:

error (line 197): CUDA_ERROR_FILE_NOT_FOUND

I'm running CUDA 3.0 on Ubuntu x86_64.
Luigi

jasonp · 2011-04-21, 19:15

Do you have .ptx files in the current working directory? It sounds like they can't be found...

xilman · 2011-04-21, 20:23

Quote:

Originally Posted by jasonp

It turns out I need a large dataset for testing out some poly selection ideas, and also to look for problems in msieve's stage 2 root sieve, so I propose we get some volunteers to run msieve's polynomial selection on RSA768. I only have 4 cores at home, so I'll need some help.

If you're interested in helping out, you will need at least msieve v1.48; either the CPU or the GPU version will work fine, since I don't know which is faster anymore after many optimization passes by jrk and myself last year.

If you want all the output in the same directory, and have multiple cores, then create a worktodo.ini file containing only

Code:

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

all on one line, and for core X just run

Code:

msieve -v -l msieve.datX -nf msieve.fbX -s msieve.datX -np1 START,END

where START and END are the lower and upper limits for the range of A6 to search. This will only run stage 1, so if you have a GPU it will be fully utilized.

I don't think we need reservations; the search space is huge, and the piece of it that is explored is selected randomly when msieve starts. You can even give all your machines the same START and END, just make sure START is more than about 10000 or so and END is less than 10^9. Choose a range that is comfortable for you; I use blocks of 50k or so and that should take a few days. The memory use will be minimal, and it should scale nicely on a single machine. Feel free to email me the resulting msieve.datX.m file, it shouldn't be very large.

Thanks in advance...

As a matter of interest, why select polynomials for an integer which has already been factored?

Why not choose another integer for which polynomials may be used to find an unknown factorization?

I'd be more likely to contribute if I thought my computrons were to be used to discover not only how to optimize an algorithm but also to factor something new.

Paul

Batalov · 2011-04-21, 20:58

Is this one better? ;-)

Code:

1277084241151234056138032444117696294463495814859358729085598492505371354848881700339362323998975213394079746572338141432416331606901339736311198821300573531889266392471447339245789340640531173457490909466115724372364498629623169567

I have erased the factors from the disk and then drilled a hole in it. Honest, guv'nor!

jrk · 2011-04-21, 23:20

or RSA232:

Code:

1009881397871923546909564894309468582818233821955573955141120516205831021338528545374366109757154363664913380084917065169921701524733294389270280234380960909804976440540711201965410747553824948672771374075011577182305398340606162079

jasonp · 2011-04-22, 01:09

The advantage to RSA768 over all the other similarly large numbers is that we have a known high-quality polynomial to compare against, the result of many machine-decades of computation that nobody has been able to beat (yet) even with more powerful algorithms. It doesn't matter to me at all that RSA768 is finished, since I wouldn't try to actually proceed with the sieving even if the target was unfactored.

EdH · 2011-04-22, 02:40

I started an msieve 1.48 run on a WinXP SP2 P4 2GHz 768MB machine with the following command:

Code:

msieve -v -l msieve.dat -nf msieve.fb -s msieve.dat -np1 10000,20000

What came back, so far:

Code:

Msieve v. 1.48
Thu Apr 21 17:14:12 2011
random seeds: b9cd5ef0 56d2f1c8
factoring 12301866845301177551304949583849627207728535695953347921973224
400507263657518745202199786469389956474942774063845925192557326303453731
791702612214291346167042921431160222124047927473779408066535141959745985
13 (232 digits)
searching for 15-digit factors
commencing number field sieve (232-digit input)
commencing number field sieve polynomial selection
searching leading coefficients from 10000 to 20000
deadline: 3200 seconds per coefficient
randomizing rational coefficient: using piece #1 of 21
p = 71.13 bits, sieve = 98.71 bits
coeff 10032 specialq 18158186 - 19604544 other 9358796 - 14038195
aprogs: 99268 entries, 320594 roots
poly 10032 2282451445199536922149 70485088559861748602501485521335617706
poly 10032 2105930248610298754309 70485088559873131853887948015503834692
poly 10032 2395423117256603750111 70485088559860089822613203334649695087
poly 10032 2122059671201707677299 70485088559855909769785855170575396408
poly 10032 2821785041227369536419 70485088559870209775630059540726145810
poly 10032 2721747825635695567877 70485088559868857374581546782511847042
poly 10032 1883789397981912485473 70485088559864473995160123946307214327
poly 10032 3132674142496020459257 70485088559855277435769254388873543052
poly 10032 2492682964533326601979 70485088559863144973701761354608068319
poly 10032 2029035654244117011281 70485088559871542452807670582716184156
hashtable: 48236 entries,  5.88 MB
randomizing rational coefficient: using piece #14 of 21
p = 71.13 bits, sieve = 98.72 bits
coeff 10092 specialq 49300034 - 53226940 other 5682618 - 8523927
aprogs: 63787 entries, 215004 roots
poly 10092 2921199589834893328963 70415072376793996900198145177626643480
poly 10092 3147261955872904292851 70415072376762931557683506904984865037
poly 10092 1861377589418776192501 70415072376782950819722429001726320903
poly 10092 2281117153083549815461 70415072376771700436620311739710830962
poly 10092 2773420321500702919241 70415072376793390243204655340402295451
poly 10092 2418010623966010642709 70415072376759358253191239924274075454
poly 10092 2429680660679877830197 70415072376767242455813634137485610367
poly 10092 3699907063125108479431 70415072376788496519731167317242157244
poly 10092 2706280899754443170537 70415072376740310187214581290368514904
poly 10092 2266709534860625534897 70415072376763307504728189559925033327
poly 10092 2354794694019300674659 70415072376782525504691776451513354740
poly 10092 2929909215552701610359 70415072376756645783706039026967661926
poly 10092 2955853655531965570319 70415072376761178273596387809470352871
poly 10092 3241922373680313327151 70415072376792697633011841542428741774
poly 10092 2858998510167370706569 70415072376770669044644699588409008525
hashtable: 68783 entries,  2.94 MB
randomizing rational coefficient: using piece #9 of 21
p = 71.13 bits, sieve = 98.72 bits
coeff 10140 specialq 33673201 - 36355380 other 6878624 - 10317936
aprogs: 75044 entries, 250058 roots
poly 10140 2892356760713787143591 70359408186405834743112561085997476210
poly 10140 1998451404062744032901 70359408186433131179389883290050712373
poly 10140 1903211969473191389773 70359408186444897785950687457625256951
poly 10140 2511760929895285576507 70359408186441837932637595700833916565
poly 10140 2393921004168073668007 70359408186439921430792331637258659458
poly 10140 1984459263374618000519 70359408186440058228706929917180083112
poly 10140 2229046024000180001753 70359408186427813719500839952731094428
poly 10140 2156690978207222948693 70359408186433484757519676617903399008
poly 10140 2556288654423653055461 70359408186423511841580998379560582557
poly 10140 2222332586970390086327 70359408186452853559786546402886001814
poly 10140 2798628098357541397877 70359408186444232436887295416693254116
poly 10140 1950853441968147266843 70359408186432537840124644049417312145
poly 10140 3366249427879027087577 70359408186456816744727186487384615676
poly 10140 2362847541745343221237 70359408186433026743667455409131739186
hashtable: 133603 entries,  5.38 MB
randomizing rational coefficient: using piece #21 of 21
p = 71.13 bits, sieve = 98.72 bits
coeff 10152 specialq 84510343 - 91241864 other 4342418 - 6513627
aprogs: 49657 entries, 165770 roots
poly 10152 2493221498265160496801 70345540163159109704137263454805740817
poly 10152 1926227160424211012731 70345540163144379959916792896826043073
poly 10152 2258215168119173283889 70345540163160761674130079458295584020
poly 10152 2858666981691623799323 70345540163152838928330506722459188193
poly 10152 2123494084363946303383 70345540163158233737232827670832952544
poly 10152 2930322756464746096151 70345540163138187964751820375599692599
poly 10152 2757530294652372907217 70345540163147522748819366254541990419
poly 10152 2022930026887293088597 70345540163153678616573356740815236308
poly 10152 3181290459244830302029 70345540163144749814852171039023479493
poly 10152 2604027359300031800509 70345540163158264413042381444556132363
poly 10152 2670355068465503863741 70345540163138990914036685270331679566
poly 10152 2066048110420092801211 70345540163165328610018204068366042683
poly 10152 2254429808347774087021 70345540163140962031973616180349754054
poly 10152 2749398110056224063019 70345540163155810380656492866197809504
poly 10152 2015491175570376185471 70345540163152870819038468303365179117
poly 10152 2898387978670124592959 70345540163135045142645241220827568009
poly 10152 2278128986992991503061 70345540163149852113013656734285303644
poly 10152 2093562404035219515113 70345540163172074139640460056288887533
poly 10152 2018067171060645534643 70345540163144077013517283366120315061
poly 10152 3108738973985193098891 70345540163130398398661032784406968333
poly 10152 1943914121047455970061 70345540163166337329259415540919745403
poly 10152 2224362788413542689473 70345540163144632612929344237763800125
poly 10152 3057143457500143122497 70345540163140110978406360675696196096
poly 10152 1938623665627797992017 70345540163147035130641453907665415547
poly 10152 1840733031702042335737 70345540163155522531670281381047946521
poly 10152 2206500824672685413389 70345540163147980939020305572722770041
hashtable: 78612 entries,  2.94 MB
randomizing rational coefficient: using piece #10 of 21
p = 71.13 bits, sieve = 98.72 bits
coeff 10164 specialq 36391210 - 39289887 other 6618066 - 9927099
aprogs: 72544 entries, 234250 roots
poly 10164 3077993895811328800123 70331691251226428558203803590430421786
poly 10164 2528957603728135686401 70331691251238565094110719260024559115
poly 10164 2458588138747376935441 70331691251234387439832315865851364678
poly 10164 1782253554878354008631 70331691251214847670706459124696317701
poly 10164 2622068906582314867333 70331691251229907338073339289761465212
poly 10164 2501374568271379599523 70331691251230689550746827696012479311
poly 10164 2282855296451400169501 70331691251211165864368857844577227326
poly 10164 2252970809967404443949 70331691251228310466564444307119782482
poly 10164 3145051445894613560287 70331691251211125912540816151274529655
poly 10164 2486484102270586653997 70331691251228064293549323826100825408
poly 10164 2052416067651213907697 70331691251222965483173562225644044782
poly 10164 2206250633043204085073 70331691251221540403469756459207755612
poly 10164 2023397235483038141381 70331691251241979779845212946406954353
poly 10164 2551242973469207756467 70331691251226521121035184084546151767
poly 10164 2117420016503837646893 70331691251249454704643841757914959750
poly 10164 2342016304236285844001 70331691251229600816828636536569204871
hashtable: 93007 entries,  2.94 MB
randomizing rational coefficient: using piece #18 of 21
p = 71.13 bits, sieve = 98.73 bits
coeff 10200 specialq 67283810 - 72643182 other 4868576 - 7302865
aprogs: 55338 entries, 190140 roots
poly 10200 2022208413342392542259 70290258696016723383748086980916481848
poly 10200 2649447860915340205579 70290258696029321418510692302957884667
poly 10200 2681608026323455394917 70290258696006993398454626981292086635
poly 10200 2926166927316662779697 70290258696019547243999806347255770929
poly 10200 2213250064911768228301 70290258696027820955607948045940549458
poly 10200 2081635465137700247759 70290258696023307065464242347092169120
poly 10200 1932139725049304677513 70290258696025788767572436952354424213
poly 10200 2839652372392664732021 70290258696031070540592373866801334485
poly 10200 2565696732201622143893 70290258696023379042406766377373431722
poly 10200 2935930881777487956517 70290258696021274622347967388258854127
poly 10200 1784941792767337147123 70290258696034522566244978003852970538
poly 10200 2009997661329222189461 70290258696028981928220732373547307445
poly 10200 2523990180477815556179 70290258696018031928836186072163581907

More later. . .

Would you like a similar run (20000,30000) on an Ubuntu P4 machine? Or will this even be large enough?

Batalov · 2011-04-22, 04:45

These are not really "poly"s. (It's a misnomer. They are 1st stage candidates.)
What you would like to see is "save"s.

...Oh, wait, this is -np1. These are good.

ET_ · 2011-04-22, 08:48

Quote:

Originally Posted by jasonp

Do you have .ptx files in the current working directory? It sounds like they can't be found...

I was so happy I compiled the source, that I forgot that last part :red:

Luigi

P.S. Meanwhile the GUI became quiite slow, but for now I can aceept it (gee, I feel like a bradip!)

jasonp · 2011-04-22, 10:36

Yes, the resource use of the GPU code is pretty noticeable, and I'll understand if you want to switch to the CPU version instead. I'll take anything between 10^4 and 10^9.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial selection	Max0526	NFS@Home	9	2017-05-20 08:57
Improved NFS polynomial selection	jasonp	Operation Kibibit	5	2014-09-07 11:02
Call for volunteers: RSA896	jasonp	Operation Kibibit	134	2013-09-03 22:08
2^877-1 polynomial selection	fivemack	Factoring	47	2009-06-16 00:24
Polynomial selection	CRGreathouse	Factoring	2	2009-05-25 07:55

2011-04-21, 14:06	#1
jasonp Tribal Bullet Oct 2004 DE7₁₆ Posts	call for volunteers: RSA768 polynomial selection It turns out I need a large dataset for testing out some poly selection ideas, and also to look for problems in msieve's stage 2 root sieve, so I propose we get some volunteers to run msieve's polynomial selection on RSA768. I only have 4 cores at home, so I'll need some help. If you're interested in helping out, you will need at least msieve v1.48; either the CPU or the GPU version will work fine, since I don't know which is faster anymore after many optimization passes by jrk and myself last year. If you want all the output in the same directory, and have multiple cores, then create a worktodo.ini file containing only Code: 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 all on one line, and for core X just run Code: msieve -v -l msieve.logX -nf msieve.fbX -s msieve.datX -np1 START,END where START and END are the lower and upper limits for the range of A6 to search. This will only run stage 1, so if you have a GPU it will be fully utilized. I don't think we need reservations; the search space is huge, and the piece of it that is explored is selected randomly when msieve starts. You can even give all your machines the same START and END, just make sure START is more than about 10000 or so and END is less than 10^9. Choose a range that is comfortable for you; I use blocks of 50k or so and that should take a few days. The memory use will be minimal, and it should scale nicely on a single machine. Feel free to email me the resulting msieve.datX.m file, it shouldn't be very large. Thanks in advance... Last fiddled with by jasonp on 2011-04-24 at 15:15 Reason: datX -> logX (thanks Serge)

2011-04-21, 15:47	#2
ET_ Banned "Luigi" Aug 2002 Team Italia 43×113 Posts	I'm in... Code: error (line 197): CUDA_ERROR_FILE_NOT_FOUND I'm running CUDA 3.0 on Ubuntu x86_64. Luigi Last fiddled with by ET_ on 2011-04-21 at 16:25

2011-04-21, 19:15	#3
jasonp Tribal Bullet Oct 2004 3,559 Posts	Do you have .ptx files in the current working directory? It sounds like they can't be found...

2011-04-22, 01:09	#7
jasonp Tribal Bullet Oct 2004 3,559 Posts	The advantage to RSA768 over all the other similarly large numbers is that we have a known high-quality polynomial to compare against, the result of many machine-decades of computation that nobody has been able to beat (yet) even with more powerful algorithms. It doesn't matter to me at all that RSA768 is finished, since I wouldn't try to actually proceed with the sieving even if the target was unfactored.

2011-04-22, 04:45	#9
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10092₁₀ Posts	These are not really "poly"s. (It's a misnomer. They are 1st stage candidates.) What you would like to see is "save"s. ...Oh, wait, this is -np1. These are good. Last fiddled with by Batalov on 2011-04-22 at 04:58 Reason: my bad

2011-04-22, 10:36	#11
jasonp Tribal Bullet Oct 2004 3,559 Posts	Yes, the resource use of the GPU code is pretty noticeable, and I'll understand if you want to switch to the CPU version instead. I'll take anything between 10^4 and 10^9.