20191004, 22:56  #34 
Aug 2005
Seattle, WA
1,597 Posts 

20191005, 12:53  #35 
Feb 2017
Nowhere
2·3·11·59 Posts 
Thanks to R.D. Silverman and jyb for the references.
As it turns out, I've actually had both of Bent's papers in my files for over a decade. I'd forgotten there were two basic identities. Now that I'm reviewing the papers, I even vaguely recall having plowed through them at the time I originally downloaded them. There are a few remaining algebraic details about the specific application to generalized Lucas numbers, but I'm sure I can work these out. BTW, looking at this stuff made me think of a longstanding question: For which squarefree N > 1 does the fundamental unit of the quadratic field Q(sqrt(N)) have norm 1? It is well known, of course, that that N = 2, or N = p, a prime congruent to 1 (mod 4) fills the bill. And, of course, it is necessary that 1 be a quadratic residue of every prime factor of N. But beyond that, I'm not sure what has been found. Last fiddled with by Dr Sardonicus on 20191005 at 12:56 Reason: Add necessary condition 
20191007, 13:01  #36 
Feb 2017
Nowhere
2×3×11×59 Posts 
There is also the formula in this "Chinese paper" on Aurifeuillian factorizations of numbers of the form

20200827, 13:09  #37  
Dec 2011
11×13 Posts 
Quote:
Jumping to the example at the end, the paper demonstrates the factorization of a certain 362digit number into the product of a 181digit number times a 182digit number. Although I was unaware of this 1999 paper, my software cracked the Phi function (Brent's notation) of 44^253+1 into the same 181 and 182digit L and M components using the methods of Brent's 1993 and 1995 papers, which I referenced a few posts back. The M component had a 46digit factor, which I obtained via ECM with B1=43M on January 16, 2013. The remaining 116digit composite was factored by me using GNFS on January 21, 2013. (The penultimate factor of the L component contained 21 digits.) [I'm not suggesting I was the first to perform any of this factorization  merely that I had an interest and I happen to have factored this number.] Based on one example, the results of this "new class" are the same as results using traditional methods. Does anybody know if there are any cases where this method can find additional factorizations not found by a good understanding of Brent's methods? If so, I'll try to more fully understand the referenced 1999 paper. Last fiddled with by rcv on 20200827 at 13:22 

20200828, 00:06  #38  
Feb 2017
Nowhere
2×3×11×59 Posts 
Quote:
Some years back I computed an Aurifeuillian factorization using the formula given in an earlier paper (it computed the usual polynomial factors IIRC), then by using the formula in the "Chinese paper." The "Chinese paper" formula was ten times faster. I asked about "homogeneous" versions of the formula for Aurifeuillian facroes "homogeneous Cunningham numbers" but my memory fails me on what the several responses revealed. 

20200828, 01:39  #39  
Dec 2011
11×13 Posts 
Quote:
As far as formulae for Homogeneous Cunningham numbers, I've had formulae for the L and M terms for HC numbers up to the bases in Paul Leyland's tables for several years. I notice Paul's HC page recently (~2 years ago) provides support for Aurifeuillian factors and provides specific algebraic formulae for the applicable Aurifeuillian factors. I never attempted to derive a general formula to split higherbase HC numbers into their Aurifeuillian components, since the bases have remained very small and stagnant. Last fiddled with by rcv on 20200828 at 01:42 

20200828, 14:34  #40 
Feb 2017
Nowhere
2·3·11·59 Posts 
The algebraic polynomial factorizations are well known "in theory." If n is odd, substituting for x in the cyclotomic polynomial yields a polynomial that splits into two Aurifeuillian polynomial factors A(x) and A(x). (For n = 4, substituting 2x^{2} for x in x^{2} + 1 does the trick.)
For example, substituting 3*x^2 for x in x^2 + x + 1 gives 9*x^4  3*x^2 + 1, which factors as (3*x^2 + 3*x + 1)*(3*x^2  3*x + 1). If you use this algebraic factorization to compute the factors in a numerical instance with n of any size, you have to be able to evaluate at least one of the polynomials at the appropriate argument value. Previous approaches were based on, for example, computing the coefficients as efficiently as possible. The formula in the "Chinese paper," however, is not based on finding or evaluating the algebraic polynomial factors. It uses instead the evaluation of expressions that look Gauss sums, and expresses the factors as gcd's. The result that the gcd's actually give the Aurifeuillian factors is what is proven in the paper. Whether you understand why the formula works (and I don't), it is much easier to use than methods requiring evaluating the Aurifeuillian factor polynomials. I note that the paper only applies directly to numerical Aurifeuillian factorizations of M^n + or  1; however, as is well known, this factorization "cuts across" the usual cyclotomic factors. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Aurifeuillian Factors of n^x±1?  Stargate38  Factoring  6  20120305 06:05 
algorithms for special factorizations  jjcale  Factoring  6  20110728 02:06 
Schinzel's Aurifeuillian style factorizations?  wblipp  Math  2  20100815 20:33 
Why do these P+1 factorizations work?  Mr. P1  GMPECM  5  20091011 12:44 
lower bounds on incomplete factorizations  J.F.  Factoring  3  20080614 18:58 