Aurifeuillian Factorizations

Raman · 2008-06-29, 11:05

Quote:

Originally Posted by Lucas

$ (2^{4k-2}+1) = (2^{2k-1}-2^{k}+1) (2^{2k-1}+2^{k}+1) $
$(3^{6k-3}+1) = (3^{2k-1}+1) (3^{2k-1}-3^{k}+1) (3^{2k-1}+3^{k}+1) $
$(5^{10k-5}-1) = (5^{2k-1}-1) (5^{4k-2}-5^{3k-1}+3.5^{2k-1}-5^{k}+1) (5^{4k-2}+5^{3k-1}+3.5^{2k-1}+5^{k}+1) $
$(6^{12k-6}+1) = (6^{4k-2}+1) (6^{4k-2}-6^{3k-1}+3.6^{2k-1}-6^{k}+1) (6^{4k-2}+6^{3k-1}+3.6^{2k-1}+6^{k}+1) $
$(7^{14k-7}+1) = (7^{2k-1}+1) (7^{6k-3}-7^{5k-2}+3.7^{4k-2}-7^{3k-1}+3.7^{2k-1}-7^{k}+1) (7^{6k-3}+7^{5k-2}+3.7^{4k-2}+7^{3k-1}+3.7^{2k-1}+7^{k}+1) $
$(10^{20k-10}+1) = (10^{4k-2}+1) (10^{8k-4}-10^{7k-3}+5.10^{6k-3}-2.10^{5k-2}+7.10^{4k-2}-2.10^{3k-1}+5.10^{2k-1}-10^{k}+1) (10^{8k-4}+10^{7k-3}+5.10^{6k-3}+2.10^{5k-2}+7.10^{4k-2}+2.10^{3k-1}+5.10^{2k-1}+10^{k}+1) $
$(11^{22k-11}+1) = (11^{2k-1}+1) (11^{10k-5}-11^{9k-4}+5.11^{8k-4}-11^{7k-3}-11^{6k-3}+11^{5k-2}-11^{4k-2}-11^{3k-1}+5.11^{2k-1}-11^{k}+1) (11^{10k-5}+11^{9k-4}+5.11^{8k-4}+11^{7k-3}-11^{6k-3}-11^{5k-2}-11^{4k-2}+11^{3k-1}+5.11^{2k-1}+11^{k}+1) $
$(12^{6k-3}+1) = (12^{2k-1}+1) (12^{2k-1}-2^{2k-1}.3^{k}+1) (12^{2k-1}+2^{2k-1}.3^{k}+1) $

(1) Why the Aurifeuillian factorization of 5 alone, one lesser than a power of 5, while others are one greater than the other powers?
(2) Suppose that I want to derive the Aurifeuillian factorization for a random base between 13 and 99. How will I do so?

fivemack · 2008-06-29, 12:16

I don't know why 5- has the special form and 5+ doesn't; since 13- has a special form and 13+ doesn't, and the same holds for 17 and 29, I suspect it's to do with being =1 mod 4.

I think the Aurefeuillian factors for base N come from the factorisation of $N^N x^{2N} \pm 1$ as a polynomial, so you can just factorize that in something like pari-gp; and you have the symmetry properties (generally in terms of Nx+1/x) so you could make a sextic SNFS polynomial for 14^182+1. Don't know whether 14^182+1 has already been done by ECM.

alpertron · 2008-06-29, 13:39

In my ECM factoring applet I used Richard Brent's method for computing the coefficients of the Aurifeuillian polynomial factors.

R.D. Silverman · 2008-06-29, 15:38

Quote:

Originally Posted by fivemack

I don't know why 5- has the special form and 5+ doesn't; since 13- has a special form and 13+ doesn't, and the same holds for 17 and 29, I suspect it's to do with being =1 mod 4.

YES. The Aurefeullian is on the minus side for b = 1 mod 4.
Also for bases that are k^2p where p = 1 mod 4. (e.g. 2^2 * 5)

See Riesel's book.

jyb · 2009-08-17, 18:23

I've been looking at the way in which the primitive parts of Aurifeuillian factors are calculated. In the Cunningham book, III C 2, it states the following:

With base b and exponent n with odd part m:

