mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-03-15, 03:32   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×103 Posts
Thumbs up 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?"
wblipp is offline   Reply With Quote
Old 2015-03-15, 15:40   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

25×7×43 Posts
Default

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!
Batalov is offline   Reply With Quote
Old 2015-03-15, 16:47   #3
chris2be8
 
chris2be8's Avatar
 
Sep 2009

23×52×11 Posts
Default

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.
chris2be8 is offline   Reply With Quote
Old 2015-03-15, 18:35   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

94116 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2015-03-16, 11:42   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by wblipp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-03-16, 14:22   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3×13×283 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
xilman is offline   Reply With Quote
Old 2015-03-18, 10:31   #7
balamber
 
balamber's Avatar
 
Jun 2012
spb.ru

1416 Posts
Default

Quote:
Originally Posted by wblipp View Post
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
balamber is offline   Reply With Quote
Old 2015-03-18, 18:47   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by balamber View Post

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
R.D. Silverman is offline   Reply With Quote
Old 2015-03-18, 20:45   #9
balamber
 
balamber's Avatar
 
Jun 2012
spb.ru

22·5 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 View Post
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.
balamber is offline   Reply With Quote
Old 2015-03-19, 12:26   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by balamber View Post
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]
R.D. Silverman is offline   Reply With Quote
Old 2015-03-20, 17:14   #11
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·103 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
wblipp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Short term goal em99010pepe No Prime Left Behind 94 2008-03-24 21:02
Longer-term plans? fivemack NFSNET Discussion 3 2008-02-21 19:26
What's the next term in the sequence (part deux)? grandpascorpion Puzzles 4 2007-01-11 13:19
Short-term goal em99010pepe Operation Billion Digits 8 2005-11-26 22:53
Long-term Primenet archive delta_t Data 3 2005-08-25 00:31

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


Wed Dec 8 23:00:55 UTC 2021 up 138 days, 17:29, 0 users, load averages: 1.54, 1.54, 1.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.