How Big Can an SNFS Constant Term Be?

[wblipp]

Suppose I started with a 40 digit number "p", found a 200 digit prime "q" in p^7-1, and now want to factor q+1.

Letting a = (p^7-1)/(p-1)/q, I could set up the polynomial

x^6 + x^5 + x^4 + x^3 + x^2 + x + (a+1)

This would be a 240 digit SNFS factorization vs a 200 digit GNFS factorization, except the final coefficient is 40 digits. If I understand correctly, we wouldn't get the SNFS advantage because of the large coefficient. If "a" were only 2 or 3 digits, this would work fine. How big can "a" get before it is "too big?"

[Batalov]

Well, it cannot be very big.
Or else we could recast all pesky natural quartics (e.g. arising from Cunnigham's 2L/M with exponents divisible by 3 [but not by 9], or by 5, or or 15) into sextics with 10-15-20 digit coefficients at terms of x and x^4... but we can't!

[chris2be8]

I've done some with fairly big terms. Eg 1123211^21+1262 with poly:

n: 29536685155104080856287903897527565250297490827112361090369164872774659770733948449930972459855401895254845063
type: snfs
# m = 1123211^4
m:  1591642004763292774171441
c5: 1123211
c4: 0
c3: 0
c2: 0
c1: 0
c0:  1262

As a very rough guess adding twice as many digits as the largest term has to the SNFS difficulty will give a rough idea how good it is. But that's only to say if it's worth trying some test sieving on it. And I've not been much above 12 digit terms.

Chris

PS. Found a better example, 93782639^17-1 with poly:

c4: 93782639
c0: -1
Y1: -1
m: 77355250649205425507590966271041

[wblipp]

Both of these examples have the largest coefficient at one-fourth the size of m. I was hoping the answer would be as large as one-half, but I also feared the answer might be as small as one-tenth. Maybe I'll look for a case at one-third to see if one-fourth is a tight bound.

[R.D. Silverman]

Originally Posted by wblipp

Suppose I started with a 40 digit number "p", found a 200 digit prime "q" in p^7-1, and now want to factor q+1.

Letting a = (p^7-1)/(p-1)/q, I could set up the polynomial

x^6 + x^5 + x^4 + x^3 + x^2 + x + (a+1)

This would be a 240 digit SNFS factorization vs a 200 digit GNFS factorization, except the final coefficient is 40 digits. If I understand correctly, we wouldn't get the SNFS advantage because of the large coefficient. If "a" were only 2 or 3 digits, this would work fine. How big can "a" get before it is "too big?"

Poorly and incompletely posed.

[xilman]

Originally Posted by R.D. Silverman

Poorly and incompletely posed.

I think that was understood from the start, otherwise why would "too big" be in quotes?

Nonetheless it's an interesting question to consider under various interpretations of conditions. Two arbitrary conditions I will impose for present purposes are that only two polynomials are used and that one of them is linear.

One interpretation, for instance, goes as follows: SNFS has algebraic polynomial coefficients O(1), which is what it makes it special. Unfortunately that only tells you the asymptotic behaviour and we are not factoring arbitrarily large integers.

Another interpretation: fix the size of N. For an algebraic polynomial coefficient of maximum magnitude m, how big may m be, in terms of the size of N, such that the time taken to factor N is less than t times that to factor N by the GNFS where all the coefficients are of size g?

[balamber]

Originally Posted by wblipp

This would be a 240 digit SNFS factorization vs a 200 digit GNFS factorization, except the final coefficient is 40 digits. If I understand correctly, we wouldn't get the SNFS advantage because of the large coefficient. If "a" were only 2 or 3 digits, this would work fine. How big can "a" get before it is "too big?"

This choice (GNFS vs SNFS with a large c0) is usual for multiperfect numbers. I have no ideas, except test sieving for these choices.

Example 1. M889=2^889-1
Poly for M889: P(x) = x^6+x^5+x^4+x^3+x^2+x+1
m = 2^127
P[m] = M889/(2^127-1) = 127^2 * P226
P226+1 = 2 * 13 * 167 * 233 * 1523710665712981893166806141197 * C189
Poly for (P226+1): Q(x) = x^6+x^5+x^4+x^3+x^2+x+c0, where c0=1+127^2=16130
(SNFS difficulty 230)

So, we have the choice between SNFS-230 and GNFS-189. The maximal coefficient c0=16130 is small enough. So, the first choice (SNFS-189) appears to be more convenient. C189 = P91*P99


Example 2. M883=2^883-1
Poly for M883: P(x) = 2*x^6-1
m=2^147
P[m] = M883 = 8831 * 63577 * 258777491057348926546569104663 * P228
P228+1 = 2^7 * 73349953 * C218
Poly for (P228+1): Q(x) = x^6+c0,
where m=2^146 (both sides are divided by 2^7) and c0 = 1135079928310973320630041866046765585
(SNFS difficulty 264)

So, we have the choice between SNFS-264 and GNFS-218. From formal point of view, the choice of SNFS has to be better. Nevertheless, the huge coefficient c0=1135079928310973320630041866046765585 disagrees with this "formal point of view" ;) C218 = P74 * P145