$L_n = \prod_{d|m}{'}[(L_{n/d}*)^{\eps_d}(M_{n/d}*)^{1-\eps_d}]$
$M_n = \prod_{d|m}{'}[(L_{n/d}*)^{1-\eps_d}(M_{n/d}*)^{\eps_d}]$

where

$\eps_d = \frac{1 + (b|d)}{2}$

and "the prime on the product sign indicates that the product is taken over the divisors d of m such that (b,d)=1."

It mentions that it's stating these formulas without proof, which is significant because I believe that they are not actually correct. In particular, if b is a multiple of an odd square, then these formulas will fail to find some algebraic factors. Of course, it's worth noting that none of the bases used in the Cunningham project actually have this property, so this isn't a problem that would have affected that project.

As an example, consider the smallest base which is a multiple of an odd square (and not square itself, of course), 18. With b = 18, we have

$L_6 = L_6*$ .

I.e. these formulas find no algebraic factors at all because the product excludes all divisors d except 1. But in fact,

$L_6 = L_6*M_2*$

More generally, for b = 18 any time n is a multiple of 3, there will be missed factors.

To correct this, let b' be the squarefree part of b. (E.g., for b = 18, b' = 2). Then we should have

$\eps_d = \frac{1 + (b'|d)}{2}$

and the prime on the product sign indicates that it includes divisors d of m where (b',d)=1 (rather than (b,d)=1). Then the formulas for L and M above would look the same.

Any comments? Is this common knowledge that I'm only rediscovering now?

R.D. Silverman · 2009-08-17, 23:07

Quote:

Originally Posted by jyb

I've been looking at the way in which the primitive parts of Aurifeuillian factors are calculated. In the Cunningham book, III C 2, it states the following:

With base b and exponent n with odd part m:

$L_n = \prod_{d|m}{'}[(L_{n/d}*)^{\eps_d}(M_{n/d}*)^{1-\eps_d}]$
$M_n = \prod_{d|m}{'}[(L_{n/d}*)^{1-\eps_d}(M_{n/d}*)^{\eps_d}]$

where

$\eps_d = \frac{1 + (b|d)}{2}$

and "the prime on the product sign indicates that the product is taken over the divisors d of m such that (b,d)=1."

It mentions that it's stating these formulas without proof, which is significant because I believe that they are not actually correct. In particular, if b is a multiple of an odd square, then these formulas will fail to find some algebraic factors. Of course, it's worth noting that none of the bases used in the Cunningham project actually have this property, so this isn't a problem that would have affected that project.

As an example, consider the smallest base which is a multiple of an odd square (and not square itself, of course), 18. With b = 18, we have

$L_6 = L_6*$ .

I.e. these formulas find no algebraic factors at all because the product excludes all divisors d except 1. But in fact,

$L_6 = L_6*M_2*$

More generally, for b = 18 any time n is a multiple of 3, there will be missed factors.

To correct this, let b' be the squarefree part of b. (E.g., for b = 18, b' = 2). Then we should have

$\eps_d = \frac{1 + (b'|d)}{2}$

and the prime on the product sign indicates that it includes divisors d of m where (b',d)=1 (rather than (b,d)=1). Then the formulas for L and M above would look the same.

Any comments? Is this common knowledge that I'm only rediscovering now?

You appear to be correct. It certainly is new to me.

I suggest you send this to Sam Wagstaff.

Nice catch!

XYYXF · 2009-08-22, 02:17

Quote:

Originally Posted by Raman

(2) Suppose that I want to derive the Aurifeuillian factorization for a random base between 13 and 99. How will I do so?

There are my old computations up to 50: http://xyyxf.at.tut.by/aurifeuillean.pdf

To short the notation, for exapmle, (a⁴+5a³b+7a²b²+5ab³+b⁴) is written as {1, 5, 7, 5, 1}, and so on.

The factorization goes when the multiplier outside {...}² appears to be a square.

Raman · 2010-01-05, 06:39

Two more new questions:

Similar to the Aurifeuillian factorizations,
for Lucas numbers, I found out a nice factorization from the web
$L_{5n} = L_n.(5F_n^2-5F_n+1).(5F_n^2+5F_n+1)$
only when that value of n is odd
where L_n is the n^th Lucas number, and then
that F_n is the n^th Fibonacci number.
$F_n = \frac{\alpha^n-\beta^n}{\alpha-\beta}$ and $L_n = \alpha^n+\beta^n$
where those values of $\alpha = \frac{1+\sqrt 5}{2}$ and $\beta = \frac{1-\sqrt 5}{2}$

(3) Do there exist similar identities for Homogeneous Cunninghams, or other values of Fibonacci/Lucas numbers itself, besides that multiple of 5?

The algebraic factors are derived in such a way that, if m is a factor of n,
Both b^m-1 and b^m+1 are factors of bⁿ-1, if n/m is even.
Only b^m-1 is a factor of bⁿ-1, if n/m is odd.
b^m+1 is a factor of bⁿ+1, only if n/m is odd.
The same condition is true for Homogeneous Cunninghams as well as Fibonnaci/Lucas factors assuming that Fibonacci numbers are upon the minus side only, and then that the Lucas numbers are within the plus side itself, right then.

What about the algebraic factors of Aurifeuillian factorizations, how do they derive from?
To ask up the above question more clearly only:
(4) Let P be a number of form 4k-2 and let Q be an odd factor of P.
For what values of M and N do we have that 2,(Q)L dividing 2,(P)L and 2,(Q)M dividing 2,(P)M
and then what condition, do we have that 2,(Q)M dividing 2,(P)L and 2,(Q)L dividing 2,(P)M

Then, is that same condition between the values of M and N, true for other bases than 2, as well as that above Lucas factorization identity?

Raman · 2010-01-05, 07:40

It was a typo, it should be correct when that, the above entries of M and N should be replaced up by using the values of P and Q respectively.
Then, it is right now.

Quote:

Originally Posted by Batalov

only, by now itself?

For what values of P and Q do we have that 2,(Q)L dividing 2,(P)L and 2,(Q)M dividing 2,(P)M
--> When P/Q = 1 mod 8 or 7 mod 8
and then under what condition, do we have that 2,(Q)M dividing 2,(P)L and 2,(Q)L dividing 2,(P)M
--> When P/Q = 3 mod 8 or 5 mod 8
Correct?

Then, for what values of P and Q, do we have both 2,(Q)L and 2,(Q)M dividing 2,(P)L or 2,(P)M?

(5) Still not getting up how to pick up that SNFS polynomial for Fibonacci/Lucas numbers at all.
For Cunningham numbers, it is trivial that the numbers are close to a power of integer.
For Fibonacci Numbers, say take up that first hole F(1049).
Fibonacci Numbers/Lucas Numbers are not close to any power of integer at all.
Lucas Numbers are close to $\phi^n$ where $\phi$ is that golden ratio = $1+\sqrt 5 \over 2$
And then it is true that the Fibonacci numbers are exactly close to $1 \over \sqrt 5$ ratio of the Lucas numbers only...

R.D. Silverman · 2010-01-06, 13:44

Quote:

Originally Posted by Raman

Fibonacci Numbers/Lucas Numbers are not close to any power of integer at all.

Most of your notation makes no sense. I won't try to interpret it.

Use standard notation. Say what you mean.

I will however respond to the comment above.

Hint:
Fibonacci/Lucas numbers ARE very close to a perfect power of the
RATIO of two smaller Fibonacci/Lucas numbers.

fivemack · 2010-01-06, 14:34

If you know that Fibonacci numbers have an SNFS polynomial (and I tell you that this is the case), then use lattice reduction (you don't have to do anything clever, it's all implemented within pari-gp) to find the polynomial:

Code:

% gp
? F=fibonacci(1049);
? u=fibonacci(174);
? v=fibonacci(175);
? lindep([F,u^6,u^5*v,u^4*v^2,u^3*v^3,u^2*v^4,u*v^5,v^6])
%21 = [-1, 1, 0, 15, 20, 30, 18, 5]~

That is, F = u^6 + 15*u^4*v^2 + 20*u^3*v^3 + 30*u^2*v^4 + 18*u*v^5 + 5*v^6

Basically, it's a matter of linear equations:

lucas(N) = phi^N + phi^{-N}
lucas(N+1) = phi^{N+1} + phi^{-N-1}

is a linear equation (with coefficients in Q[phi]) which lets you write phi^N in terms of lucas(N) and lucas(N+1). If you use this value of phi^N to compute, say, phi^{6N-1} + phi^{-6N+1}, the coefficients of phi cancel out and you get a rational expression. See the middle section in http://en.wikipedia.org/wiki/Perrin_number.

2008-06-29, 12:16	#2
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 13×491 Posts	I don't know why 5- has the special form and 5+ doesn't; since 13- has a special form and 13+ doesn't, and the same holds for 17 and 29, I suspect it's to do with being =1 mod 4. I think the Aurefeuillian factors for base N come from the factorisation of $N^N x^{2N} \pm 1$ as a polynomial, so you can just factorize that in something like pari-gp; and you have the symmetry properties (generally in terms of Nx+1/x) so you could make a sextic SNFS polynomial for 14^182+1. Don't know whether 14^182+1 has already been done by ECM. Last fiddled with by fivemack on 2008-06-29 at 12:16

2009-08-17, 18:23	#5
jyb Aug 2005 Seattle, WA 2×3×283 Posts	Error in Cunningham Book? I've been looking at the way in which the primitive parts of Aurifeuillian factors are calculated. In the Cunningham book, III C 2, it states the following: With base b and exponent n with odd part m: $L_n = \prod_{d\|m}{'}[(L_{n/d})^{\eps_d}(M_{n/d})^{1-\eps_d}]$ $M_n = \prod_{d\|m}{'}[(L_{n/d})^{1-\eps_d}(M_{n/d})^{\eps_d}]$ where $\eps_d = \frac{1 + (b\|d)}{2}$ and "the prime on the product sign indicates that the product is taken over the divisors d of m such that (b,d)=1." It mentions that it's stating these formulas without proof, which is significant because I believe that they are not actually correct. In particular, if b is a multiple of an odd square, then these formulas will fail to find some algebraic factors. Of course, it's worth noting that none of the bases used in the Cunningham project actually have this property, so this isn't a problem that would have affected that project. As an example, consider the smallest base which is a multiple of an odd square (and not square itself, of course), 18. With b = 18, we have $L_6 = L_6$ . I.e. these formulas find no algebraic factors at all because the product excludes all divisors d except 1. But in fact, $L_6 = L_6M_2*$ More generally, for b = 18 any time n is a multiple of 3, there will be missed factors. To correct this, let b' be the squarefree part of b. (E.g., for b = 18, b' = 2). Then we should have $\eps_d = \frac{1 + (b'\|d)}{2}$ and the prime on the product sign indicates that it includes divisors d of m where (b',d)=1 (rather than (b,d)=1). Then the formulas for L and M above would look the same. Any comments? Is this common knowledge that I'm only rediscovering now?

2010-01-05, 06:39	#8
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts	Two more new questions: Similar to the Aurifeuillian factorizations, for Lucas numbers, I found out a nice factorization from the web $L_{5n} = L_n.(5F_n^2-5F_n+1).(5F_n^2+5F_n+1)$ only when that value of n is odd where L_n is the n^th Lucas number, and then that F_n is the n^th Fibonacci number. $F_n = \frac{\alpha^n-\beta^n}{\alpha-\beta}$ and $L_n = \alpha^n+\beta^n$ where those values of $\alpha = \frac{1+\sqrt 5}{2}$ and $\beta = \frac{1-\sqrt 5}{2}$ (3) Do there exist similar identities for Homogeneous Cunninghams, or other values of Fibonacci/Lucas numbers itself, besides that multiple of 5? The algebraic factors are derived in such a way that, if m is a factor of n, Both b^m-1 and b^m+1 are factors of bⁿ-1, if n/m is even. Only b^m-1 is a factor of bⁿ-1, if n/m is odd. b^m+1 is a factor of bⁿ+1, only if n/m is odd. The same condition is true for Homogeneous Cunninghams as well as Fibonnaci/Lucas factors assuming that Fibonacci numbers are upon the minus side only, and then that the Lucas numbers are within the plus side itself, right then. What about the algebraic factors of Aurifeuillian factorizations, how do they derive from? To ask up the above question more clearly only: (4) Let P be a number of form 4k-2 and let Q be an odd factor of P. For what values of M and N do we have that 2,(Q)L dividing 2,(P)L and 2,(Q)M dividing 2,(P)M and then what condition, do we have that 2,(Q)M dividing 2,(P)L and 2,(Q)L dividing 2,(P)M Then, is that same condition between the values of M and N, true for other bases than 2, as well as that above Lucas factorization identity? Last fiddled with by Raman on 2010-01-05 at 06:43 Reason: For fixing up that MIMETEX tag only, by now itself

2010-01-06, 14:34	#11
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 13×491 Posts	If you know that Fibonacci numbers have an SNFS polynomial (and I tell you that this is the case), then use lattice reduction (you don't have to do anything clever, it's all implemented within pari-gp) to find the polynomial: Code: % gp ? F=fibonacci(1049); ? u=fibonacci(174); ? v=fibonacci(175); ? lindep([F,u^6,u^5v,u^4v^2,u^3v^3,u^2v^4,uv^5,v^6]) %21 = [-1, 1, 0, 15, 20, 30, 18, 5]~ That is, F = u^6 + 15u^4v^2 + 20u^3v^3 + 30u^2v^4 + 18uv^5 + 5v^6 Basically, it's a matter of linear equations: lucas(N) = phi^N + phi^{-N} lucas(N+1) = phi^{N+1} + phi^{-N-1} is a linear equation (with coefficients in Q[phi]) which lets you write phi^N in terms of lucas(N) and lucas(N+1). If you use this value of phi^N to compute, say, phi^{6N-1} + phi^{-6N+1}, the coefficients of phi cancel out and you get a rational expression. See the middle section in http://en.wikipedia.org/wiki/Perrin_number.

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

2008-06-29, 13:39	#3
alpertron Aug 2002 Buenos Aires, Argentina 2501₈ Posts	In my ECM factoring applet I used Richard Brent's method for computing the coefficients of the Aurifeuillian polynomial factors.