mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-05-23, 19:51   #1
jchein1
 
May 2005

3C16 Posts
Default 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
jchein1 is offline   Reply With Quote
Old 2005-05-23, 20:20   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

32·11·103 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-05-23, 20:51   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22×32×31 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2005-05-23, 21:16   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Thumbs up

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-05-23, 22:00   #5
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

5F216 Posts
Default

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
Zeta-Flux is offline   Reply With Quote
Old 2005-05-23, 22:03   #6
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3·277 Posts
Default

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...
Mystwalker is offline   Reply With Quote
Old 2005-05-24, 00:22   #7
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111002 Posts
Default

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 is offline   Reply With Quote
Old 2005-05-24, 05:35   #8
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22×32×31 Posts
Default

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?
philmoore is offline   Reply With Quote
Old 2005-05-24, 06:01   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000002 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-05-24, 10:05   #10
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

22×29 Posts
Default

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
JHansen is offline   Reply With Quote
Old 2005-05-24, 13:35   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Thumbs up

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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is this a Perfect Number ? Godzilla Miscellaneous Math 8 2016-09-05 05:56
Odd Perfect Number is 36k+9 ? isaac Miscellaneous Math 5 2014-07-22 22:18
Factorization attempt for a c110 regards Odd Multi-Perfect Numbers jchein1 Factoring 60 2006-11-25 19:38
Factorization attempt for a c214 regards Odd Perfect Numbers jchein1 Factoring 14 2005-10-15 20:01
Factorization attempt on 100^99+99^100 JHansen Factoring 34 2005-05-27 19:24

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

Sun Nov 29 02:43:56 UTC 2020 up 79 days, 23:54, 3 users, load averages: 0.94, 1.16, 1.21

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