C166 from 10^455-1?

Stargate38 · 2011-12-16, 18:48

Why didn't anyone factor the cofactor of (10⁴⁵⁵-1)/(10⁹¹-1) yet? It's well within the range of GNFS or SNFS.

Here's the decimal expansion (166 digits):

Code:

4550956748305222152126018815762238940620303956367340855900091266114182783163428849423951840315664063783883817473128035867761145293485421290359307345105428632108260961

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

jasonp · 2011-12-16, 18:57

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

Stargate38 · 2011-12-16, 18:58

I found it here:
http://www.factordb.com/index.php?id...00000013095705

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

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

Batalov · 2011-12-16, 19:05

Quote:

Originally Posted by Stargate38

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

Because it is relatively hard -
http://homepage2.nifty.com/m_kamada/...ds.htm#BIGGNFS

There are more wanted similar-sized projects.

Stargate38 · 2011-12-16, 19:08

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?

Batalov · 2011-12-16, 19:18

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

fivemack · 2011-12-16, 20:51

Quote:

Originally Posted by Stargate38

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?

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.

Stargate38 · 2011-12-16, 22:16

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.

Batalov · 2011-12-16, 22:47

Yes they do. But this is not a Cunningham number!

On Kamada's site, you will find some useful plots ...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)

fivemack · 2011-12-16, 22:53

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

Stargate38 · 2011-12-17, 00:49

I only have 4 GB of RAM (can't afford to buy more

), along with the pagefile. Is a team sieve possible? I've seen it done with other numbers (ie. numbers from Aliquot Sequences).

2011-12-16, 18:48	#1
Stargate38 "Daniel Jackson" May 2011 14285714285714285714 2³·83 Posts	C166 from 10^455-1? Why didn't anyone factor the cofactor of (10⁴⁵⁵-1)/(10⁹¹-1) yet? It's well within the range of GNFS or SNFS. Here's the decimal expansion (166 digits): Code: 4550956748305222152126018815762238940620303956367340855900091266114182783163428849423951840315664063783883817473128035867761145293485421290359307345105428632108260961 This number has been left unfactored for at least 1 year. It could have been factored by now. Why isn't it factored yet?

2011-12-16, 18:58	#3
Stargate38 "Daniel Jackson" May 2011 14285714285714285714 2³·83 Posts	I found it here: http://www.factordb.com/index.php?id...00000013095705 It's also on other sites such as this one: http://homepage2.nifty.com/m_kamada/math/11111.htm They're factoring repunits and near-repdigits, but they haven't factored that c166. Why? Last fiddled with by Stargate38 on 2011-12-16 at 19:01 Reason: Added another site.

2011-12-16, 19:08	#5
Stargate38 "Daniel Jackson" May 2011 14285714285714285714 2³×83 Posts	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? Last fiddled with by Stargate38 on 2011-12-16 at 19:17

2011-12-16, 22:16	#8
Stargate38 "Daniel Jackson" May 2011 14285714285714285714 2³×83 Posts	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. Last fiddled with by Stargate38 on 2011-12-16 at 22:20

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Team sieve #26: c166 from 4788:2661	jrk	Aliquot Sequences	38	2011-05-16 17:58
ECM for c166 from 4788:2661	frmky	Aliquot Sequences	36	2011-04-28 06:27
Team sieve #25: c166 from 4788:2632	jrk	Aliquot Sequences	13	2011-03-24 02:48
ECM work on 4788:2632 c166	schickel	Aliquot Sequences	8	2011-03-05 01:11
Team sieve #22: c166 from 3270:620	fivemack	Aliquot Sequences	55	2011-02-15 23:01

2011-12-16, 18:57	#2
jasonp Tribal Bullet Oct 2004 6727₈ Posts	Do the main 10- tables in the Cunningham Project go over 10^400?

2011-12-16, 19:18	#6
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×47×101 Posts	Ever? I have no doubts about it. 2013, 2014, by almost anyone while doing school homework in parallel.

2011-12-16, 22:47	#9
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·47·101 Posts	Yes they do. But this is not a Cunningham number! On Kamada's site, you will find some useful plots ...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)

2011-12-16, 22:53	#10
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 14427₈ Posts	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

2011-12-17, 00:49	#11
Stargate38 "Daniel Jackson" May 2011 14285714285714285714 1010011000₂ Posts	I only have 4 GB of RAM (can't afford to buy more ), along with the pagefile. Is a team sieve possible? I've seen it done with other numbers (ie. numbers from Aliquot Sequences).