Factoring humongous Cunningham numbers

[henryzz]

Originally Posted by bsquared

It splits trivially. The cofactor is (probably) prime:

5709159772448037211922834074597972300554167586081064642060063215601487922318323

Can you give an example of how Aurifeuillian factorizations work for homegeneous cunninghams or share your script?

not just probably
i proved it with:
http://www.alpertron.com.ar/ECM.HTM

[fatphil]

Originally Posted by R.D. Silverman

11,9+ for odd multiples of 11 (not 99 because 9 is already a square)

Weird, I get an Aurefeuillian factorisation for 99 too:

? factor(hf(11,9,9))

params=[11, 9, 11/9, 1/3, 11, -1, 198]

[[5750932177, 1; 104907806276834514493, 1],
[100981, 1; 251857, 1; 26343084072127026078073, 1]]

I currently have 2 simple scripts. One works for half the candidates, another works for about a half, but with a reasonable overlap. Many of the cases that you listed still require further tweaking to one of my scripts, but that's mostly just sign fiddling. However, I'm hoping to unify the logic so that there's just one script and it works out exactly what needs to be done. Presently I'm using
polynomialfactors = factor(polsubst(polcyclo(n),x,aur*x^2)))[,1]~
numericfactors = subst(polynomialfactors, x, sq)*fudge
for suitably chosen n, aur, sq, fudge dependent on the two bases and the index. sq's basically the squared part, and aur is the non-square part.

This is a bit slow as it relies on polynomial factoring, which is at least pretty swift compared to integer factoring. Dr. Sardonicus might investigate if there's a Gauss sum representation which would be practically instant to evaluate. Bob - do you think Gauss sums are a worthwhile thing to look at, or do you think it's a no-hoper?

[R.D. Silverman]

Originally Posted by fatphil

Weird, I get an Aurefeuillian factorisation for 99 too:

? factor(hf(11,9,9))

params=[11, 9, 11/9, 1/3, 11, -1, 198]

do you think it's a no-hoper?

The last time that I looked, 99 was an odd multiple of 11.......

[fatphil]

Originally Posted by R.D. Silverman

The last time that I looked, 99 was an odd multiple of 11.......

Are you familiar with the concept of who paragraphs keep related sentences together, and by extension, multiple paragraphs can be used to keep less-related sentences separate from each other?

If so, why did you keep the first paragraph, and only the final sentence of my final paragraph, thereby chopping out the immediately preceding context for the final question and giving it an entirely different context? In particular, what on earth made you think that '99' was in any related to that final question?!

And oddly, I think you'll find that I'm the one (along with Sun et al., and Wagstaff), who is saying that 11^99+9^99 admits an Aurefeuillian factorisation, and you, Gauss, and Kraitchik (and probably Brent too), who are avoiding that number with your "not 99 because 9 is already a square" and "squarefree n" comments.

Anyway, the question, this time containing all necessary context in one sentence was:
"Do you think that there is a way to express the Aurefeuillian factorisations of homogeneous cyclotomics in terms of trivially-calculable Gauss sums, in the same way that simple n-th root-of-unity cyclotomics' factors can be, rather than having to resort to heavy, but certainly tractible, polynomial factorisation?"

[R.D. Silverman]

Originally Posted by fatphil

Are you familiar with the concept of who paragraphs keep related sentences together, and by extension, multiple paragraphs can be used to keep less-related sentences separate from each other?

If so, why did you keep the first paragraph, and only the final sentence of my final paragraph, thereby chopping out the immediately preceding context for the final question and giving it an entirely different context? In particular, what on earth made you think that '99' was in any related to that final question?!

And oddly, I think you'll find that I'm the one (along with Sun et al., and Wagstaff), who is saying that 11^99+9^99 admits an Aurefeuillian factorisation, and you, Gauss, and Kraitchik (and probably Brent too), who are avoiding that number with your "not 99 because 9 is already a square" and "squarefree n" comments.

Anyway, the question, this time containing all necessary context in one sentence was:
"Do you think that there is a way to express the Aurefeuillian factorisations of homogeneous cyclotomics in terms of trivially-calculable Gauss sums, in the same way that simple n-th root-of-unity cyclotomics' factors can be, rather than having to resort to heavy, but certainly tractible, polynomial factorisation?"

Your final sentence asserts facts that are not in evidence. One can get
the coefficients simply by solving some linear simultaneous equations.

[fatphil]

Originally Posted by R.D. Silverman

Your final sentence asserts facts that are not in evidence. One can get
the coefficients simply by solving some linear simultaneous equations.

Which bit's not in evidence? The Gauss sums are from Sun et al. However, they might be completely unnecessary, depending on how the other lead you provide.

It seems as if you final sentence is referring to:
http://wwwmaths.anu.edu.au/~brent/pub/pub127.html
http://wwwmaths.anu.edu.au/~brent/pub/pub135.html

I'll grab them and give them a read. They're quite possible more efficient than polynomial factorisation, and worth looking into. Thanks.

[xilman]

An update is in progress as I type. There are 166 composites left in the main tables now.


Paul

[Jeff Gilchrist]

Originally Posted by xilman

An update is in progress as I type. There are 166 composites left in the main tables now.

Are you updating the tables here: http://www.leyland.vispa.com/numth/f.../anbn/main.htm

[xilman]

Originally Posted by Jeff Gilchrist

Are you updating the tables here: http://www.leyland.vispa.com/numth/f.../anbn/main.htm

Yup.

[xilman]

I've just posted the last update of 2008.


Paul

[Andi47]

Originally Posted by xilman

I've just posted the last update of 2008.


Paul

Can you please put a link to the reservation page at the tables-page? It is otherwise quite tricky to find it (digging through a HUGE number of posts in this thread...), when you don't have a bookmark (yet).