mersenneforum.org How Big Can an SNFS Constant Term Be?
 Register FAQ Search Today's Posts Mark Forums Read

 2015-03-15, 03:32 #1 wblipp     "William" May 2003 New Haven 23·103 Posts How Big Can an SNFS Constant Term Be? 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?"
 2015-03-15, 15:40 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 25D816 Posts 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!
 2015-03-15, 16:47 #3 chris2be8     Sep 2009 42568 Posts I've done some with fairly big terms. Eg 1123211^21+1262 with poly: Code: 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: Code: c4: 93782639 c0: -1 Y1: -1 m: 77355250649205425507590966271041 Last fiddled with by chris2be8 on 2015-03-15 at 16:53 Reason: Added PS.
 2015-03-15, 18:35 #4 wblipp     "William" May 2003 New Haven 94116 Posts 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.
2015-03-16, 11:42   #5
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 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.

2015-03-16, 14:22   #6
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

31·359 Posts

Quote:
 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?

2015-03-18, 10:31   #7
balamber

Jun 2012
spb.ru

2010 Posts

Quote:
 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.

Last fiddled with by balamber on 2015-03-18 at 10:35

2015-03-18, 18:47   #8
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 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.

Quote:
 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!!!!!

Last fiddled with by R.D. Silverman on 2015-03-18 at 18:47 Reason: typo

2015-03-18, 20:45   #9
balamber

Jun 2012
spb.ru

22×5 Posts

Quote:
 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.

Quote:
 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.

2015-03-19, 12:26   #10
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 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]

2015-03-20, 17:14   #11
wblipp

"William"
May 2003
New Haven

23·103 Posts

Quote:
 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.

Last fiddled with by wblipp on 2015-03-20 at 17:45

 Similar Threads Thread Thread Starter Forum Replies Last Post em99010pepe No Prime Left Behind 94 2008-03-24 21:02 fivemack NFSNET Discussion 3 2008-02-21 19:26 grandpascorpion Puzzles 4 2007-01-11 13:19 em99010pepe Operation Billion Digits 8 2005-11-26 22:53 delta_t Data 3 2005-08-25 00:31

All times are UTC. The time now is 00:17.

Fri Jan 21 00:17:29 UTC 2022 up 181 days, 18:46, 0 users, load averages: 1.62, 1.70, 1.52