mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2019-10-04, 22:56   #34
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

62016 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
jyb is online now   Reply With Quote
Old 2019-10-05, 12:53   #35
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×887 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2019-10-07, 13:01   #36
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×887 Posts
Default

There is also the formula in this "Chinese paper" on Aurifeuillian factorizations of numbers of the form

M^{n} \; \pm \; 1
Dr Sardonicus is offline   Reply With Quote
Old 2020-08-27, 13:09   #37
rcv
 
Dec 2011

14310 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
rcv is offline   Reply With Quote
Old 2020-08-28, 00:06   #38
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

DDC16 Posts
Default

Quote:
Originally Posted by rcv View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-08-28, 01:39   #39
rcv
 
Dec 2011

14310 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
rcv is offline   Reply With Quote
Old 2020-08-28, 14:34   #40
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

354810 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Aurifeuillian Factors of n^x±1? Stargate38 Factoring 6 2012-03-05 06:05
algorithms for special factorizations jjcale Factoring 6 2011-07-28 02:06
Schinzel's Aurifeuillian style factorizations? wblipp Math 2 2010-08-15 20:33
Why do these P+1 factorizations work? Mr. P-1 GMP-ECM 5 2009-10-11 12:44
lower bounds on incomplete factorizations J.F. Factoring 3 2008-06-14 18:58

All times are UTC. The time now is 22:13.

Mon Oct 19 22:13:42 UTC 2020 up 39 days, 19:24, 0 users, load averages: 2.48, 2.16, 1.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.