mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > NFSNET Discussion

 
 
Thread Tools
Old 2006-11-27, 19:42   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3·7·167 Posts
Default How much work would these numbers take?

For those of you familiar with wblipp and his Odd Perfect Number search, you probably know he's searching for factorizations to increase the minimum bounds of what an Odd Perfect Number should be above. He has had the same two numbers in the "Most Wanted" server for what seems like a long time.

The numbers are 3221^73-1 and 2801^79-1. I believe one is at the 60-digit level and the other is at the 55 or 50 digit level. I haven't run the ecm client in a while, so I'm not sure which is which.

I'm wondering how much work it it would take to attempt these factorizations with a method other than ecm. I can't even begin to understand the math involved in these other programs I've heard about, but I have a dual-core 2.8GHz Pentium-D to help in whatever way it can.

For those of you who want to argue about whether OPNs exist or not, I'm not saying they do or don't. I'm only interested in increasing the lower bounds, which are now around 10^500.

Your opinion is appreciated.
jasong is offline  
Old 2006-11-27, 20:59   #2
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3×7×167 Posts
Default

Quote:
Originally Posted by jasong View Post
The numbers are 3221^73-1 and 2801^79-1. I believe one is at the 60-digit level and the other is at the 55 or 50 digit level.
When I wrote the above, it was in reference to what type of factor the ecm curves were expected to find, if they found anything. Sorry for any confusion I may have caused.
jasong is offline  
Old 2006-11-27, 21:04   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

101011100010012 Posts
Default

Quote:
Originally Posted by jasong View Post
The numbers are 3221^73-1 and 2801^79-1. I believe one is at the 60-digit level and the other is at the 55 or 50 digit level. I haven't run the ecm client in a while, so I'm not sure which is which.

I'm wondering how much work it it would take to attempt these factorizations with a method other than ecm.
Hmm, let's see. I'm about to start thinking out loud, always an excuse to make blatantly silly mistakes for which I have to apologise afterwards. Oh well, what the hell, here goes.

3221^73-1 has 257 digits, so the naive SNFS approach would take, to a quite good approximation, rather a long while. It's smaller than the record holder, but bigger than any others so far reported. The top two, according to Sam Wagstaff's newsletters, have 274 and 248 digits.

The other number has 273 digits and so also falls between the record holders. Again, it would be distinctly non-trivial by SNFS but possible --- if anyone cared enough about it.

I don't immediately see any way of reducing the SNFS difficulty, but that's an admission of ignorance and not a statement of its impossibility.


Paul
xilman is offline  
Old 2006-11-28, 19:31   #4
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

5×132 Posts
Default

Jasong,

I suggest you do ecm on these numbers first. If you find a factor, it will probably reduce the number.

Regards
C.
ValerieVonck is offline  
Old 2006-11-28, 19:52   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by CedricVonck View Post
Jasong,

I suggest you do ecm on these numbers first. If you find a factor, it will probably reduce the number.

Regards
C.
Yes, but this won't help SNFS. Pulling a (say) 50 digit factor from a composite
in this range still leaves the cofactor too big to handle with GNFS. And
pulling out a factor does not help SNFS at all. One can only hope that
the (resulting) cofactor is prime.
R.D. Silverman is offline  
Old 2006-11-28, 21:03   #6
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

84510 Posts
Default

That's true, but if you can reduce the size to decent level, e.g. 150-180, it would stand a much better chance to do SNFS on it.
I know, the better approach is to put these number in an ecmnet server, and let several people work on it thus increasing the chance of finding a factor.

Crunching alone with that kind of HW, it will be tricky....
My $0.02
ValerieVonck is offline  
Old 2006-11-28, 21:21   #7
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

Quote:
Originally Posted by CedricVonck View Post
That's true, but if you can reduce the size to decent level, e.g. 150-180, it would stand a much better chance to do SNFS on it.
No, not true. It would get into GNFS range but doesn't help SNFS at all.
smh is offline  
Old 2006-11-29, 01:42   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by CedricVonck View Post
That's true, but if you can reduce the size to decent level, e.g. 150-180, it would stand a much better chance to do SNFS on it.
I do not reply to messages simply for the joy of hearing myself speak.
When I say something, I do so for a reason.

Allow me to ask: How many numbers have you factored with SNFS?
What qualifies you to contradict an expert on the subject????

Finding a prime factor (that leaves a composite cofactor) of a number
that is suitable for SNFS DOES NOT HELP AT ALL. NADA. ZILCH.
R.D. Silverman is offline  
Old 2006-11-29, 02:12   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Finding a prime factor (that leaves a composite cofactor) of a number
that is suitable for SNFS DOES NOT HELP AT ALL. NADA. ZILCH.
By way of explanation, if you do SNFS on a number, the polynomial you choose depends on the form of the number. Dividing known factors out before starting will destroy the special form of the number that makes SNFS possible.

jasonp
jasonp is offline  
Old 2006-11-29, 05:27   #10
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

5·132 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I do not reply to messages simply for the joy of hearing myself speak.
When I say something, I do so for a reason.

Allow me to ask: How many numbers have you factored with SNFS?
What qualifies you to contradict an expert on the subject????

Finding a prime factor (that leaves a composite cofactor) of a number
that is suitable for SNFS DOES NOT HELP AT ALL. NADA. ZILCH.
How much numbers? Probably a lot less then you. No argument there.
My largest was a c131 with SNFS difficulty of c141.

No it would probably won't help for SNFS purposes ... that you are right.

Last fiddled with by ValerieVonck on 2006-11-29 at 05:28
ValerieVonck is offline  
Old 2006-11-29, 10:59   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2B8916 Posts
Default

Quote:
Originally Posted by CedricVonck View Post
How much numbers? Probably a lot less then you. No argument there.
My largest was a c131 with SNFS difficulty of c141.

No it would probably won't help for SNFS purposes ... that you are right.
No "probably" about it. It definitely won't help. Unless, of course, you have some mathematical insights that the rest of us haven't yet acquired. If that is the case, please enlighten us. We'd be delighted to be able to improve our capabilities.

If enough factors are found by ECM to reduce the composite cofactor to, say, 160 digits factoring that residue becomes feasible by GNFS (though still not easy) and easier than SNFS on the full number.

Here I confess my laziness. I do not know the size of the unfactored portions of the two numbers and can't be bothered to find out. If you (i.e. CedricVonck) want to do something slightly useful, please find out that information and post it here. Then work out how much ECM effort is likely to be needed before any factors found will reduce the residue to GNFS range.


Paul
xilman is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Carmichael numbers and Devaraj numbers devarajkandadai Number Theory Discussion Group 0 2017-07-09 05:07
How to calculate work/effort for PRP work? James Heinrich PrimeNet 0 2011-06-28 19:29
6 digit numbers and the mersenne numbers henryzz Math 2 2008-04-29 02:05
Don't know how to work on Cunningham numbers. jasong GMP-ECM 6 2006-06-30 08:51
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25

All times are UTC. The time now is 09:24.


Thu Jan 27 09:24:11 UTC 2022 up 188 days, 3:53, 1 user, load averages: 1.42, 1.37, 1.41

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

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”