Factoring humongous Cunningham numbers

[RichD]

Try the -a side. You might be surprised.

[jyb]

Originally Posted by RichD

Try the -a side. You might be surprised.

Oh, I did. Obviously it was better than -r, but still pretty bad.

[Batalov]

There's no magic bullet (for 2,1100+); it is very slow (as a quartic and as an octic); I am going to return it back into the wild sometime soon.

For the c121, only GNFS makes sense (and it is way too easy to even start thinking about an octic; I see the octic, but I don't like it given the size c121). If you had an octic with diff.152 and cofactor size of the full 152 digits, then maybe it could make sense to play with it.

[jyb]

Originally Posted by Batalov

There's no magic bullet (for 2,1100+); it is very slow (as a quartic and as an octic); I am going to return it back into the wild sometime soon.

For the c121, only GNFS makes sense (and it is way too easy to even start thinking about an octic; I see the octic, but I don't like it given the size c121). If you had an octic with diff.152 and cofactor size of the full 152 digits, then maybe it could make sense to play with it.

Well sure, doing this particular number by GNFS is the way to go, but as I said this was an experiment. To take a more difficult example, consider 10+9,690L. Its primitive has 177 digits, with no (very) small factors. By the normal quartic it would have an SNFS difficulty of ~276. GNFS would be the far better of those two options, but it's still a lot of work. But with an octic, the nominal SNFS difficulty would be ~184, which sounds pretty darn easy.

So the question is, is there any good choice of parameters that could make sieving this number with an octic behave like it really has difficulty 184? Or failing that, just how much of a penalty would you estimate there is? 20 digits of difficulty? 30?

[Batalov]

Well it has a factor 20 digits... So one primitive part is a c159 and the other, a c158... Needs more ECM! ;-)

And then, one of them is factored completely, and the other (the former c177) has a c115 remaining.

[jyb]

Originally Posted by Batalov

Well it has a factor 20 digits... So one primitive part is a c159 and the other, a c158... Needs more ECM! ;-)

And then, one of them is factored completely, and the other (the former c177) has a c115 remaining.

*Sigh* You're really trying hard to avoid the question, aren't you?

I don't really care about 10+9,690[LM] in particular, it was just an illustration--which is why I didn't put any effort at all into looking for small factors of the primitives. Suppose one or both of them didn't happen to have any small (i.e. within range of ECM) factors. Then reconsider the same questions from my last post.

[Batalov]

For all of these small numbers octics will be suboptimal.

[R.D. Silverman]

Originally Posted by Batalov

For all of these small numbers octics will be suboptimal.

Very suboptimal

[jyb]

Originally Posted by Batalov

For all of these small numbers octics will be suboptimal.

Originally Posted by R.D. Silverman

Very suboptimal

Okay, so if an octic is suboptimal, by definition there exists a better option. For the example I've given (subject to the hypothetical that there are no small factors), what would that be? GNFS with a 177-digit composite? That's really better than an octic with difficulty 184? Or is there some other option I'm not aware of?

[Batalov]

Originally Posted by jyb

GNFS with a 177-digit composite? That's really better than an octic with difficulty 184?

If there was a test case, one could sieve and answer this question. And if there isn't, then there are a million other interesting questions that could be answered before this one.

One simple thing that maybe should be mentioned is that a phrase "...and there was a 20 (30? 40? 60?) digit virtual size penalty incurred while sieve this number" has a meaning only when "this number" is defined. There is not universal "size penalty", not 20, not 40 digits. Not for a quartic, not for an octic. It is only a post hoc colloquial figure of speech. For each number it will be different. The proof of the pudding is ...you know.

[jyb]

Originally Posted by Batalov

If there was a test case, one could sieve and answer this question. And if there isn't, then there are a million other interesting questions that could be answered before this one.

One simple thing that maybe should be mentioned is that a phrase "...and there was a 20 (30? 40? 60?) digit virtual size penalty incurred while sieve this number" has a meaning only when "this number" is defined. There is not universal "size penalty", not 20, not 40 digits. Not for a quartic, not for an octic. It is only a post hoc colloquial figure of speech. For each number it will be different. The proof of the pudding is ...you know.

I was asking by analogy with this. But okay, I get the idea. It's just that you (and Bob, especially) were quite emphatic that the octic was *not* the best choice.