mersenneforum.org How much work would these numbers take?
 Register FAQ Search Today's Posts Mark Forums Read

 2006-11-27, 19:42 #1 jasong     "Jason Goatcher" Mar 2005 3·7·167 Posts 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.
2006-11-27, 20:59   #2
jasong

"Jason Goatcher"
Mar 2005

3×7×167 Posts

Quote:
 Originally Posted by jasong 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.

2006-11-27, 21:04   #3
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

101011100010012 Posts

Quote:
 Originally Posted by jasong 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

 2006-11-28, 19:31 #4 ValerieVonck     Mar 2004 Belgium 5×132 Posts Jasong, I suggest you do ecm on these numbers first. If you find a factor, it will probably reduce the number. Regards C.
2006-11-28, 19:52   #5
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by CedricVonck 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.

 2006-11-28, 21:03 #6 ValerieVonck     Mar 2004 Belgium 84510 Posts 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
2006-11-28, 21:21   #7
smh

"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts

Quote:
 Originally Posted by CedricVonck 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.

2006-11-29, 01:42   #8
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by CedricVonck 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.

2006-11-29, 02:12   #9
jasonp
Tribal Bullet

Oct 2004

3×1,181 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2006-11-29, 05:27   #10
ValerieVonck

Mar 2004
Belgium

5·132 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2006-11-29, 10:59   #11
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2B8916 Posts

Quote:
 Originally Posted by CedricVonck 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

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Number Theory Discussion Group 0 2017-07-09 05:07 James Heinrich PrimeNet 0 2011-06-28 19:29 henryzz Math 2 2008-04-29 02:05 jasong GMP-ECM 6 2006-06-30 08:51 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