How much work would these numbers take?

[jasong]

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]

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.

[xilman]

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

[ValerieVonck]

Jasong,

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

Regards
C.

[R.D. Silverman]

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.

[ValerieVonck]

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

[smh]

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.

[R.D. Silverman]

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.

[jasonp]

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

[ValerieVonck]

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.

[xilman]

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