mersenneforum.org Factorization attempt to a c163 - a new Odd Perfect Number roadblock
 Register FAQ Search Today's Posts Mark Forums Read

 2005-05-23, 19:51 #1 jchein1   May 2005 748 Posts Factorization attempt to a c163 - a new Odd Perfect Number roadblock 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 Code: 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 Code: 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 Last fiddled with by akruppa on 2005-05-24 at 20:24 Reason: added CODE tags to avoid horizontal scrolling
2005-05-23, 20:20   #2
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·72·109 Posts

Quote:
 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

 2005-05-23, 20:51 #3 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 21378 Posts 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.
2005-05-23, 21:16   #4
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 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.

 2005-05-23, 22:00 #5 Zeta-Flux     May 2003 60B16 Posts 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
 2005-05-23, 22:03 #6 Mystwalker     Jul 2004 Potsdam, Germany 14778 Posts 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...
 2005-05-24, 00:22 #7 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 21378 Posts 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.
2005-05-24, 05:35   #8
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts

Quote:
 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?

 2005-05-24, 06:01 #9 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 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 Last fiddled with by akruppa on 2005-05-24 at 06:02
 2005-05-24, 10:05 #10 JHansen     Apr 2004 Copenhagen, Denmark 1648 Posts 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 Code: 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
2005-05-24, 13:35   #11
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Godzilla Miscellaneous Math 8 2016-09-05 05:56 isaac Miscellaneous Math 5 2014-07-22 22:18 jchein1 Factoring 60 2006-11-25 19:38 jchein1 Factoring 14 2005-10-15 20:01 JHansen Factoring 34 2005-05-27 19:24

All times are UTC. The time now is 05:02.

Sun May 9 05:02:22 UTC 2021 up 30 days, 23:43, 0 users, load averages: 1.00, 1.47, 1.53