mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2020-06-25, 22:21   #177
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by sweety439 View Post
but 12^319 > 10^323, so 10^323-1 should be factored first

Also Phi_319(12) > Phi_323(10)

12^319-1 has an algebraic factor. We are not factoring 12^319-1, we are factoring (12^319-1)/(12^29-1) ~12^290 ~ C313.

The resulting polynomial is reciprocal, so we can do this number with a quintic.
However, quintic polynomials for numbers this size result in matrices that are
significantly larger than those for numbers of similar
size done with sextics. Greg is LA constrained right now, so he skipped 12^319-1
for the time being. He did C314, C315, C316 C317 and is now working on C318's
via 3^667-1 etc.

Greg may indeed do R323 before he does 12^319-1. I think he will. R323 might well be
done by a reciprocal octic to take advantage of the algebraic factor 10^19-1. Whether
the octic would be easier than the obvious sextic might be an interesting experiment.


It might also be interesting to see if a septic would be any better. I think a septic
will be slightly better in general for numbers of this size.

Let's do a "back of the envelope" look at the norms. Take (10^6, 10^6) == (a,b) as a
'typical lattice point'.

For a sextic, an algebraic norm is ~ a^6 ~ 10^36 and a
linear norm is ~ b * (10^324/6) ~ 10^60. For a septic an anorm is ~a^7 ~ 10^42
and a linear norm is b *(10^322/7) ~ 10^52. The norms are closer for the
septic and their product is slightly smaller. A septic seems slightly superior.
For the reciprocal octic an anorm is a^8 ~ 10^48 and a linear norm is b * (10^38) ~ 10^44 which seems even better still.

Note that one also needs to adjust these estimates by the special-q. The estimates
also ignore the effect of variance on the norms. Since we want smooth numbers
we are more concerned with the tails of the distributions of the norms rather than
the means. However, it does give a quick comparison.

NFS works best when the norms are as nearly equal as possible, other things
being equal.

This very rough estimate is based on the assumption that (10^6, 10^6) is a
typical lattice point. Adjust the analysis if this assumption is not a good enough
estimate. I do now know what sieve areas the lasievef siever uses.

Noone has been calling for him to do 12^319-1.

It is possible that Greg missed the reciprocal octic for R323. He will get to it.

Doing R323 seems to be a compulsion with you.
R.D. Silverman is offline   Reply With Quote
Old 2020-06-27, 07:33   #178
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

7E816 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
12,293+ just set a new record for largest penultimate factor.
Wow. I've been so busy I didn't even notice. Yay!
frmky is offline   Reply With Quote
Old 2020-06-27, 07:48   #179
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

23×11×23 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It is nice to hear that Universities are still going!

Greg, do you know of anyone offering a first course (on-line) in string theory?
I'd love to take one. Or a course in quantum field theory? I did get to take
a course in relativistic quantum mech from Ed Purcell when I was an undergrad.
[45 years ago, however!] It was a small fun class; he was a superb teacher.

I'm not sure if I have the needed pre-reqs.
My differential geometry background is minimal, so I may need to take that first.
Basic tensor analysis is not a problem.
Sorry, but I don't. I took a QFT course 20 years ago from Alfred Shapere at U. Kentucky, who was a student of Frank Wilczek. Haven't looked at it since I'm afraid. The closest I've come to string theory is attending a couple of talks by Ed Witten, of which I understood very little.
frmky is offline   Reply With Quote
Old 2020-06-28, 19:57   #180
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25·233 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post

<snip>

Greg may indeed do R323 before he does 12^319-1. I think he will. R323 might well be
done by a reciprocal octic to take advantage of the algebraic factor 10^19-1. Whether
the octic would be easier than the obvious sextic might be an interesting experiment.


It might also be interesting to see if a septic would be any better. I think a septic
will be slightly better in general for numbers of this size.

Let's do a "back of the envelope" look at the norms. Take (10^6, 10^6) == (a,b) as a
'typical lattice point'.

