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

2008-06-29, 11:05   #1
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Aurifeuillian Factorizations

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?

Last fiddled with by Raman on 2008-06-29 at 11:19

 2008-06-29, 12:16 #2 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 11000101100002 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
 2008-06-29, 13:39 #3 alpertron     Aug 2002 Buenos Aires, Argentina 101001101012 Posts In my ECM factoring applet I used Richard Brent's method for computing the coefficients of the Aurifeuillian polynomial factors.
2008-06-29, 15:38   #4
R.D. Silverman

Nov 2003

723210 Posts

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.

Last fiddled with by R.D. Silverman on 2008-06-29 at 15:40 Reason: fix \

 2009-08-17, 18:23 #5 jyb     Aug 2005 Seattle, WA 25×72 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_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?
2009-08-17, 23:07   #6
R.D. Silverman

Nov 2003

26·113 Posts

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!

2009-08-22, 02:17   #7
XYYXF

Jan 2005
Minsk, Belarus

24×52 Posts

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, (a4+5a3b+7a2b2+5ab3+b4) is written as {1, 5, 7, 5, 1}, and so on.

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

Last fiddled with by XYYXF on 2009-08-22 at 02:27

 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 Ln is the nth Lucas number, and then that Fn is the nth 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 bm-1 and bm+1 are factors of bn-1, if n/m is even. Only bm-1 is a factor of bn-1, if n/m is odd. bm+1 is a factor of bn+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-05, 07:40   #9
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

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

Last fiddled with by Raman on 2010-01-05 at 07:52

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

Nov 2003

26×113 Posts

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.

 2010-01-06, 14:34 #11 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 18B016 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^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.

 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 21:52.

Mon Oct 19 21:52:36 UTC 2020 up 39 days, 19:03, 1 user, load averages: 1.23, 1.46, 1.69