mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2008-03-11, 12:58   #45
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by akruppa View Post
I'll do 3,553- c163.

Alex
Are you using SNFS? or GNFS? The decision is close.
R.D. Silverman is offline   Reply With Quote
Old 2008-03-11, 15:40   #46
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2008-03-11, 15:46   #47
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2008-03-14, 09:56   #48
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

3·73 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
wpolly is offline   Reply With Quote
Old 2008-03-14, 10:08   #49
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2008-03-19, 20:43   #50
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18D116 Posts
Default

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)
fivemack is offline   Reply With Quote
Old 2008-06-10, 08:17   #51
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2008-06-10, 09:08   #52
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

25418 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2008-06-10, 11:16   #53
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

22×3×7×112 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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
xilman is offline   Reply With Quote
Old 2008-07-19, 13:17   #54
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by garo View Post
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
bdodson is offline   Reply With Quote
Old 2008-08-07, 09:48   #55
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
7+ table garo Cunningham Tables 85 2020-04-15 21:12
5- table garo Cunningham Tables 82 2020-03-15 21:47
5+ table garo Cunningham Tables 99 2020-01-10 06:29
6+ table garo Cunningham Tables 79 2020-01-01 15:26
6- table 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

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.