For a sextic, an algebraic norm is ~ a^6 ~ 10^36 and a
linear norm is ~ b * (10^324/6) ~ 10^60. For a septic an anorm is ~a^7 ~ 10^42
and a linear norm is b *(10^322/7) ~ 10^52. The norms are closer for the
septic and their product is slightly smaller. A septic seems slightly superior.
For the reciprocal octic an anorm is a^8 ~ 10^48 and a linear norm is b * (10^38) ~ 10^44 which seems even better still.


.
I'd like to hear ideas from others about what I wrote just above. It seems that
a degree 7 polynomial would be better (than degree 6) for Greg to use moving forward
for numbers that NFS@Home is about to undertake.
R.D. Silverman is offline   Reply With Quote
Old 2020-06-29, 10:29   #181
wreck
 
wreck's Avatar
 
"Bo Chen"
Oct 2005
Wuhan,China

A016 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I'd like to hear ideas from others about what I wrote just above. It seems that
a degree 7 polynomial would be better (than degree 6) for Greg to use moving forward
for numbers that NFS@Home is about to undertake.
I test the speed 4 years ago, the result shows deg 7 is much slower than deg 6.
deg 6 need 102 CPU years to collect 1200M raw relations, while deg 7 need 182 CPU years on an i3 CPU.
I attach the poly and test files.
Attached Files
File Type: txt R323_poly_deg6.txt (665 Bytes, 9 views)
File Type: txt R323_poly_deg7.txt (601 Bytes, 7 views)
File Type: gz R323_record_sieve_33_400M_deg6.xls.tar.gz (8.4 KB, 0 views)
File Type: gz R323_record_sieve_33_400M_deg7.xls.tar.gz (8.4 KB, 2 views)
wreck is offline   Reply With Quote
Old 2020-06-29, 15:39   #182
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001000002 Posts
Default

Quote:
Originally Posted by wreck View Post
I test the speed 4 years ago, the result shows deg 7 is much slower than deg 6.
deg 6 need 102 CPU years to collect 1200M raw relations, while deg 7 need 182 CPU years on an i3 CPU.
I attach the poly and test files.
One needs to change the factor base sizes moving from d = 6 to 7. Increase the
algebraic and decrease the linear.
R.D. Silverman is offline   Reply With Quote
Old 2020-06-29, 20:50   #183
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
One needs to change the factor base sizes moving from d = 6 to 7. Increase the
algebraic and decrease the linear.
Note also that one should (likely) apply special q to the algebraic side instead of
rational side.
R.D. Silverman is offline   Reply With Quote
Old 2020-07-02, 00:04   #184
wreck
 
wreck's Avatar
 
"Bo Chen"
Oct 2005
Wuhan,China

25·5 Posts
Default

I guess you mean increase alim and decrease rlim, use option -a.
But I test again with these changes, the situation is the same.
When I use alim=800M rlim =200M -a, and binary lasieve5_f compiled, it need 100 CPU years to collect 1200M raw relations on an i7 CPU;
While use alim=rlim =400M,-r with the same binary and processor,it need 40 CPU years to collect 1200M raw relations.
Though I don't know why,it is a little strange.
wreck is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cunningham ECM efforts pinhodecarlos Cunningham Tables 7 2017-12-21 13:29
Cunningham ECM Now Futile? R.D. Silverman GMP-ECM 4 2012-04-25 02:45
Cunningham Project on YouTube Batalov Cunningham Tables 0 2012-02-26 02:58
Extended Cunningham or so rekcahx Factoring 6 2011-08-19 12:45
Introduction: ECM work done on Cunningham Project composites garo Cunningham Tables 2 2005-01-20 10:06

All times are UTC. The time now is 22:55.

Sat Jul 11 22:55:35 UTC 2020 up 108 days, 20:28, 0 users, load averages: 2.27, 1.98, 1.84

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.