Factoring humongous Cunningham numbers - Page 112

LaurV · 2015-03-25, 16:13

You are my man! I knew it!

LaurV · 2015-04-17, 06:55

Again, replying to my own posts...

We are still sieving the C158 from Paul and have ~62M relations for it. It does not seem to wanna try filtering. We assume we knew (but might be wrong) that ~45M-50M relations may be enough for this size a compy. Is something wrong with the new yafu, or I am parallel with the subject again? (i.e. how many more relations I should get? should I force a filtering? should I report a bug in yafu thread? or some PEBKAC again? I remember seeing a nice graph with composite size vs number of (G/S)NFS relations, but I can't find it anymore)

axn · 2015-04-17, 07:41

Quote:

Originally Posted by LaurV

We are still sieving the C158 from Paul and have ~62M relations for it. It does not seem to wanna try filtering. We assume we knew (but might be wrong) that ~45M-50M relations may be enough for this size a compy.

What are the parameters in the nfs.job file?

LaurV · 2015-04-17, 09:59

Quote:

Originally Posted by axn

What are the parameters in the nfs.job file?

This is a good question, but it has to wait until I return home tonight. Meantime, I found some graphs I was looking for, and as expected, I was "a little bit off" with the numbers... the 45M relations which I remembered was for a ~C150. I still have to dig until a bit over ~70M relations are found...

VBCurtis · 2015-04-17, 23:26

Quote:

Originally Posted by LaurV

This is a good question, but it has to wait until I return home tonight. Meantime, I found some graphs I was looking for, and as expected, I was "a little bit off" with the numbers... the 45M relations which I remembered was for a ~C150. I still have to dig until a bit over ~70M relations are found...

The expected number of relations is a function of the large-primes size, rather than the composite size. It may have been that a couple years ago, C158 would have been done with 29-bit LP, which would be consistent with 45-50M relations. It sounds like YAFU chose 30-bit LP for your job, which will need ~80M. If you/YAFU had chosen 31-bit LP, it would need ~135M relations (but those relations would be found nearly twice as fast as 30-bit-LP relations).

Please do post how many raw relations this job needs; I've been doing jobs this size with 31LP, so I'd like data on a 30LP job.

LaurV · 2015-04-18, 02:58

Quote:

Originally Posted by VBCurtis

If you/YAFU had chosen...

Me?

c'mon boyar, I only press keys and click the mouse! I didn't chose nothing. I wouldn't know how...

Joking apart, thanks a lot for the explanation, it makes sense, I begun to guess that after axn's question. It also calms my pride: now I have the excuse to say that I was right remembering the 45M (I split a few of composites of ~C150+ for my aliquot sequences, but this was years ago, I still have them reserved but some of them are not touched for years, so I am sure you are right about the LP, then probably I am not going totally insane, hehe).

OTOH, in the morning when I left (my working Saturday today) it was still sieving, no sign of any filtering, and the speed is quite reasonable, it gets a bit more than 400k-420k relations per every q range (default range of yafu, 4 cores, ~100k-110k relations per core). Wondering if it may be the 31LP?

I may post the poly later.

Now back to work.

VBCurtis · 2015-04-18, 04:55

My explanation is, at best, imprecise. For a specific LP level, larger GNFS jobs *will* require more relations; if both are done with 30LP, a C158 might require 10% more rels than a C150. Same with SNFS difficulty. The polynomial has nothing to do with the choice of LP bounds; however, the .fb file should list the parameters that were chosen, along with the poly. lpba and lpbr are the large-prime bounds; these are powers of 2. So, take a peek at those parameters in the .fb file, decide which power of 2 they are, and you have your hint for relations needed.

Dubslow · 2015-04-18, 05:21

Yafu of course keeps the poly and parameters in GGNFS form in nfs.job as well as Msieve form in nfs.fb. (I find the GGNFS format a bit more human readable.)

LaurV · 2015-04-18, 06:05

Quote:

Originally Posted by Dubslow

nfs.job

Yeah, that I mean when I said "poly".

Quote:

Originally Posted by VBCurtis

these are powers of 2. So, take a peek

Oh! This is easier than expected, I know the powers of 2 by heart...

R.D. Silverman · 2015-04-18, 07:32

Quote:

Originally Posted by VBCurtis

The expected number of relations is a function of the large-primes size, rather than the composite size.

False.

LaurV · 2015-04-18, 10:58

Quote:

Originally Posted by LaurV

Oh! This is easier than expected, I know the powers of 2 by heart...

Ha! They are not!

hehe, yafu decided to store them in number of bits. Good to know.

Code:

n: 15245685683654194070528451784367735927134564102584982532265254072253746820313011591722538299058918175786099377638450142276578178842074686064451121444334808941
skew: 76967649.34
c0: -388219652152137289945728452849156092151552
c1: 31897168474946617482234360164118068
c2: -8309850439619272290936949
c3: -13444173881982964058
c4: -21258070854
c5: 720
Y0: -7330995270849431836665563364183
Y1: 132282895415155891
rlim: 36800000
alim: 36800000
lpbr: 30
lpba: 30
mfbr: 60
mfba: 60
rlambda: 2.6
alambda: 2.6

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-03-25, 16:13	#1222
LaurV Romulan Interpreter Jun 2011 Thailand 3·3,221 Posts	You are my man! I knew it!

2015-04-17, 06:55	#1223
LaurV Romulan Interpreter Jun 2011 Thailand 3×3,221 Posts	Again, replying to my own posts... We are still sieving the C158 from Paul and have ~62M relations for it. It does not seem to wanna try filtering. We assume we knew (but might be wrong) that ~45M-50M relations may be enough for this size a compy. Is something wrong with the new yafu, or I am parallel with the subject again? (i.e. how many more relations I should get? should I force a filtering? should I report a bug in yafu thread? or some PEBKAC again? I remember seeing a nice graph with composite size vs number of (G/S)NFS relations, but I can't find it anymore)

2015-04-18, 04:55	#1228
VBCurtis "Curtis" Feb 2005 Riverside, CA 11×443 Posts	My explanation is, at best, imprecise. For a specific LP level, larger GNFS jobs will require more relations; if both are done with 30LP, a C158 might require 10% more rels than a C150. Same with SNFS difficulty. The polynomial has nothing to do with the choice of LP bounds; however, the .fb file should list the parameters that were chosen, along with the poly. lpba and lpbr are the large-prime bounds; these are powers of 2. So, take a peek at those parameters in the .fb file, decide which power of 2 they are, and you have your hint for relations needed.

2015-04-18, 05:21	#1229
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 16065₈ Posts	Yafu of course keeps the poly and parameters in GGNFS form in nfs.job as well as Msieve form in nfs.fb. (I find the GGNFS format a bit more human readable.)