Factoring humongous Cunningham numbers - Page 115

Batalov · 2015-05-20, 01:50

Six years ago I did not know many things. But that's ok. I am as clever as I was back them - I still don't know those things.

I thought about octics from time to time.
But let's consider - where do they come from?
1. They trivially come forward if you can take sqrt of x and double all degrees. You turn a quartic into an octic with no benefit in size. That's almost never good (except if the number was _very_ large; I thought that 2,1100+ is almost that large, but no!).
2. If you use cyclotomic polcyclo(5) and the Aurifeuillian for base 2, your get an octic foldable into a quartic. Cf. #1, same situation.
3. They happen to be around if you can use the cyclotomic polcyclo(3) and get you difficulty down 1.5x times. (Your starting polynomial may already have some reduction in size - either as an Aurifeuillian or from polcyclo(5); then you get an octic. If you had polcyclo(21), then you are fine because its degree is 12 and then you fold it reciprocally into degree 6, but with from polcyclo(15) you get a degree 8). Unfortunately and naturally, the cofactor will be even more than 1.5x less than that difficulty, so from the point of view of the raw polynomial the cofactor always looks like a GNFS to begin with.
4. They can be made from polcyclo(17); that is almost as bad as #1, -- the gain is only 1/17th of difficulty and the reward is hard to see.

What about degree 7 polynomials? Well, they never happen because degree of cyclotomic is never 7.

Quartics are hard for large size (and growing harder with size). Why do people then even use quartics? Well, they still provide a 1.25x reduction in size, and then even if you didn't use quartic, you cannot use quintic (it will be reducible and the siever will be not working properly) - you then have to use sextic with some residual degree (b^(n%6)) going into c6 and making for an irreducible poly. For some (smaller) sizes, sextic will be more painful than quartic. So, hence, quartic.

Not all numbers really have to be done necessarily today or tomorrow - just leave them for the future: either the computers will become more powerful and these projects will be peanuts in 2020, or some new theory will get advanced. My 2 cents.

LaurV · 2015-05-20, 02:32

Quote:

Originally Posted by Batalov

I thought about octics from time to time.
But let's consider - where do they come from? <snip>

