mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-05-23, 21:16   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16238 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2005-05-23, 21:29   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Arrow

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)
R.D. Silverman is offline   Reply With Quote
Old 2005-05-24, 04:20   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3·787 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2005-05-24, 16:27   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

54416 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2005-05-24, 16:43   #5
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3·5·61 Posts
Default

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
T.Rex is offline   Reply With Quote
Old 2005-05-24, 17:23   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

33×233 Posts
Default

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.
rogue is online now   Reply With Quote
Old 2005-05-24, 17:50   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

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?
R.D. Silverman is offline   Reply With Quote
Old 2005-05-24, 18:02   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Thumbs up

Quote:
Originally Posted by T.Rex

<SNIP>

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.......
R.D. Silverman is offline   Reply With Quote
Old 2005-05-24, 18:23   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

Quote:
Originally Posted by R.D. Silverman

<snip>

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
already go beyond the state-of-the-art. They are more than adequate
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.
R.D. Silverman is offline   Reply With Quote
Old 2005-05-24, 19:33   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

23×113 Posts
Default

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
xilman is online now   Reply With Quote
Old 2005-05-24, 21:23   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×337 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Discussion on Cunningham tables: Requests etc. Mystwalker Cunningham Tables 277 2018-11-28 02:59
Extensions to Cunningham tables Raman Cunningham Tables 87 2012-11-14 11:24
Extended Cunningham tables Zeta-Flux Factoring 2 2008-03-03 18:34
Cunningham Tables @mersenneforum.org v2.0 garo Cunningham Tables 3 2006-07-04 08:00
New Cunningham Tables forum. 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.