Factorization attempt to a c163 - a new Odd Perfect Number roadblock

[jchein1]

Currently, I am attempting to prove that an Odd Perfect Number must have at least 9 distinct prime factors (I did 8 in 1979). I need to get just one factor out of a c163 from the L Aurifeillian of 17^289-1 or alternatively prove that c163 has at most 4 factors (i.e. to show that c163 has no factor less than c163^(1/5)) by a non-probabilistic algorithm.

Note: If someone can prove that the c163 has at most 3 factors that would be even better for my work.

I just completed the 2614th curve at the 35 digits level. The completed factorization of (17^289-1)/16 is

10949 * 1749233 * 2699538733 *  8093 * 202879 * 21366108595042598039019343 * 1268289320653338013663048107658421895784820383933483845536741745292852579037241336594064422676519255617544021091795698651078540915868211167 *

1080976398676005497687700789001811475732289777254501989753747835521426921182991116146472692199375816076769108716604114107484303070529988526405561481325009425864203  (163-digit composite).

The computer output from Dario Alpern’s (http://www.alpertron.com.ar/ECM.HTM) ecm program is

Factoring 1080976398676005497687700789001811475732289777254501989753747835521426921182991116146472692199375816076769108716604114107484303070529988526405561481325009425864203 (163 digits) 

Limit (B1=11000000; B2=1100000000)    Curve 2614
Digits in factor:      >= 15    >= 20    >= 25    >= 30    >= 35    >= 40
Probability:            100%     100%     100%     100%      99%      40%

Paul Zimmermann tried about 1700 curves with B1=3000000, B2=4016636513 on the c163 and suggested that I post this query on your help list. William Lipp made exactly same suggestion. Any advice would be welcome. Thank you in advance.

Joseph E.Z. Chein

[xilman]

Originally Posted by jchein1

Currently, I am attempting to prove that an Odd Perfect Number must have at least 9 distinct prime factors (I did 8 in 1979). I need to get just one factor out of a c163 from the L Aurifeillian of 17^289-1 or alternatively prove that c163 has at most 4

Any advice would be welcome. Thank you in advance.

Joseph E.Z. Chein

A c163 is feasible, though non-trivial, by GNFS these days. That would settle the question of its factorization.

I think I'd want to see ECM work done to around the p50 level before recommending it be done by GNFS.

Paul

[philmoore]

So did the 139 digit number come from some sort of Aurifeuillean factorization? What are the polynomials of those factors? I don't know, but I'm sure that others will, whether or not SNFS might be of use here.

[R.D. Silverman]

Originally Posted by philmoore

So did the 139 digit number come from some sort of Aurifeuillean factorization? What are the polynomials of those factors? I don't know, but I'm sure that others will, whether or not SNFS might be of use here.

It is either A + B or A-B with A,B polynomials with coefficients:

A : (1, 9, 11, -5, -15, -5, 11, 9, 1) (degree 8 in x = 17^H)

B: 17^K(1, 3, 17, -3, -3, 17, 3, 1) (degree 7 in 17^H) with H = 2K-1 , H = 17

You should be able to reduce this octic to a quartic in (x+17/x). I don't
have Macsyma or Maple to do the manipulation, and I would hate to do it
by hand. A C163 via SNFS is quite easy.

[Zeta-Flux]

Joseph,

I took a look at this problem a few summers ago. I'm glad someone is finally tackling it! It is about time. When I looked at it, I was just going to show that 3 and 5 both had to divide an odd perfect number of 8 factors. But a friend of mine already did it (he is a fellow grad student here at Berkeley-but didn't publish that result). We were thinking about eventually trying to do the whole shibang, but never got around to it.

I'm currently using my computer to do another SNFS factorization, but once that is done (should stop tomorrow) I'd be willing to take a crack at your number if you'd like (or if nobody else gets to it first).

