C166 from 10^455-1?
 

Why didn't anyone factor the cofactor of (10[SUP]455[/SUP]-1)/(10[SUP]91[/SUP]-1) yet? It's well within the range of GNFS or SNFS.

Here's the decimal expansion (166 digits):

[CODE]4550956748305222152126018815762238940620303956367340855900091266114182783163428849423951840315664063783883817473128035867761145293485421290359307345105428632108260961[/CODE]

This number has been left unfactored for at least 1 year. It could have been factored by now. Why isn't it factored yet?

Do the main 10- tables in the Cunningham Project go over 10^400?

I found it here:
[URL]http://www.factordb.com/index.php?id=1100000000013095705[/URL]

It's also on other sites such as this one:
[URL]http://homepage2.nifty.com/m_kamada/math/11111.htm[/URL]

They're factoring repunits and near-repdigits, but they haven't factored that c166. Why?

[QUOTE=Stargate38;282457]...They're factoring repunits and near-repdigits, but they haven't factored that c166. Why?[/QUOTE]
Because it is relatively hard -
[URL]http://homepage2.nifty.com/m_kamada/math/records.htm#BIGGNFS[/URL]

There are [URL="http://homes.cerias.purdue.edu/~ssw/cun/want122"]more wanted[/URL] similar-sized projects.

Is anyone ever going to SNFS this number? It's small compared to most number factored by SNFS during the past year. It wouldn't even take a year to GNFS. Anyone have a good poly?

Ever? I have no doubts about it. 2013, 2014, by almost anyone while doing school homework in parallel. :smile:

[QUOTE=Stargate38;282462]Is anyone ever going to SNFS this number? It's small compared to most number factored by SNFS during the past year. It wouldn't even take a year to GNFS. Anyone have a good poly?[/QUOTE]

What kind of resources do you have access to? It will take about one CPU-year to GNFS; so a season if you've got a quad-core, or a month on a fairly heavy (dual six-core Xeon) workstation. msieve and gnfs-lasieve4I15e have been tested thoroughly in this sort of size range; you are unlikely to run into unforeseen road-blocks. You can likely do it yourself, it's a bit big as a first factorisation project but entirely practicable. Feel free to ask any of us for advice.

I don't have my computer on 24/7. I have a dual-core AMD Athlon and the longest factorization I've ever done is about 100 minutes on a 91 digit number using SIQS. How do you calculate the time that it takes for NFS factorization? I need an equation. I can't keep my computer on 182.5 days (365 days split between dual-core) nonstop because I get bad storms, on average every 90 days year-round. How long would NFS@Home take to factor it? They do Cunningham numbers all the time.

Yes they do. But this is [I]not[/I] a Cunningham number!

On Kamada's site, you will find some [URL="http://homepage2.nifty.com/m_kamada/math/gnfs_time.png"]useful plots[/URL] ...and even a formula.
(Of course, it is for a general estimate only and for any individual set of computers, the estimate may be within ~1/3x to ~3x)

NFS@home could probably do it overnight, but it's not big enough to be worth using their resources on; it's the same sort of question as 'how quickly can you get to the shops by space-shuttle', where the answer is 'it would be daft to go to the shops by space-shuttle'.

Sieving is a perfectly parallel process, which means you can do it in almost arbitrarily small chunks and you will lose only small quantities of work with each power outage.

I fear you don't really have enough compute power to do this job without getting frustrated: you really need to be running 64-bit Linux, if only in a VM; you really need 8GB or so of memory; more than two cores would be great.

How do you calculate the time for GNFS? Well, you do a lot of factorisations and fit a curve. I've done a lot of factorisations and fitted a curve, and get

about 100 CPU-hours for 130 digits
multiply by three for every ten digits after that

