mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2008-06-29, 11:05   #1
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default Aurifeuillian Factorizations

Quote:
Originally Posted by Lucas
<br />
(2^{4k-2}+1) = (2^{2k-1}-2^{k}+1) (2^{2k-1}+2^{k}+1)<br />
 (3^{6k-3}+1) = (3^{2k-1}+1) (3^{2k-1}-3^{k}+1) (3^{2k-1}+3^{k}+1)<br />
 (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)<br />
 (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)<br />
 (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)<br />
 (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)<br />
 (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)<br />
 (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)<br />
(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
Raman is offline   Reply With Quote
Old 2008-06-29, 12:16   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000101100002 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2008-06-29, 13:39   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101001101012 Posts
Default

In my ECM factoring applet I used Richard Brent's method for computing the coefficients of the Aurifeuillian polynomial factors.
alpertron is offline   Reply With Quote
Old 2008-06-29, 15:38   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 \
R.D. Silverman is offline   Reply With Quote
Old 2009-08-17, 18:23   #5
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

25×72 Posts
Default 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?
jyb is online now   Reply With Quote
Old 2009-08-17, 23:07   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by jyb View Post
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!
R.D. Silverman is offline   Reply With Quote
Old 2009-08-22, 02:17   #7
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

24×52 Posts
Default

Quote:
Originally Posted by Raman View Post
(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
XYYXF is offline   Reply With Quote
Old 2010-01-05, 06:39   #8
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

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
Raman is offline   Reply With Quote
Old 2010-01-05, 07:40   #9
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

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 View Post
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
Raman is offline   Reply With Quote
Old 2010-01-06, 13:44   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by Raman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-01-06, 14:34   #11
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18B016 Posts
Default

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

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.