Very good post, it clarified few things for me (and muddied few others, but we are still struggling with it, don't tell to these guys!) I like when people get explanatory. (No irony!). Thanks Serge.

jyb · 2015-05-20, 04:06

Quote:

Originally Posted by Batalov

Six years ago I did not know many things. But that's ok. I am as clever as I was back them - I still don't know those things.

Same here. I like to imagine that I know more now than I did then, but I could be fooling myself.

Quote:

Originally Posted by Batalov

I thought about octics from time to time.
But let's consider - where do they come from?

Yes, I've pondered the same question. It's why I began this discussion and started experimenting.

Quote:

Originally Posted by Batalov

1. They trivially come forward if you can take sqrt of x and double all degrees. You turn a quartic into an octic with no benefit in size. That's almost never good (except if the number was _very_ large; I thought that 2,1100+ is almost that large, but no!).
2. If you use cyclotomic polcyclo(5) and the Aurifeuillian for base 2, your get an octic foldable into a quartic. Cf. #1, same situation.
4. They can be made from polcyclo(17); that is almost as bad as #1, -- the gain is only 1/17th of difficulty and the reward is hard to see.

Yup, I'm with you on these.

Quote:

Originally Posted by Batalov

3. They happen to be around if you can use the cyclotomic polcyclo(3) and get you difficulty down 1.5x times. (Your starting polynomial may already have some reduction in size - either as an Aurifeuillian or from polcyclo(5); then you get an octic. If you had polcyclo(21), then you are fine because its degree is 12 and then you fold it reciprocally into degree 6, but with from polcyclo(15) you get a degree 8). Unfortunately and naturally, the cofactor will be even more than 1.5x less than that difficulty, so from the point of view of the raw polynomial the cofactor always looks like a GNFS to begin with.

I may be misunderstanding you here, but I'm not sure I agree with your conclusion. The examples I gave have a difficulty 1.5x less because of dividing out the algebraic factor. The actual primitive is indeed more than 1.5x less, but only by a tiny bit, so it's possible that an octic ends up doing better than GNFS.

But also, you're missing another set of numbers:
5. Aurefeuillian splits for certain cyclotomic numbers (and their homogeneous versions). Specifically, consider 30^n+1, 10^n+3^n and 6^n+5^n, all with n a multiple of 30.

In these cases, the natural polynomial has degree 16, so can be folded to an octic. There's no other SNFS polynomial at all (of reasonable degree).

Quote:

Originally Posted by Batalov

What about degree 7 polynomials? Well, they never happen because degree of cyclotomic is never 7.

Quartics are hard for large size (and growing harder with size). Why do people then even use quartics? Well, they still provide a 1.25x reduction in size, and then even if you didn't use quartic, you cannot use quintic (it will be reducible and the siever will be not working properly) - you then have to use sextic with some residual degree (b^(n%6)) going into c6 and making for an irreducible poly. For some (smaller) sizes, sextic will be more painful than quartic. So, hence, quartic.

Not all numbers really have to be done necessarily today or tomorrow - just leave them for the future: either the computers will become more powerful and these projects will be peanuts in 2020, or some new theory will get advanced. My 2 cents.

Thank you for your thoughts. I really appreciate it.

BTW, have you ever used msieve to post-process an octic before? When I was trying a few days ago, it consistently crashed.

Batalov · 2015-05-20, 07:15

Quote:

Originally Posted by jyb

BTW, have you ever used msieve to post-process an octic before? When I was trying a few days ago, it consistently crashed.

Yes, I have. (I've even written some little thing for the Duff's device that used to be in the sqrt phase.)
It should work. Worked for me. What stage did it crash on?

jyb · 2015-05-20, 13:50

Quote:

Originally Posted by Batalov

Yes, I have. (I've even written some little thing for the Duff's device that used to be in the sqrt phase.)
It should work. Worked for me. What stage did it crash on?

Almost immediately after starting filtering. It said "commencing number field sieve..." and then seg-faulted before printing out the polynomials. I'll debug it sometime when I have the chance.

jyb · 2015-05-22, 04:40

Quote:

Originally Posted by jyb

Almost immediately after starting filtering. It said "commencing number field sieve..." and then seg-faulted before printing out the polynomials. I'll debug it sometime when I have the chance.

I had the chance.

xilman · 2015-06-12, 18:13

Apologies for not posting an update a couple of weeks ago. Other issues have intervened.

In the last 6 weeks another 18 factors have been reported, as given below. There are now 171 composites remaining in the tables so it's still possible that extensions will be added later this year. If the rate of 12 factors a month is (slightly) exceeded, the number of composites will be less than 100 by the end of 2015.

As always, my thanks to everyone who attempts to factor these integers.

Paul

Code:

8+7	251	C214	124615696353637706346546040754622082470604333132075533125685330753699961.	P143				J Becker		SNFS	2015-04-27
8+3	251	C219	364482679535460879253091202241643481038274886715777426276466844003697747156558134569151.	P133		J Becker		SNFS	2015-04-29
7+3	268	C184	106592190577726524744988734993053670086708968918376809.	P131							J Becker		SNFS	2015-05-02
10-9	227	C184	120132540928134839142904430999870926995810271171800873874601.	P125						J Becker		SNFS	2015-05-04
11+10	214	C189	586364757765566648538746443532551233500982915886177485689.	P133						R Silverman		SNFS	2015-05-04
10+9	227	C188	182321598911891021114527349799283914816952526461160810192988619121.	P123					J Becker		SNFS	2015-05-06
10+7	227	C170	133910433815804634290469166668134079538767088257374332405279.	P111						J Becker		SNFS	2015-05-12
11+3	218	C209	250281729227434261873262955329217235451846973385994100895366500929.	P144					R Silverman		SNFS	2015-05-14
10+3	227	C215	48741045575797633093659494864518596314104861670104807109533.	P156						J Becker		SNFS	2015-05-15
6+5	292	C224	415244518612622353198574801831649522570969069240496328152775187091507061920420316681.	P141			J Becker		SNFS	2015-05-18
7+3	269	C180	430535257354776817116314402840418660829247957429115016692389378099125139711793043297.	P97			J Becker		SNFS	2015-05-22
7-3	269	C194	203727509055352490967755188685019578245967838439247.	P144							J Becker		SNFS	2015-05-25
7-6	269	C186	46371992318174057132565752141850585842171120664002856319.	P130						J Becker		SNFS	2015-05-29
7+6	269	C191	368618548036826427068768349588872729894268216276635272271.	P134						J Becker		SNFS	2015-05-31
11+6	218	C171	81640967883107148980963460944963100207700944025175617.	P119							R Silverman		SNFS	2015-06-01
7+5	269	C190	95669271746639625406375028201801227629711003767068507.	P137							J Becker		SNFS	2015-06-04
7-4	269	C194	1614839673351561669883444051370535550671580371721183888271230576777.	P127					J Becker		SNFS	2015-06-09
6+5	293	C197	125030764214362844726887694353021492610352646449541334275343243613159548097447618845315994101.	P105		J Becker		SNFS	2015-06-10

jyb · 2015-06-12, 21:04

Quote:

Originally Posted by xilman

Apologies for not posting an update a couple of weeks ago. Other issues have intervened.

In the last 6 weeks another 18 factors have been reported, as given below. There are now 171 composites remaining in the tables so it's still possible that extensions will be added later this year. If the rate of 12 factors a month is (slightly) exceeded, the number of composites will be less than 100 by the end of 2015.

As always, my thanks to everyone who attempts to factor these integers.

Paul

Code:

8+7	251	C214	124615696353637706346546040754622082470604333132075533125685330753699961.	P143				J Becker		SNFS	2015-04-27
8+3	251	C219	364482679535460879253091202241643481038274886715777426276466844003697747156558134569151.	P133		J Becker		SNFS	2015-04-29
7+3	268	C184	106592190577726524744988734993053670086708968918376809.	P131							J Becker		SNFS	2015-05-02
10-9	227	C184	120132540928134839142904430999870926995810271171800873874601.	P125						J Becker		SNFS	2015-05-04
11+10	214	C189	586364757765566648538746443532551233500982915886177485689.	P133						R Silverman		SNFS	2015-05-04
10+9	227	C188	182321598911891021114527349799283914816952526461160810192988619121.	P123					J Becker		SNFS	2015-05-06
10+7	227	C170	133910433815804634290469166668134079538767088257374332405279.	P111						J Becker		SNFS	2015-05-12
11+3	218	C209	250281729227434261873262955329217235451846973385994100895366500929.	P144					R Silverman		SNFS	2015-05-14
10+3	227	C215	48741045575797633093659494864518596314104861670104807109533.	P156						J Becker		SNFS	2015-05-15
6+5	292	C224	415244518612622353198574801831649522570969069240496328152775187091507061920420316681.	P141			J Becker		SNFS	2015-05-18
7+3	269	C180	430535257354776817116314402840418660829247957429115016692389378099125139711793043297.	P97			J Becker		SNFS	2015-05-22
7-3	269	C194	203727509055352490967755188685019578245967838439247.	P144							J Becker		SNFS	2015-05-25
7-6	269	C186	46371992318174057132565752141850585842171120664002856319.	P130						J Becker		SNFS	2015-05-29
7+6	269	C191	368618548036826427068768349588872729894268216276635272271.	P134						J Becker		SNFS	2015-05-31
11+6	218	C171	81640967883107148980963460944963100207700944025175617.	P119							R Silverman		SNFS	2015-06-01
7+5	269	C190	95669271746639625406375028201801227629711003767068507.	P137							J Becker		SNFS	2015-06-04
7-4	269	C194	1614839673351561669883444051370535550671580371721183888271230576777.	P127					J Becker		SNFS	2015-06-09
6+5	293	C197	125030764214362844726887694353021492610352646449541334275343243613159548097447618845315994101.	P105		J Becker		SNFS	2015-06-10

Thanks for the update, Paul. It looks like your site hasn't actually updated yet.

debrouxl · 2015-06-13, 06:33

Hot on the heels of your update, the first of 6 numbers sieved by NFS@Home is fully factored

http://www.mersenneforum.org/showpos...&postcount=208
http://factordb.com/index.php?id=1100000000469481596

Code:

7-5	293	C231 369949332999429058969069423566453026066929418980094327655796551034582876227213807384578477111027.	P136 NFS@Home + Victor de Hollander	SNFS	2015-06-13

pinhodecarlos · 2015-06-14, 20:45

I'm reaching a point were my cores are not efficient on running LLR so I was thinking to put them on 14e sieve for NFS@Home. How much ecm was done on this 117 composites?

R.D. Silverman · 2015-06-15, 12:45

Quote:

Originally Posted by pinhodecarlos

I'm reaching a point were my cores are not efficient on running LLR so I was thinking to put them on 14e sieve for NFS@Home. How much ecm was done on this 117 composites?

Noone has accurate data.

2015-06-13, 06:33	#1263
debrouxl Sep 2009 977 Posts	Hot on the heels of your update, the first of 6 numbers sieved by NFS@Home is fully factored http://www.mersenneforum.org/showpos...&postcount=208 http://factordb.com/index.php?id=1100000000469481596 Code: 7-5 293 C231 369949332999429058969069423566453026066929418980094327655796551034582876227213807384578477111027. P136 NFS@Home + Victor de Hollander SNFS 2015-06-13

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New phi for homogeneous Cunningham numbers	wpolly	Factoring	26	2016-07-29 04:34
Mathematics of Cunningham Numbers (3rd ed., 2002, A.M.S.)	Xyzzy	Cunningham Tables	42	2014-04-02 18:31
Don't know how to work on Cunningham numbers.	jasong	GMP-ECM	6	2006-06-30 08:51
Doing Cunningham numbers but messed up.	jasong	Factoring	1	2006-04-03 17:18
Need help factoring Cunningham numbers	jasong	Factoring	27	2006-03-21 02:47

2015-05-20, 01:50	#1255
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,497 Posts	Six years ago I did not know many things. But that's ok. I am as clever as I was back them - I still don't know those things. I thought about octics from time to time. But let's consider - where do they come from? 1. They trivially come forward if you can take sqrt of x and double all degrees. You turn a quartic into an octic with no benefit in size. That's almost never good (except if the number was _very_ large; I thought that 2,1100+ is almost that large, but no!). 2. If you use cyclotomic polcyclo(5) and the Aurifeuillian for base 2, your get an octic foldable into a quartic. Cf. #1, same situation. 3. They happen to be around if you can use the cyclotomic polcyclo(3) and get you difficulty down 1.5x times. (Your starting polynomial may already have some reduction in size - either as an Aurifeuillian or from polcyclo(5); then you get an octic. If you had polcyclo(21), then you are fine because its degree is 12 and then you fold it reciprocally into degree 6, but with from polcyclo(15) you get a degree 8). Unfortunately and naturally, the cofactor will be even more than 1.5x less than that difficulty, so from the point of view of the raw polynomial the cofactor always looks like a GNFS to begin with. 4. They can be made from polcyclo(17); that is almost as bad as #1, -- the gain is only 1/17th of difficulty and the reward is hard to see. What about degree 7 polynomials? Well, they never happen because degree of cyclotomic is never 7. Quartics are hard for large size (and growing harder with size). Why do people then even use quartics? Well, they still provide a 1.25x reduction in size, and then even if you didn't use quartic, you cannot use quintic (it will be reducible and the siever will be not working properly) - you then have to use sextic with some residual degree (b^(n%6)) going into c6 and making for an irreducible poly. For some (smaller) sizes, sextic will be more painful than quartic. So, hence, quartic. Not all numbers really have to be done necessarily today or tomorrow - just leave them for the future: either the computers will become more powerful and these projects will be peanuts in 2020, or some new theory will get advanced. My 2 cents.

2015-06-14, 20:45	#1264
pinhodecarlos "Carlos Pinho" Oct 2011 Milton Keynes, UK 3×17×97 Posts	I'm reaching a point were my cores are not efficient on running LLR so I was thinking to put them on 14e sieve for NFS@Home. How much ecm was done on this 117 composites?