20080629, 11:05  #1  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts 
Aurifeuillian Factorizations
Quote:
(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 20080629 at 11:19 

20080629, 12:16  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
2^{3}×3×5×53 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 as a polynomial, so you can just factorize that in something like parigp; 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 20080629 at 12:16 
20080629, 13:39  #3 
Aug 2002
Buenos Aires, Argentina
5^{2}×53 Posts 
In my ECM factoring applet I used Richard Brent's method for computing the coefficients of the Aurifeuillian polynomial factors.

20080629, 15:38  #4  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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 20080629 at 15:40 Reason: fix \ 

20090817, 18:23  #5 
Aug 2005
Seattle, WA
61F_{16} 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: where 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 . I.e. these formulas find no algebraic factors at all because the product excludes all divisors d except 1. But in fact, 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 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? 
20090817, 23:07  #6  
Nov 2003
1110100100100_{2} Posts 
Quote:
I suggest you send this to Sam Wagstaff. Nice catch! 

20090822, 02:17  #7  
Jan 2005
Minsk, Belarus
620_{8} Posts 
Quote:
To short the notation, for exapmle, (a^{4}+5a^{3}b+7a^{2}b^{2}+5ab^{3}+b^{4}) 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 20090822 at 02:27 

20100105, 06:39  #8 
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 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. and where those values of and (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^{n}1, if n/m is even. Only b^{m}1 is a factor of b^{n}1, if n/m is odd. b^{m}+1 is a factor of b^{n}+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 4k2 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 20100105 at 06:43 Reason: For fixing up that MIMETEX tag only, by now itself 
20100105, 07:40  #9 
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. 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 where is that golden ratio = And then it is true that the Fibonacci numbers are exactly close to ratio of the Lucas numbers only... Last fiddled with by Raman on 20100105 at 07:52 
20100106, 13:44  #10  
Nov 2003
16444_{8} Posts 
Quote:
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. 

20100106, 14:34  #11 
(loop (#_fork))
Feb 2006
Cambridge, England
2^{3}·3·5·53 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 parigp) 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]~ Basically, it's a matter of linear equations: lucas(N) = phi^N + phi^{N} lucas(N+1) = phi^{N+1} + phi^{N1} 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^{6N1} + 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Aurifeuillian Factors of n^x±1?  Stargate38  Factoring  6  20120305 06:05 
algorithms for special factorizations  jjcale  Factoring  6  20110728 02:06 
Schinzel's Aurifeuillian style factorizations?  wblipp  Math  2  20100815 20:33 
Why do these P+1 factorizations work?  Mr. P1  GMPECM  5  20091011 12:44 
lower bounds on incomplete factorizations  J.F.  Factoring  3  20080614 18:58 