P.S. My question HERE was connected with SNFS for M712=2^712-1. Thank you for anser once more.

[R.D. Silverman]

Originally Posted by balamber

So, we have the choice between SNFS-264 and GNFS-218. From formal point of view, the choice of SNFS has to be better. Nevertheless, the huge coefficient c0=1135079928310973320630041866046765585 disagrees with this "formal point of view" ;) C218 = P74 * P145

Compare the NORMS generated by the two different polynomials.

P.S. My question HERE was connected with SNFS for M712=2^712-1. Thank you for anser once more.

I am having a stupidity attack. Why would one ever factor 2^(2n) - 1 via NFS?????
It is the difference of two squares!!!!!

[balamber]

Originally Posted by R.D. Silverman

Compare the NORMS generated by the two different polynomials.

Correct improvement for polynomials of a same order (my 2nd example).
But for the 1st example we have:
1) SNFS poly of the 6th order.
2) best GNFS poly for C189 should be of the 5th order
(As far as I understand, topicstarter meets the same problem.)

How can I compare these polynomials without test sieving? I don't know. It is really interesting! Thank you in advance.

Originally Posted by R.D. Silverman

I am having a stupidity attack. Why would one ever factor 2^(2n) - 1 via NFS?????
It is the difference of two squares!!!!!

Indeed. The question was about the half of this number (2^356+1) = 17 * P106. (P106+1) was my first snfs job and I had problems with small factors. Sorry for off.

[R.D. Silverman]

Originally Posted by balamber

Correct improvement for polynomials of a same order (my 2nd example).
But for the 1st example we have:
1) SNFS poly of the 6th order.
2) best GNFS poly for C189 should be of the 5th order
(As far as I understand, topicstarter meets the same problem.)

How can I compare these polynomials without test sieving? I don't know. It is really interesting! Thank you in advance.

I bring back my old .signature:

"You can lead a horse's ass to knowledge, but you can't make him think".

I told you what to do. You chose to ignore me or argue with me.


Indeed. The question was about the half of this number (2^356+1) = 17 * P106. (P106+1) was my first snfs job and I had problems with small factors. Sorry for off.[/QUOTE]

[wblipp]

Originally Posted by R.D. Silverman

Compare the NORMS generated by the two different polynomials.

Does this sound like a reasonable heuristic to handicap the effect of an "oversized" coefficient?

We have an empirical heuristic for when SNFS and GNFS are equally difficult; it says that a 240 digit SNFS is about the same difficulty as 174 digit GNFS. 174 digit numbers can be written in seven "digits" using a 24.8 digit radix, so the size of the L2-norm of a degree-6 GNFS polynomial will be about sqrt(7)* 24.8, about 66 digits. The L2-norm of an SNFS polynomial will be about 1 digit.

If we plot the pairs (size, norm) we have that (240, 1) and (176, 66) are equally difficult - the proposed heuristic is that all points on the line between these two points also have that same difficulty.

Note: Edited because 29 digits allows monic polynomial, but 24.8 digits is sufficient for general polynomials.