mersenneforum.org Factoring humongous Cunningham numbers
 Register FAQ Search Today's Posts Mark Forums Read

2008-12-01, 18:41   #650
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

34×71 Posts

Quote:
 Originally Posted by bsquared It splits trivially. The cofactor is (probably) prime: Code: 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

2008-12-01, 19:27   #651
fatphil

May 2003

3×7×11 Posts

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

2008-12-01, 23:23   #652
R.D. Silverman

Nov 2003

161008 Posts

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

2008-12-01, 23:46   #653
fatphil

May 2003

3×7×11 Posts

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

2008-12-03, 17:54   #654
R.D. Silverman

Nov 2003

723210 Posts

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

2008-12-03, 18:48   #655
fatphil

May 2003

3×7×11 Posts

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

 2008-12-14, 19:19 #656 xilman Bamboozled!     "πΊππ·π·π­" May 2003 Down not across 237338 Posts An update is in progress as I type. There are 166 composites left in the main tables now. Paul
2008-12-15, 14:58   #657
Jeff Gilchrist

Jun 2003

116910 Posts

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

2008-12-15, 19:16   #658
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

3·19·179 Posts

Quote:
 Originally Posted by Jeff Gilchrist Are you updating the tables here: http://www.leyland.vispa.com/numth/f.../anbn/main.htm
Yup.

 2008-12-29, 14:57 #659 xilman Bamboozled!     "πΊππ·π·π­" May 2003 Down not across 3×19×179 Posts Last of the year I've just posted the last update of 2008. Paul
2008-12-29, 15:36   #660
Andi47

Oct 2004
Austria

7·353 Posts

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

Last fiddled with by Andi47 on 2008-12-29 at 15:38 Reason: inserted missing words

 Similar Threads Thread Thread Starter Forum Replies Last Post wpolly Factoring 26 2016-07-29 04:34 Xyzzy Cunningham Tables 42 2014-04-02 18:31 jasong GMP-ECM 6 2006-06-30 08:51 jasong Factoring 1 2006-04-03 17:18 jasong Factoring 27 2006-03-21 02:47

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

Tue Dec 1 05:59:42 UTC 2020 up 82 days, 3:10, 1 user, load averages: 1.88, 1.76, 1.70