mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-06-29, 16:42   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

23×797 Posts
Default 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'.
fivemack is offline   Reply With Quote
Old 2007-06-29, 17:16   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
[already factored] with a quintic.
R.D. Silverman is offline   Reply With Quote
Old 2007-06-30, 00:10   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

23×797 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2007-06-30, 01:13   #4
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
Wacky is offline   Reply With Quote
Old 2007-06-30, 09:20   #5
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

4A516 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 .
smh is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SNFS 200 parameters JoeCrump Factoring 3 2009-12-06 14:50
fun with snfs masser Sierpinski/Riesel Base 5 36 2008-04-18 02:39
SNFS Sample(10^4+1) nuggetprime Factoring 1 2007-06-11 16:31
Weights and measures mfgoode Puzzles 12 2006-02-03 06:22
Difficulty Running Prime with DSL Rosenfeld Lounge 16 2004-07-31 22:15

All times are UTC. The time now is 02:51.

Fri Dec 4 02:51:46 UTC 2020 up 23:03, 0 users, load averages: 2.39, 1.96, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.