mersenneforum.org A question about Cunningham tables
 Register FAQ Search Today's Posts Mark Forums Read

 2005-05-23, 21:16 #1 T.Rex     Feb 2004 France 16238 Posts A question about Cunningham tables Hi, I've looked at Cunningham tables and I found no factorisation of big numbers like: 2^29800963 - 1 = 15436497912585268249 * ... or: 2^4782969 + 1 = 3635056441 * ... Why ? Is the goal to fill the tables from the beginning up only ? Why not also collecting the factors of big numbers ? I've not found a clear description of the exact goals of this project. Tony
2005-05-23, 21:29   #2
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by T.Rex Hi, I've looked at Cunningham tables and I found no factorisation of big numbers like: 2^29800963 - 1 = 15436497912585268249 * ... or: 2^4782969 + 1 = 3635056441 * ... Why ? Is the goal to fill the tables from the beginning up only ? Why not also collecting the factors of big numbers ? I've not found a clear description of the exact goals of this project. Tony
Because the tables were defined with a limited scope. The current
tables are beyond our ability at the upper end. Extending them to such
large exponents would be pointless, because factoring numbers that size
are totally a matter of (a GREAT DEAL) of luck. We only succeed when
there are 1 or 2 small factors, and the cofactor is prime. Such numbers
are extremely rare. So a systemic effort would simply yield a sprinkling
of small factors where there is no hope of finishing off the cofactors.

May I suggest that you read the introduction to the tables (available
on Sam Wagstaff's Website) to understand their history????

The current goal is to finish the existing tables. Sometimes when a sub-table
gets finished, or close to being finished, it is extended by a modest amount.

What is "big" depends on best available algorithms. By current or near-future
standards, "big" is any general number of more than about 200 digits, or
a Cunningham number of more than 250 digits. Currently *hopeless* is
a general number of 768 bits or a Cunningham number of more than about
1024 bits (SNFS could just barely do a 1024 bit number with a massive, massive effort)

2005-05-24, 04:20   #3
wblipp

"William"
May 2003
New Haven

3·787 Posts

Quote:
 Originally Posted by T.Rex Hi, I've looked at Cunningham tables and I found no factorisation of big numbers like: 2^29800963 - 1 = 15436497912585268249 * ... or: 2^4782969 + 1 = 3635056441 * ...
Will Edgington collects all known factors of Mersenne numbers. He regularly updates a file with factors for exponents under 200,000 and responds to emails about factors of higher exponents.

http://www.garlic.com/~wedgingt/mersenne.html

 2005-05-24, 16:27 #4 alpertron     Aug 2002 Buenos Aires, Argentina 54416 Posts It would be nice to have an appendix of the Cunningham project that lists the known _complete_ factorization of a^b +/- 1 with bases 2 to 12 and exponents greater than the ones used actually in the project. That list would not very extensive, because the pseudoprime cofactors should be verified. That should limit the values of a^b +/- 1 to less than, say, 5000 digits at most, unless someone discovers a method to find quickly if a factor of a^b +/- 1 is prime or not.
 2005-05-24, 16:43 #5 T.Rex     Feb 2004 France 3·5·61 Posts Thanks for the answers. - I've warned Will about the Mersenne factor. - I've read again the introduction to the Cunningham tables but it still is unclear for me. Probably due to my poor english. - Thanks for the explanation of the goal of the project. It's clear now. Nevertheless, I think it is so fun to find a factor of so big numbers, even by luck (or with prime95 for the first one and with PARI/gp for the second one)). Where is collected all the knowledge about the factorization properties of these Cunningham numbers ? Regards, Tony
2005-05-24, 17:23   #6
rogue

"Mark"
Apr 2003
Between here and the

33×233 Posts

Quote:
 Originally Posted by T.Rex Where is collected all the knowledge about the factorization properties of these Cunningham numbers ?
Is this what you are looking for: http://www.cerias.purdue.edu/homes/ssw/cun/index.html . In the minimum it is a starting point.

2005-05-24, 17:50   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by alpertron It would be nice to have an appendix of the Cunningham project that lists the known _complete_ factorization of a^b +/- 1 with bases 2 to 12 and exponents greater than the ones used actually in the project. That list would not very extensive, because the pseudoprime cofactors should be verified. That should limit the values of a^b +/- 1 to less than, say, 5000 digits at most, unless someone discovers a method to find quickly if a factor of a^b +/- 1 is prime or not.
Suggest it to the authors.

It isn't a bad idea. Why don't you put one together?

2005-05-24, 18:02   #8
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by T.Rex Nevertheless, I think it is so fun to find a factor of so big numbers, even by luck (or with prime95 for the first one and with PARI/gp for the second one)).
As the saying goes: "different stokes for different folks".
If you find it fun, you are certainly welcome to do it.

However, I share the view of the Cunningham authors:

"there is a real feeling of accomplishment in breaking apart some huge
number which has withstood assaults for decades, especially when in doing
so one has had to devise and carry out some new computational scheme"

I never saw the fascination in just mindlessly running code written by
others. I wanted to understand the algorithms and write the code myself.
Therein lies the real reward: writing and using your OWN code.

As for finding small factors of very large numbers, I think it is just too easy.
The real reward comes from the success arising from an *extended* effort.

And let me repeat in parting what we are all told by our parents:

Finish what you start before going on to something new.......

2005-05-24, 18:23   #9
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by R.D. Silverman As for finding small factors of very large numbers, I think it is just too easy. The real reward comes from the success arising from an *extended* effort. And let me repeat in parting what we are all told by our parents: Finish what you start before going on to something new.......
Allow me to add that finding small factors of much larger numbers is,
as John Selfridge put it:

"Picking plums at waist height".

It is a first step toward complete factorizations, but the CURRENT tables
for pushing developments in algorithms. I see no reason why finding
a small factor of 2^n-1 (for large n) through luck, using ECM, contributes
to improving the art.

Note: I would have more respect for your endeavors if you were using
your own code.. While I too use GMP-ECM, I have in the past coded my own
ECM program. I devote my time to improving my NFS code, rather than
improving my ECM code. A single person can't optimize everything.

2005-05-24, 19:33   #10
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

23×113 Posts

Quote:
 Originally Posted by R.D. Silverman Suggest it to the authors. It isn't a bad idea. Why don't you put one together?
Seconded.

I certainly don't have time to do it myself, but I may be able to assist in a small way.

Paul

 2005-05-24, 21:23 #11 alpertron     Aug 2002 Buenos Aires, Argentina 22×337 Posts Thanks, Bob and Paul. I actually don't have time either but for base 2 someone can convert the information located at the complete factorization page of Will Edgington Mersenne site to the format used in the Cunningham project. Many records with general primality testing algorithms were done with large factors of non-prime Mersenne numbers.

 Similar Threads Thread Thread Starter Forum Replies Last Post Mystwalker Cunningham Tables 277 2018-11-28 02:59 Raman Cunningham Tables 87 2012-11-14 11:24 Zeta-Flux Factoring 2 2008-03-03 18:34 garo Cunningham Tables 3 2006-07-04 08:00 garo Factoring 1 2006-03-23 22:17

All times are UTC. The time now is 18:41.

Tue Apr 20 18:41:08 UTC 2021 up 12 days, 13:22, 0 users, load averages: 3.79, 3.46, 3.46