Factorization of 2,689+.c170: p59 * p112

[dleclair]

On Friday December 17th 2004, the factorization of 2^689+1 was completed:

Original number had 170 digits:
36853708864631493391644250804985251280305803918595388924243234412509638519371705475313062632915374659511065091204901783709434713933478948265259721213748840180591280153129

Probable prime factor 1 has 112 digits:
3086847660174709759161235271337878300483574045797182130230663823691355075162921322245761098593210884070961472739

Probable prime factor 2 has 59 digits:
11938946433963522169904424491139802212517997000669460027011

This project was particularly easy, requiring only about 4 days of sieving time.

The polynomials used were:

9007199254740992X - 81129638414606681695789005144065

and

X^6 - X^5 - 5X^4 + 4X^3 + 6X^2 - 3X - 1

About 56 million relations were collected which was substantially more than the minimum required.

Removal of duplicates and singletons reduced this to about 43.5M relations on 27.7M large primes ideals on primes > 10M.

Multiple passes of clique removal reduced this large set down to 4,245,185 relations.

Merging of the relations further reduced this to a matrix with that was about 1.14M square but quite dense with an average relation set weight of 69.96.

This matrix and required about 2.5 days on an Athlon XP 2500+ machine to run to completion.

The factors were found on the first dependency after about 18 minutes.

Many thanks to all the NFSNET sievers!

[JHansen]

Originally Posted by dleclair

The polynomials used were:

9007199254740992X - 81129638414606681695789005144065

and

X^6 - X^5 - 5X^4 + 4X^3 + 6X^2 - 3X - 1

Can you tell a little about how you found these polys? What does one look for in a number to be able to pull out a sextic like that?

---
Cheers,
Jes

[xilman]

Originally Posted by JHansen

Can you tell a little about how you found these polys? What does one look for in a number to be able to pull out a sextic like that?

OK, a little clue. Enough to get you started perhaps, but not enough to spoil the enjoyment of working it out yourself.

Observe that 689 = 13 * 53.

More clues later if you really can't get further on your own.


Paul

[JHansen]

Originally Posted by xilman

More clues later if you really can't get further on your own.


Paul

I think I'll have to through the towel in the ring now. :

The clue about 689=13*53 hasn't helped a lot

I tried to look at the linear poly, which is 2^53*X-(2^106+1). It's root mod N is some number 256...369 (207 digits), that I couldn't plug in the sextic, since my pocket calc can't handle numbers larger then 2048 bits, and I don't have access to any multiprecision software until after jan 5.

I tried to see if the sextic has an obvious root, like 2^13, 2^53 or 2^106, but no luck there either.

I need a hint as to what direction to look, so a clue more, please, but only that! I'd still like to find the answer myself

-----
Cheers,
Jes

[xilman]

Originally Posted by JHansen

I think I'll have to through the towel in the ring now. :

The clue about 689=13*53 hasn't helped a lot

I tried to look at the linear poly, which is 2^53*X-(2^106+1). It's root mod N is some number 256...369 (207 digits), that I couldn't plug in the sextic, since my pocket calc can't handle numbers larger then 2048 bits, and I don't have access to any multiprecision software until after jan 5.

I tried to see if the sextic has an obvious root, like 2^13, 2^53 or 2^106, but no luck there either.

I need a hint as to what direction to look, so a clue more, please, but only that! I'd still like to find the answer myself

-----
Cheers,
Jes

Ok. Here's taking the hint one stage further. x^pq+1 is divisible by x^p+1 when q is odd. In particular, x^689+1 is divisible by x^53+1. Perform the division and see what you get. See if you can correlate that with your observation about the linear polynomial.

It may not seem like it yet, but you are making progress so keep going,


Paul

[Wacky]

Originally Posted by JHansen

The clue about 689=13*53 hasn't helped a lot

I tried to look at the linear poly, which is 2^53*X-(2^106+1). It's root mod N is some number 256...369 (207 digits),

Let me suggest that you try to solve this with algebra rather than numerically.

2^53 is obviously significant. Try substituting "Y" for 2^53 in both polynomials and the original Cunningham number.

[akruppa]

I don't think how to find the sextic is obvious at all for someone who doesn't know the required trick. Therefore, another hint: try to get a degree 12 polynomial first, using xilman's and Wacky's suggestions.

Alex

[JHansen]

Here's where I got to:

Letting N:=2^689+1 and y:=2^53, we have N=y^13+1. This factor as (y+1)\sum_{n=0}^{12} (-1)^n y^n. Is this the 12'th degree poly you were talking about, Alex?

But how to convert that 12'th degree into something managble has eluded me so far.... If there's a trick I didn't see it. Can someone please let me (and everyone else) in on the 'secret' now?


-----
Cheers,
Jes

[xilman]

Originally Posted by JHansen

Here's where I got to:

Letting N:=2^689+1 and y:=2^53, we have N=y^13+1. This factor as (y+1)\sum_{n=0}^{12} (-1)^n y^n. Is this the 12'th degree poly you were talking about, Alex?

But how to convert that 12'th degree into something managble has eluded me so far.... If there's a trick I didn't see it. Can someone please let me (and everyone else) in on the 'secret' now?


-----
Cheers,
Jes

You're getting there. Now try working out the root of the linear polynomial. In particular, start by dividing it by 2^53.

Paul

[xilman]

Originally Posted by xilman

You're getting there. Now try working out the root of the linear polynomial. In particular, start by dividing it by 2^53.

Paul

Another clue. You've found out how to get a degree-12 polynomial, but you want a degree-6 version. So divide the polynomial you have by x^6 and regroup terms. Play around with it a bit and, in particular, see whether you can make a useful change of variable.

That's a big hint!

Paul

[Wacky]

Originally Posted by JHansen

If there's a trick I didn't see it. Can someone please let me (and everyone else) in on the 'secret' now?

Jes,

Please do not feel that your request for help has fallen on deaf ears.

Yes, we (at least Paul(Xilman), Alex, and myself) could "let you in on the secret" by simply expressing the two polynomials in a simple form. However, I think that there is significant value in letting you "work it out for yourself". In fact, you expressed some desire for this approach yourself.

Therefore, I, and knowing them, I presume also Paul and Alex, would prefer to see you expend the effort to understand the math and discover the particulars for yourself.

The transform that works in this case is but one possible form that can be used. If you can recognize the general technique, then you may be able to apply that generalization to other factorizations that have not yet been done.

It is my hope that you can learn from the exercise so that, in the future, you might lead rather than just following.

As you discover facts about this factorization, feel free to continue to express whatever you have found. And do not hesitate to ask for additional help when you are really "stuck". I'm sure that you will continue to receive hints as long as you are trying to work it out.

Richard