By the way, I'm wondering why you even need to factor that number. It looks like [17^289 -1]/16 already has at least 8 factors. Thus any OPN number N with 17 | N and [17^289-1]/16 | N must have at least 9 factors. So why do you need to factor this number?

Best,
Pace Nielsen

[Mystwalker]

I did a P-1 run with B1=1100000000 (11e8), B2=593887176568 (gmp-ecm default) - no factor found.
More is not wise with 1 GB RAM...

[philmoore]

I'm not getting the Aurifeuillian factorization to work out. I should be getting A^2-B^2 to be equal to (17^289-1)/(17^17-1), right? I get the first 50 or so digits the same, but after that, the agreement ends. I'm not sure if I am misinterpreting something or the coefficients aren't quite right.

A and B are symmetric polynomials, but could the large coefficient 17^9 multiplying B cause problems?

202879 is the only known small factor of this one, so if SNFS is the way to go, it will be a 168-digit factorization.

[philmoore]

Originally Posted by R.D. Silverman

It is either A + B or A-B with A,B polynomials with coefficients:

A : (1, 9, 11, -5, -15, -5, 11, 9, 1) (degree 8 in x = 17^H)

B: 17^K(1, 3, 17, -3, -3, 17, 3, 1) (degree 7 in 17^H) with H = 2K-1 , H = 17

You should be able to reduce this octic to a quartic in (x+17/x). I don't
have Macsyma or Maple to do the manipulation, and I would hate to do it
by hand. A C163 via SNFS is quite easy.

Here's the problem: the second polynomial should read:

B: 17^K(1, 3, 1, -3, -3, 1, 3, 1) (degree 7 in 17^H) with H = 2K-1 , H = 17

Now I get A^2 - B^2 coming out correctly.

I am having trouble reducing the octic to a quartic, though. The octic is A +/- B, and even though A and B are symmetric, because they are of different degrees, the sum or difference is not. Ideas, anyone?

[akruppa]

That's exactly where I got stuck last night.

Bob's suggestion was to not do a polynomial in (1+1/x), which would require the coefficients to be symmetric, but in (1+17/x). Unfortunately, I didn't manage to make a quartic this way, either - the coefficients never matched up.

The octic would be useless for sieving - the coefficients are quite large (not that much smaller than they'd be for GNFS) and the degree too high...

Alex

[JHansen]

Can someone with Maple experience please explain the best way to manipulate polynomial expressions like that in Maple. I've been fiddleing with the algsubs command, but it doesn't seem to do what I want.

I've tried playing around with the 12'th degree polynomial you get by giving Maple the command

normal(x^13+1)/(x+1);

This can be reduced to degree 6. This I know how to do. What I don't know is how to make Maple do it. If I multiply by x^(-6) to get the symmetric polynomial I thought of something like

algsubs(1/x+x=y,x^12-x^11+x^10-x^9+x^8-x^7+x^6-x^5+x^4-x^3+x^2-x+1);

but then Maple returns an expression that still contains x. I've read in the help pages, that you manually have to replace negative exponents, but this does not involve a pure negative exponent, since I'm replacing x+x^(-1) by y.

What do I do?

--
Cheers,
Jes

[R.D. Silverman]

Originally Posted by philmoore

Here's the problem: the second polynomial should read:

B: 17^K(1, 3, 1, -3, -3, 1, 3, 1) (degree 7 in 17^H) with H = 2K-1 , H = 17

Now I get A^2 - B^2 coming out correctly.

I am having trouble reducing the octic to a quartic, though. The octic is A +/- B, and even though A and B are symmetric, because they are of different degrees, the sum or difference is not. Ideas, anyone?

Thanks for the correction; It shows that one shouldn't do the
computations by hand........

Unfortunately, I don't have any CA software available.

Try expressing the octic as a quartic in (ax + b/x) for some a,b. I'm not
sure if this will work. Maybe Peter Montgomery has some ideas; he is much
more intuitive about such manipulations than I am.... You could also try
a quartic in (a * 17^c + b * 17^-d) for different c,d.