20150315, 03:32  #1 
"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^71, and now want to factor q+1.
Letting a = (p^71)/(p1)/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?" 
20150315, 15:40  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010110100000_{2} 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 101520 digit coefficients at terms of x and x^4... but we can't! 
20150315, 16:47  #3 
Sep 2009
898_{16} 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 Chris PS. Found a better example, 93782639^171 with poly: Code:
c4: 93782639 c0: 1 Y1: 1 m: 77355250649205425507590966271041 Last fiddled with by chris2be8 on 20150315 at 16:53 Reason: Added PS. 
20150315, 18:35  #4 
"William"
May 2003
New Haven
23·103 Posts 
Both of these examples have the largest coefficient at onefourth the size of m. I was hoping the answer would be as large as onehalf, but I also feared the answer might be as small as onetenth. Maybe I'll look for a case at onethird to see if onefourth is a tight bound.

20150316, 11:42  #5  
Nov 2003
2^{2}×5×373 Posts 
Quote:


20150316, 14:22  #6 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3·13·283 Posts 
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? 
20150318, 10:31  #7  
Jun 2012
spb.ru
2^{2}×5 Posts 
Quote:
Example 1. M889=2^8891 Poly for M889: P(x) = x^6+x^5+x^4+x^3+x^2+x+1 m = 2^127 P[m] = M889/(2^1271) = 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 SNFS230 and GNFS189. The maximal coefficient c0=16130 is small enough. So, the first choice (SNFS189) appears to be more convenient. C189 = P91*P99 Example 2. M883=2^8831 Poly for M883: P(x) = 2*x^61 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 SNFS264 and GNFS218. 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^7121. Thank you for anser once more. Last fiddled with by balamber on 20150318 at 10:35 

20150318, 18:47  #8  
Nov 2003
2^{2}×5×373 Posts 
Quote:
Quote:
It is the difference of two squares!!!!! Last fiddled with by R.D. Silverman on 20150318 at 18:47 Reason: typo 

20150318, 20:45  #9  
Jun 2012
spb.ru
2^{2}·5 Posts 
Quote:
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. 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. 

20150319, 12:26  #10  
Nov 2003
7460_{10} Posts 
Quote:
"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] 

20150320, 17:14  #11  
"William"
May 2003
New Haven
2369_{10} Posts 
Quote:
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 L2norm of a degree6 GNFS polynomial will be about sqrt(7)* 24.8, about 66 digits. The L2norm 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 20150320 at 17:45 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Short term goal  em99010pepe  No Prime Left Behind  94  20080324 21:02 
Longerterm plans?  fivemack  NFSNET Discussion  3  20080221 19:26 
What's the next term in the sequence (part deux)?  grandpascorpion  Puzzles  4  20070111 13:19 
Shortterm goal  em99010pepe  Operation Billion Digits  8  20051126 22:53 
Longterm Primenet archive  delta_t  Data  3  20050825 00:31 