Factoring humongous Cunningham numbers

[xilman]

Originally Posted by smh

Can somenody explain me how to create a SNFS polynomial for these numbers?

Here's a clue: it should be all you need.

Given a^n \pm b^n == 0 mod N, divide by b^n to get (a/b)^n \pm 1 == 0 mod N. You've now got exactly the same form as for the regular Cunningham tables.

Purists can witter on about multiplicative inverses and whether they exist mod N. Such purists will also realize that if the inverse can't be found by the extended GCD algorithm a factorization of N is at hand anyway.

Paul

[Jushi]

Bob, would you mind if I also put a copy online at my page http://cage.ugent.be/~jdemeyer/cunningham/?

[Pascal Ochem]

The factors of the C98 from 3^349-2^349 are:

4168235213414369860712355318929423366202629 (pp43)
6054961803389403532431183517420804533418860819773628313 (pp55)

[Andi47]

Originally Posted by Pascal Ochem

The factors of the C98 from 3^349-2^349 are:

4168235213414369860712355318929423366202629 (pp43)
6054961803389403532431183517420804533418860819773628313 (pp55)

pp = possible prime?

Edit: Primo certifies both factors as prime within a split second

[R.D. Silverman]

Originally Posted by Jushi

Bob, would you mind if I also put a copy online at my page http://cage.ugent.be/~jdemeyer/cunningham/?

Go right ahead.

[Andi47]

Done 648 curves on 3^379+2^379 using GMP-ECM at B1=1e6 and B2=default, no factor found. Together with Silverman's ~300 curves this should have finished the 35 digit range.

(P.S.: This should read 379 (1) 5.C181 ;-) )

Now running a some curves with B1=3e6 at this number.

I have also done 300 curves on the C144 of 3^395-2^395, no factor found.

[R.D. Silverman]

Originally Posted by Andreas Schinde

<snip>

(P.S.: This should read 379 (1) 5.C181 ;-) )

Not really.

I follow the Cunningham format:

N (a,b,c...) means that 3^N + 2^N has the algebraic factors
3^a + 2^a, 3^b + 2^b, etc.

So

379 (1) C181 means that 3^379 + 2^379 has the algebraic factor
of 3^1 + 2^1. 5 is an algebraic factor. Algebraic factors do not get
directly listed. The exponents for the algebraic factors are listed inside
the parentheses.

[Greenbank]

Ah, I did wonder. Knowledge gained and all of that...

[rogue]

Originally Posted by R.D. Silverman

Not really.

I follow the Cunningham format:

N (a,b,c...) means that 3^N + 2^N has the algebraic factors
3^a + 2^a, 3^b + 2^b, etc.

So

379 (1) C181 means that 3^379 + 2^379 has the algebraic factor
of 3^1 + 2^1. 5 is an algebraic factor. Algebraic factors do not get
directly listed. The exponents for the algebraic factors are listed inside
the parentheses.

Bob, I had a question on regarding your data. Do you care if all of the factors found are prime or not? I'm asking because I believe that one of the factors you listed above was composite.

[R.D. Silverman]

Originally Posted by rogue

Bob, I had a question on regarding your data. Do you care if all of the factors found are prime or not? I'm asking because I believe that one of the factors you listed above was composite.

It is quite possible. I have not checked them.

Which factor?

[Greenbank]

400 (16,80) 19995617469086942401.C134

19995617469086942401 = 4388625601 x 4556236801