mersenneforum.org How to identify SNFS candidates and factor them?
 Register FAQ Search Today's Posts Mark Forums Read

2021-07-10, 06:30   #45
axn

Jun 2003

512510 Posts

Quote:
 Originally Posted by bur Interesting, is there a way to know if GNFS is faster or does it just turn out by experiment?
There is some rule of thumb regarding SNFS-GNFS equivalency. I think ratio of SNFS size:GNFS size of about 1.3 (?) is roughly equivalent. Here 175/119 = 1.47 is clearly favoring GNFS. SNFS 175 should be equivalent to GNFS 130 (+/-).

Of course, not all SNFS 175 are equal. And the 1.3 might not be the proper value. So, it is a good starting point to check if one or the other is clearly superior, but not definitive.

Last fiddled with by axn on 2021-07-10 at 06:30

 2021-07-10, 13:13 #46 firejuggler     Apr 2010 Over the rainbow 22×32×73 Posts I think I saw somewhere that snfs difficulty =(digit lenght-30)*1.5 Wich is close to what axn said.
2021-07-10, 13:34   #47
charybdis

Apr 2020

7×67 Posts

You can use Murphy-E scores as given by cownoise/msieve to compare polynomials as long as they have the same degree. Helpfully this is a degree 5 SNFS polynomial, so we can compare it to GNFS polynomials in the right range. The score of ~9e-11 is comparable to the score of a typical GNFS-130 polynomial. 175/130 = 1.35 so that's a good ratio to use for these numbers.

Quote:
 Originally Posted by axn Of course, not all SNFS 175 are equal. And the 1.3 might not be the proper value. So, it is a good starting point to check if one or the other is clearly superior, but not definitive.
Indeed. The big c5 coefficient makes this number more difficult than a "typical" SNFS-175. An SNFS-175 polynomial with small algebraic coefficients scores more like GNFS-123, suggesting a ratio of ~1.42 rather than 1.3 or 1.35. Though I'd guess a lot of SNFS-175s being done these days don't have small algebraic coefficients.

I believe the ratio gets larger as numbers get bigger. 1.42 would suggest SNFS-250 is as hard as GNFS-176, which it isn't.

Quote:
 Originally Posted by firejuggler I think I saw somewhere that snfs difficulty =(digit lenght-30)*1.5 Wich is close to what axn said.
This must have a typo? (130-30)*1.5 = 150...

Last fiddled with by charybdis on 2021-07-10 at 13:37

 2021-07-10, 13:53 #48 richs     "Rich" Aug 2002 Benicia, California 55616 Posts Batalov told me this: The short rule of thumb is gnfs_size < 0.56 * S +30 where S is SNFS difficulty.
 2021-07-11, 09:27 #49 bur     Aug 2020 5*10398e-4;3*2539e-3 3×131 Posts So the difficulty to factor a co-factor of a "special number" is entirely determined by the size of the special number? Or does the co-factor size also play a role? I guess the latter? And at roughly which digit length should I switch to c130 parameters? VBcurtis mentioned approximately every 30 bits I should switch +5 digits for the params, but at what starting points?
2021-07-11, 11:08   #50
axn

Jun 2003

120058 Posts

Quote:
 Originally Posted by bur So the difficulty to factor a co-factor of a "special number" is entirely determined by the size of the special number? Or does the co-factor size also play a role? I guess the latter?
The former. Using the cofactor helps in the final sqrt phase when it is doing the gcd to extract factors. That'll avoid reporting small (previously known, redundant) factors.

2021-07-11, 19:02   #51
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

10011010101112 Posts

Quote:
 Originally Posted by bur And at roughly which digit length should I switch to c130 parameters? VBcurtis mentioned approximately every 30 bits I should switch +5 digits for the params, but at what starting points?
As you get into jobs that take days rather than hours, you'll want to test-sieve parameters yourself. There aren't solid rules-of-thumb for SNFS jobs like there are for GNFS, because optimal parameter choice depends in part on the size of coefficients in the poly.

That said, the formula given the post before yours allows you to plug in 130 for GNFS and solve for S; I get 180 or so. By the time you're at 200 digits, you ought to test params yourself or study the 14e queue submissions in NFS@home subforum to see what params were chosen for SNFS jobs of similar size. That research should keep you out of trouble of the "oops this job took twice as long as it should have" sense. When in doubt, use the bigger large-prime option.

 2021-07-13, 18:00 #52 bur     Aug 2020 5*10398e-4;3*2539e-3 1100010012 Posts Ok, so I roughly chose the params for a GNFS composite of the same difficulty? 180 would agree with my current plan, I used params.c120 for 520, switched to 125 at 550 and next at 580 would be up. So far the longest SNFS took about 5 h for sieving, so I'm still far from days.

 Similar Threads Thread Thread Starter Forum Replies Last Post garambois Aliquot Sequences 24 2021-02-25 23:31 EdH EdH 14 2020-04-20 16:21 cochet Miscellaneous Math 4 2008-10-24 14:33 Brian-E Lounge 24 2008-08-01 14:13 Nightgamer360 Miscellaneous Math 9 2007-07-09 17:38

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

Mon Sep 27 00:19:29 UTC 2021 up 65 days, 18:48, 0 users, load averages: 3.10, 3.04, 2.76