mersenneforum.org Aurifeuillian Factorizations
 Register FAQ Search Today's Posts Mark Forums Read

2019-10-04, 22:56   #34
jyb

Aug 2005
Seattle, WA

1,567 Posts

Quote:
 Originally Posted by R.D. Silverman I don't have the reference at hand, but I know that the general case is discussed in Riesel's book. I believe that Brent wrote a paper on an algorithm to derive the coefficients.
Indeed, see post #31 above for the URLs of Brent's papers.

 2019-10-05, 12:53 #35 Dr Sardonicus     Feb 2017 Nowhere 346410 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 2019-10-05 at 12:56 Reason: Add necessary condition
 2019-10-07, 13:01 #36 Dr Sardonicus     Feb 2017 Nowhere 23×433 Posts There is also the formula in this "Chinese paper" on Aurifeuillian factorizations of numbers of the form $M^{n} \; \pm \; 1$
2020-08-27, 13:09   #37
rcv

Dec 2011

11·13 Posts

Quote:
 Originally Posted by Dr Sardonicus There is also the formula in this "Chinese paper" on Aurifeuillian factorizations of numbers of the form $M^{n} \; \pm \; 1$
First, I admit I am having a bit of difficulty with the notation in the 1999 "Chinese paper". What I am wondering is whether or not this paper really describes a "new class" of Aurifeuillian Factorizations.

Jumping to the example at the end, the paper demonstrates the factorization of a certain 362-digit number into the product of a 181-digit number times a 182-digit 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 182-digit 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 46-digit factor, which I obtained via ECM with B1=43M on January 16, 2013. The remaining 116-digit 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 2020-08-27 at 13:22

2020-08-28, 00:06   #38
Dr Sardonicus

Feb 2017
Nowhere

23×433 Posts

Quote:
 Originally Posted by rcv First, I admit I am having a bit of difficulty with the notation in the 1999 "Chinese paper". What I am wondering is whether or not this paper really describes a "new class" of Aurifeuillian Factorizations.
The factors are the same, but the gcd formula in the "Chinese paper" gives a new way to compute them.

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.

2020-08-28, 01:39   #39
rcv

Dec 2011

11×13 Posts

Quote:
 Originally Posted by Dr Sardonicus The factors are the same, but the gcd formula in the "Chinese paper" gives a new way to compute them. ...
Thank you, Dr. S. It's probably worth my effort to understand their paper.

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 higher-base HC numbers into their Aurifeuillian components, since the bases have remained very small and stagnant.

Last fiddled with by rcv on 2020-08-28 at 01:42

 2020-08-28, 14:34 #40 Dr Sardonicus     Feb 2017 Nowhere 23·433 Posts The algebraic polynomial factorizations are well known "in theory." If n is odd, substituting $(-1)^{\frac{n-1}{2}}nx^{2}$ for x in the cyclotomic polynomial $\Phi_{n}(x)$ yields a polynomial that splits into two Aurifeuillian polynomial factors A(x) and A(-x). (For n = 4, substituting 2x2 for x in x2 + 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Factoring 6 2012-03-05 06:05 jjcale Factoring 6 2011-07-28 02:06 wblipp Math 2 2010-08-15 20:33 Mr. P-1 GMP-ECM 5 2009-10-11 12:44 J.F. Factoring 3 2008-06-14 18:58

All times are UTC. The time now is 08:42.

Thu Sep 24 08:42:44 UTC 2020 up 14 days, 5:53, 0 users, load averages: 1.12, 1.19, 1.31