mersenneforum.org 3- table
 Register FAQ Search Today's Posts Mark Forums Read

2008-03-11, 12:58   #45
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by akruppa I'll do 3,553- c163. Alex
Are you using SNFS? or GNFS? The decision is close.

 2008-03-11, 15:40 #46 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts The difficulty is only 226 with a sextic while 163*3/2 = 244.5, so I figured SNFS would be the way to go. I didn't look for GNFS polynomials, though, so I cannot directly compare yield. The SNFS polynomial is the 6th cyclotomic so no real roots and the root properties are lousy, but I think the difference of size should more than make up for it. Alex
2008-03-11, 15:46   #47
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by akruppa The difficulty is only 226 with a sextic while 163*3/2 = 244.5, so I figured SNFS would be the way to go. I didn't look for GNFS polynomials, though, so I cannot directly compare yield. The SNFS polynomial is the 6th cyclotomic so no real roots and the root properties are lousy, but I think the difference of size should more than make up for it. Alex
I never quite agreed with the 3/2 ratio for GNFS vs. NFS. Theoretically,
the ratio should be (64/9)^1/3 : (32/9)^1/3

2008-03-14, 09:56   #48
wpolly

Sep 2002
Vienna, Austria

3·73 Posts

Quote:
 Originally Posted by R.D. Silverman I never quite agreed with the 3/2 ratio for GNFS vs. NFS. Theoretically, the ratio should be (64/9)^1/3 : (32/9)^1/3
That would be 2^1/3 : 1 or roughly 5 : 4

 2008-03-14, 10:08 #49 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts I'll do a polynomial search and compare sieving yield to get some data on how the equivalent size estimates between SNFS and GNFS work out. Alex
 2008-03-19, 20:43 #50 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 18D116 Posts According to my records, on similar hardware with reasonable management for the polynomial search, 1300 hours will split a C149 by GNFS, and comparable or slightly less effort splits an S218 by SNFS. For slightly smaller numbers, fibonacci(1057) - an S190 - took 350 hours, and a G138 was 240; a G141 took about 600, though with the benefit of hindsight I should probably have used 28-bit rather than 29-bit large primes for it. Fitting to my entire collection of factorisations done to date, GNFS takes about exp(0.114 * log_10(N) - 9.4) sieving hours, and SNFS takes about exp(0.075 * log_10(difficulty) - 8.2) hours, on 2.4GHz Core2 or similar (there's a lot of fuzz in the constant terms)
 2008-06-10, 08:17 #51 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts I finally did a comparison between GNFS and SNFS for 3,553-. A relatively short search (a few hours) found a poly with Murphy_E 6.57e-13, sieving with afb 30M, rfb 20M, lpb 2^30, sq in [30M,30M+1000] produced 943 relations over 69 special-q, for SNFS with the same parameters 2208 relations over 66 special-q, so the yield per special-q is almost 2.5 times as high for SNFS. Sieving SNFS was also a bit faster, about 4:30 vs. 3:45. A longer poly search may be able to reduce this gap, but most likely not close it. The difference is much less than I had expected from comparing SNFS difficulty to cofactor size, however. Alex
2008-06-10, 09:08   #52
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

25418 Posts

Quote:
 Originally Posted by fivemack Fitting to my entire collection of factorisations done to date, GNFS takes about exp(0.114 * log_10(N) - 9.4) sieving hours, and SNFS takes about exp(0.075 * log_10(difficulty) - 8.2) hours, on 2.4GHz Core2 or similar (there's a lot of fuzz in the constant terms)
It would mean O(n^c) complexity for gnfs, but it's not correct. http://en.wikipedia.org/wiki/General_number_field_sieve

2008-06-10, 11:16   #53
xilman
Bamboozled!

May 2003
Down not across

22×3×7×112 Posts

Quote:
 Originally Posted by R. Gerbicz It would mean O(n^c) complexity for gnfs, but it's not correct. http://en.wikipedia.org/wiki/General_number_field_sieve
Read what Tom wrote: he fitted a function to experimental data. He made no claim for a theoretical justification of that function. He implies. quite strongly as I read it, that his function is useful for predictions of runtime over a limited range. His function is also (a) simpler to use than the theoretical asymptotic behaviour and (b) any function also needs fitting to experimental data in order to determine proportionality constants appropriate to a particular implementation.

Paul

2008-07-19, 13:17   #54
bdodson

Jun 2005
lehigh.edu

210 Posts

Quote:
 Originally Posted by garo Code: Base Index Size 11M(45digits) 43M(50digits) 110M(55digits) 260M(60digits) Decimal 3 523- C233 3 527- C160 3 529- C237 3 547- C242 28187007684814701733343853709918959602754148410282288891635442685883190982601206036060713159871183941618273433101564274103406674642702392766666629184102216846223545188845742078720936554721136819216844352517919348378343972954064591022000728747
Childers/Dodson are happy to report finishing 3, 547- C242 (by snfs!) with

prp78 factor:22932169041497578656101635893906350495601781188\
2813174487175975135341417478309
and prp165 factor: 122914703941908311355702961196522843507
18584674423029707827350973961621122882489095148212477085420\
53379331195812489501111064875263191361424956117603449488246\
79539983

using msieve 1.34 for the matrix. This is 3-of-4 successes, with 7,311+
and a 2nd pass at 10,257+ using 1.36.

New wanted lists are out, with largest composite 3, 523- C233 More
Wanted at difficulty 249.5; as well as 3, 529- C237 being just a bit
further out at difficulty 252.4. (The above was difficulty 261, our
largest so far.) NFSNET already has two first holes reserved, M823 =
2,823- C197 and P823 = 2,823+ C229, at difficulty 247.75. Seems like
this base-3 list is due to get even shorter yet in the not-to-distant
future! -Bruce

 2008-08-07, 09:48 #55 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 3,553- c163: 1496011698256808140870327017215159254210989805180702509984299821 1311856567988975419611247459617464197060581406673461639594334403781089672393080946888216894062632439 Sieving with the Franke/Kleinjung siever, rest with Jason's Msieve. Alex Edit: I'll do 3,527- c160 next. Last fiddled with by akruppa on 2008-08-07 at 09:54

 Similar Threads Thread Thread Starter Forum Replies Last Post garo Cunningham Tables 85 2020-04-15 21:12 garo Cunningham Tables 82 2020-03-15 21:47 garo Cunningham Tables 99 2020-01-10 06:29 garo Cunningham Tables 79 2020-01-01 15:26 garo Cunningham Tables 41 2016-08-04 04:24

All times are UTC. The time now is 13:12.

Fri Aug 7 13:13:02 UTC 2020 up 21 days, 8:59, 1 user, load averages: 2.13, 2.20, 2.27

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.