I only have 4 GB of RAM (can't afford to buy more :sad:), along with the pagefile. Is a team sieve possible? I've seen it done with other numbers (ie. numbers from Aliquot Sequences).

[QUOTE=Stargate38;282462]Is anyone ever going to SNFS this number? It's small compared to most number factored by SNFS during the past year. It wouldn't even take a year to GNFS. Anyone have a good poly?[/QUOTE]

It is [b]ENORMOUS[/b] for SNFS!!!!!!!!! It is way beyond even M1061.

10,455-, 3,710+ and 3,616+ (I see that 3,608+ has been factored) can be sieved by RSALS, using 14e.
15e would probably be marginally faster (I know that Aliquot team sievings on MersenneForum usually use 15e above GNFS difficulty 163), but RSALS can sometimes yield a factorization more quickly, because it usually has more core than team sievings.

But 3,710+ and 3,616+ might be reserved, or being worked on at the time being ?

[QUOTE=R.D. Silverman;282517]It is [b]ENORMOUS[/b] for SNFS!!!!!!!!! It is way beyond even M1061.[/QUOTE]I suspect he's comparing the C166 with the C2xx and even C3xx which have been factored by SNFS. Many people here know why that's a false comparison but we all have to learn sometime.

Stargate33: as a rule of thumb, SNFS only works on the full number to be factored, 10^455-1 in this case, and it usually can't exploit any known factors. There are exceptions but it's a good rule of thumb. 10^455-1 has 455 digits and, as Bob says, 455 is much larger than anything yet done by SNFS.

Paul

[QUOTE=xilman;282571]I suspect he's comparing the C166 with the C2xx and even C3xx which have been factored by SNFS. Many people here know why that's a false comparison but we all have to learn sometime.

Stargate33: as a rule of thumb, SNFS only works on the full number to be factored, 10^455-1 in this case, and it usually can't exploit any known factors. There are exceptions but it's a good rule of thumb. 10^455-1 has 455 digits and, as Bob says, 455 is much larger than anything yet done by SNFS.

Paul[/QUOTE]

In this case you can divide out the algebraic factor (10^91-1) to get:

[code]n: 4550956748305222152126018815762238940620303956367340855900091266114182783163428849423951840315664063783883817473128035867761145293485421290359307345105428632108260961
skew: 1
c4 1
c3 1
c2 1
c1 1
c0 1
Y1 1
Y0 -10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
rlim: 500000000
alim: 500000000
lpbr: 35
lpba: 35
rlambda: 2.6
alambda: 2.6
mfbr: 70
mfba: 70
#sieve with the 16e siever for at least a billion relations
#parameters are just a guesstimate
[/code]

but that's still SNFS-difficulty 365(!) and thus far out of range for home computing. GNFS-166 is waaaay easier (and should doable with a single intel i7 with enough RAM and a user with enough patience.)

[QUOTE=debrouxl;282559]10,455-, 3,710+ and 3,616+ (I see that 3,608+ has been factored) can be sieved by RSALS, using 14e.
15e would probably be marginally faster (I know that Aliquot team sievings on MersenneForum usually use 15e above GNFS difficulty 163), but RSALS can sometimes yield a factorization more quickly, because it usually has more core than team sievings.

But 3,710+ and 3,616+ might be reserved, or being worked on at the time being ?[/QUOTE]
This info is available at
[url]http://homes.cerias.purdue.edu/~ssw/cun/who[/url]
the "who is factoring ..." page (for Cunningham numbers). We added
3,616+ shortly after finishing 3,608+ (an ecm cofactor). I'm frequently
checking to make sure that I'm not running ecm on numbers someone
else is sieving --- I just recently trimmed 3 of 37 from the extension with
163-233 digits. At the moment, 3,710+ is open. I'm usually sieving
larger/harder numbers (5p237 sieving finished, matrix running; 11p271
paused), and have scripts for 15e and 16e, but not 14e.

Bruce (as in Batalov+Dodson)

That must mean that GNFS is faster than SNFS in this case. Is this number on RSALS todo list? If not, I really want it factored as fast as possible. Anyone want to do it? I don't have the 8 GB of memory required. :( What's the fastest way of GNFS'ing this? How do you calculate SNFS difficulty?

[B]Why[/B] do you want this number factored?

To get some order of magnitude of the favour that you are asking, I estimate that it would take between fifteen and twenty days to factor it on my large server, and cost therefore about a hundred dollars in electricity and about fifty dollars in depreciation of the server. If you're willing to pay for that I will drop everything and factor it on my large server, but bear in mind that $150 would buy you the extra memory that you lack.

[QUOTE=Stargate38;282614]Is this number on RSALS todo list?[/QUOTE]

How much ECM has been done? I can't speak for RSALS, but they have often factored adequately pre-tested numbers for other projects.

It's customary to do ECM through 1/3 of the number size before GNFS. That is about 24,000 curves with B1=11e7, or 70,500 with B1=43e6, or 10,000 with B1=26e7, or some equivalent combination. Everybody will want that much ECM before GNFS to make it unlikely there are small factors that are more easily found with ECM.

If that sounds like a lot of computing, remember that it is much smaller than the GNFS factoring that you are asking for. Are you sufficiently interested to do the ECM work yourself? If so, then politely ask debrouxl if RSALS would do the GNFS if the ECM fails to find a factor.

[QUOTE=fivemack;282615][B]Why[/B] do you want this number factored?

To get some order of magnitude of the favour that you are asking, I estimate that it would take between fifteen and twenty days to factor it on my large server, and cost therefore about a hundred dollars in electricity and about fifty dollars in depreciation of the server. If you're willing to pay for that I will drop everything and factor it on my large server, but bear in mind that $150 would buy you the extra memory that you lack.[/QUOTE]I'd be willing to pay $5 if you factored it and then posted the factors a digit at a time over the course of a week...:missingteeth:

[QUOTE=wblipp;282631]How much ECM has been done? I can't speak for RSALS, but they have often factored adequately pre-tested numbers for other projects.

It's customary to do ECM through 1/3 of the number size before GNFS. That is about 24,000 curves with B1=11e7, or 70,500 with B1=43e6, or 10,000 with B1=26e7, or some equivalent combination. Everybody will want that much ECM before GNFS to make it unlikely there are small factors that are more easily found with ECM.

If that sounds like a lot of computing, remember that it is much smaller than the GNFS factoring that you are asking for. Are you sufficiently interested to do the ECM work yourself? If so, then politely ask debrouxl if RSALS would do the GNFS if the ECM fails to find a factor.[/QUOTE]I'd run some ECM work for $5 or so (then I could pay Tom.....:whistle:)

ECM up to 1/3 of GNFS difficulty (William's numbers) may be a bit much, but indeed, I wouldn't queue a GNFS 166 to RSALS before it has received, say, half, or two thirds, of t55, i.e. 9000 or 12000 curves at B1=11e7 (or equivalent). That's quite a bit of work...

If no one else wants it I'll have a go. It'll take me about 6 weeks though, excluding ECM.

It's obviously had enough ECM to find the 45 digit factor. Does anyone know how much more it has had?

It'll be about a week before my current work on the Brent tables is done. If anyone wants run some ECM on it I'll be grateful (Friday morning would be about the latest before I start work).

Chris K

[QUOTE=chris2be8;282695]If no one else wants it I'll have a go. It'll take me about 6 weeks though, excluding ECM.

It's obviously had enough ECM to find the 45 digit factor. Does anyone know how much more it has had?

It'll be about a week before my current work on the Brent tables is done. If anyone wants run some ECM on it I'll be grateful (Friday morning would be about the latest before I start work).

Chris K[/QUOTE]I can set up to run some curves @ 43M (I did, in fact). I've only got 1 core running ECM locally, but my server is available at aliquot.homeftp.org:8194 for those who are interested.

I've set my systems up to start running ECM to c55 tomorrow. I'll let that run for a week or two (depending how much ECM other people do), then start GNFS. I'm away until next week so won't be responding for a few days.

Thanks in advance to anyone running ECM and Happy Christmas to everyone.

Chris K

[QUOTE=chris2be8;283186]I've set my systems up to start running ECM to c55 tomorrow. I'll let that run for a week or two (depending how much ECM other people do), then start GNFS. I'm away until next week so won't be responding for a few days.

Thanks in advance to anyone running ECM and Happy Christmas to everyone.

Chris K[/QUOTE]I ran ~200 @ 43M and am running some @ 110M now; I've got maybe 120 so far. (I can do 48 curves/day with my 1 core....I could up that a little if I move one box I have sitting idle over to ECM.)

Have a safe and Merry Christmas!

[QUOTE=schickel;283203]I ran ~200 @ 43M and am running some @ 110M now; I've got maybe 120 so far. (I can do 48 curves/day with my 1 core....I could up that a little if I move one box I have sitting idle over to ECM.)[/quote]I put another core on ECM, and Ralf Recker lent some curves. As of Tuesday there are ~700 curves @110M between the two of us (most his).

Hello,

I've done about 8000 curves at 110M so it's time to start sieving. Polynomial selection is now running on all 8 cores.

Thanks for the curves you've run.

Chris K

[QUOTE=chris2be8;283927]Hello,

I've done about 8000 curves at 110M so it's time to start sieving. Polynomial selection is now running on all 8 cores.

Thanks for the curves you've run.

Chris K[/QUOTE]Sounds good. It'll be an hour or so before I can turn it off. (Maybe we'll have a lucky strike in that time!)

Polynomial selected. Sieving now in progress, it'll probably finish in February.

Chris K

[QUOTE=chris2be8;284249]Polynomial selected. Sieving now in progress, it'll probably finish in February.

Chris K[/QUOTE]How many cores do you have? I'm doing a c166 that I started 11/29 and I'm almost done with it using 8 cores.....

I've got 8 cores in total, 1 6 core box and 1 2 core box. I'm getting about 2M relations in 14 hours so it may finish sieving in late January (it depends if the rate slows down later in the range and how many relations I need). Then add a few days for LA etc.

Chris K

[QUOTE=chris2be8;284363]I've got 8 cores in total, 1 6 core box and 1 2 core box. I'm getting about 2M relations in 14 hours so it may finish sieving in late January (it depends if the rate slows down later in the range and how many relations I need). Then add a few days for LA etc.

Chris K[/QUOTE]Same setup here.....I'm running 31-bit lpba/r, and it's looking like it's going to need ~120M unique. I'm getting almost 3M/day and had 98M unique last time I ran a cycle count (yesterday), so it looks like you're in the ballpark.

[QUOTE=chris2be8;284363]I've got 8 cores in total, 1 6 core box and 1 2 core box. I'm getting about 2M relations in 14 hours so it may finish sieving in late January (it depends if the rate slows down later in the range and how many relations I need). Then add a few days for LA etc.

Chris K[/QUOTE]OK, finally got there. I've got 118M+ unique relations and 126M+ unique ideals.

I've got some relations on the other sieving machine that I'm going to toss in the mix in hopes of a little better matrix. I'll give you an ETA later on today....

False alarm! :cry:[quote=msieve]

commencing 2-way merge
reduce to 16890789 relation sets and 16635945 unique ideals
ignored 25 oversize relation sets
commencing full merge
memory use: 1909.9 MB
found 8544888 cycles, need 8524145
weight of 8524145 cycles is about 681972507 (80.00/cycle)
.....
commencing linear algebra
read 8524145 cycles
cycles contain 30396095 unique relations
read 30396095 relations
using 20 quadratic characters above 2147483270
building initial matrix
memory use: 4037.7 MB
read 8524145 cycles
matrix is 8523965 x 8524145 (2924.2 MB) with weight 907100851 (106.42/col)
sparse part has weight 664259727 (77.93/col)
filtering completed in 2 passes
matrix is 8515163 x 8511169 (2923.2 MB) with weight 906745720 (106.54/col)
sparse part has weight 664174894 (78.04/col)
matrix starts at (0, 0)
matrix is 8515163 x 8511169 (2923.2 MB) with weight 906745720 (106.54/col)
sparse part has weight 664174894 (78.04/col)
matrix needs more columns than rows; try adding 2-3% more relations[/quote]:max: :max: :max:

You are right on the edge of having enough relations. There's a small region where filtering will succeed but a little extra filtering inside the linear algebra will cause the job to fail. Add some more relations and you'll get past the danger zone. Add a few more relations after that and you can knock 10-15% off the size of the matrix, though whether that will reduce the total time to completion depends on how fast you can sieve.

Do you have an ETA? This number is #5 among the 10 smallest composites in the Repunit Factorizations:

[URL]http://homepage2.nifty.com/m_kamada/math/11111.htm[/URL]

I love to see the new factors. It makes me happy. :smile:

Man is the artificer of his own happiness. Artifice something, dude, and be happy!

Why doesn't complete factorization of 10^397-1 make you happy instead? That is a sizeable achievement!*
__________

[SIZE=1]* [URL="http://en.wikipedia.org/wiki/Littlewood%27s_law"]John Littlewood[/URL] while proof-reading a passage in a draft of a book noted once: "I wish I had said that". To his surprise, the final print said: "John Littlewood said:..." The printer's apprentice took his remark for the face value. :-) /a.f.a.i.r. from M.Gardner's book/[/SIZE]

I like factorizations of any number, especially repunits and large numbers of the form k*2^n+x, such as 8675309*2^2154+2 which is 2*(8675309*2^2153+1) (Link for the second factor: [URL]http://www.factordb.com/index.php?id=1100000000486883929[/URL]). Also I like finding Generalized Fermat primes, such as 1494^256+1 (Link: [URL]http://www.factordb.com/index.php?id=1100000000475946832[/URL]).

[QUOTE=Stargate38;287374]Also I like finding Generalized Fermat primes, such as 1494^256+1 (Link: [URL]http://www.factordb.com/index.php?id=1100000000475946832[/URL]).[/QUOTE]

Before spending much time in finding GF primes, have a look at [url=http://yves.gallot.pagesperso-orange.fr/primes/results.html]here[/url].

Are there any primes of the form 626[sup]2[sup]n[/sup][/sup]+1? I used Proth and didn't find any up to n=16. Also, Why does NewPGen crash when I try to sieve b^n+k with k=1 and b=8675310? See attatched image.

[QUOTE=Stargate38;287363]Do you have an ETA?[/QUOTE]

Linear algebra should finish in about 28 hours.So I should be able to post the factors on Sunday.

Chris K

PS. Is anyone working on R870? I could take that as my next challenge.

You may want to email M.Kamada - he doesn't read these forums, but he is in contact with half a dozen active repunit factorers. He would know. There are no reservations for these though.

[URL]http://homepage2.nifty.com/m_kamada/math/11111.htm[/URL]
See 'Sources' and 'Recent Changes' sections.

Also, if you do want to take on a c162, then why not on a Wanted Cunningham c163? It was deliberately left for enthusiasts.

[QUOTE=Stargate38;287363]Do you have an ETA? This number is #5 among the 10 smallest composites in the Repunit Factorizations:

[URL]http://homepage2.nifty.com/m_kamada/math/11111.htm[/URL]

I love to see the new factors. It makes me happy. :smile:[/QUOTE][QUOTE=schickel;282649]I'd be willing to pay $5 if you factored it and then posted the factors a digit at a time over the course of a week...:missingteeth:[/QUOTE]This offer is still open....:grin:

Sun Jan 29 00:17:21 2012 prp75 factor: 139397282236319122569927698220829009751930337603755594300386510230285560351
Sun Jan 29 00:17:21 2012 prp92 factor: 32647385051525041661479792654516355809315046496410663779745524799749707387460867800164362111

Chris K

PS. M. Kamada hasn't heard of anyone else working on R870 so I'll start on it. I think ECM to 50 digits is enough, T55 would take about two weeks for a 10% chance of a factor while GNFS will take 4-5 weeks for a 100% chance.

I think you should chat with Yousuke Koide first before you start the fatoring of M870, he has done 18400@12e7 of M870, and this number is marked with (reserved GNFS) ,
the url is
[url]http://www.h4.dion.ne.jp/~rep/table3.htm[/url]
you can have his email from [url]http://www.h4.dion.ne.jp/~rep/[/url]

Bo Chen

FWIW, my computer ran 673 curves at B1=11e6 before I saw your message and ended the tasks.
No factor found, unsurprisingly, if the number has already received more than t55 ECM work :smile:

[QUOTE=Batalov;287445]Also, if you do want to take on a c166 [strike]c162[/strike], then why not on a Wanted Cunningham c163? It was deliberately left for enthusiasts.[/QUOTE]
This is a much safer offer. This number ([URL="http://homes.cerias.purdue.edu/%7Essw/cun/want122"]3^710+1 cofactor[/URL]) is still unreserved - write to Sam.

OK, I'll leave it to Yousuke Koide. He reserved it first.

Chris