mersenneforum.org Better measures of SNFS difficulty
 Register FAQ Search Today's Posts Mark Forums Read

 2007-06-29, 16:42 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 24×3×7×19 Posts Better measures of SNFS difficulty A recent thread pointed out to me that, given N = 15*R, you can construct a quartic SNFS polynomial for the part of a^N-1 that is explained by the degree-8 factor of x^15-1 by taking advantage of the symmetry of that factor and writing it in terms of x+1/x; by the usual SNFS-difficulty measurement, this has difficulty (8/15) N log a. So I tried setting this up for 10^345-1, where the difficulty estimate is 184, and get Code: n: 28687509643492892075221128006449237350451146619508500482915984762059137296478553404775990467913950190401092476853539226200030840255611742267377635357890631 type: snfs skew: 1 c4: 1 c3: -1 c2: -4 c1: 4 c0: 1 Y1: -100000000000000000000000 Y0: 10000000000000000000000000000000000000000000001 The problem here is that, for any at all reasonable [A,B] value the difficulty comes entirely from the large size of the rational side; you really want B as small as possible, I'm wondering if this is a case where line sieving A=-10^11 .. 10^11, B=1 would be the right answer, or whether in that case NFS degenerates into something else. I assumed that this was the situation in which you tune the 'skew' parameter, but skew=100 and skew=0.01 were both very significantly slower than skew=1. To get relations at a reasonable rate is possible with sieve parameters something like Code: skew: 1 alim: 9000000 rlim: 72000000 lpbr: 29 lpba: 29 mfbr: 53 mfba: 53 which gets 0.145s/relation, so hopefully about five million seconds to get the 2^25 relations which is generally about what's needed to get a usable matrix with lpbr=29; this is comparable to the timing estimates I get for the C214 SNFS problem associated with F1009, so it's clearly not '184-digit difficulty'.
2007-06-29, 17:16   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by fivemack A recent thread pointed out to me that, given N = 15*R, you can construct a quartic SNFS polynomial for the part of a^N-1 that is explained by the degree-8 factor of x^15-1 by taking advantage of the symmetry of that factor and writing it in terms of x+1/x; by the usual SNFS-difficulty measurement, this has difficulty (8/15) N log a. So I tried setting this up for 10^345-1, where the difficulty estimate is 184, and get
For numbers of this size a QUARTIC polynomial is sub-optimal.
The reason is that for optimal performance you want the norms on the
rational side and on the algebraic side to be approximately equal.
When doing numbers in the 180+ digit range, a quartic yields norms on
the rational side that are significantly larger than those on the algebraic.

The correct thing to do in this case is to use a far bigger factor base
(and bound on the large primes) for the rational side than the algebraic.

BTW, this number is better done with the lattice sieve using rational side
special q.

Are you reserving this number??? It is one of two that I had planned to do after I finish 7,348+. The other is 7,553L.

For another example, consider 11^235-1. The "difficulty" with
(x^5 - 1)/(x-1) and x = 11^47 is about 196. However, it uses
a quartic polynomial and will be more difficult than would (say) 11^191 + 1

 2007-06-30, 00:10 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 24×3×7×19 Posts Is there a central spot that handles reservations for the Cunningham project? 11^251+1 (by GNFS on the C151) is so tempting (prime exponent and lots of ECM factors) that I'd assume it's already spoken for. If you're already set up to do 10^345-1, go for it, and I'll try to do Fibonacci(1009) instead, where I'm a little more confident I've got the right parameters for the sieving. That'll take me most of July.
2007-06-30, 01:13   #4
Wacky

Jun 2003
The Texas Hill Country

32×112 Posts

Quote:
 Originally Posted by fivemack Is there a central spot that handles reservations for the Cunningham project? 11^251+1 (by GNFS on the C151) is so tempting (prime exponent and lots of ECM factors) that I'd assume it's already spoken for.
There is most certainly a "central spot" for reservations relating to the "Cunningham Project". Dr. Samuel Wagstaff of Purdue University is "the keeper of the list". He sends out regular reports on both the factors found, and "who is doing what". If you intend to expend any effort on these numbers, you should clear your effort with him in order to avoid duplication of effort.

If you do not have his e-mail address, PM me and I will provide it to you.

2007-06-30, 09:20   #5
smh

"Sander"
Oct 2002
52.345322,5.52471

22458 Posts

Quote:
 Originally Posted by fivemack 11^251+1 (by GNFS on the C151) is so tempting (prime exponent and lots of ECM factors) that I'd assume it's already spoken for.
It wasn't on the last 'who is doing what' list. But that list is 4 weeks old. A new version should be out soon .

 Similar Threads Thread Thread Starter Forum Replies Last Post JoeCrump Factoring 3 2009-12-06 14:50 masser Sierpinski/Riesel Base 5 36 2008-04-18 02:39 nuggetprime Factoring 1 2007-06-11 16:31 mfgoode Puzzles 12 2006-02-03 06:22 Rosenfeld Lounge 16 2004-07-31 22:15

All times are UTC. The time now is 01:54.

Wed May 19 01:54:27 UTC 2021 up 40 days, 20:35, 0 users, load averages: 2.79, 2.61, 2.38