 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Cunningham Tables (https://www.mersenneforum.org/forumdisplay.php?f=51)

 Raman 2008-06-29 11:05

Aurifeuillian Factorizations

[quote=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)$$
[/quote]

(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 [I]think[/I] the Aurefeuillian factors for base N come from the factorisation of [TEX]N^N x^{2N} \pm 1[/TEX] 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 [URL="http://www.alpertron.com.ar/ECM.HTM"]ECM factoring applet[/URL] I used [URL="http://wwwmaths.anu.edu.au/~brent/pub/pub135.html"]Richard Brent's method[/URL] for computing the coefficients of the Aurifeuillian polynomial factors.

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

[QUOTE=fivemack;136899]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.

[/QUOTE]

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

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?

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

[QUOTE=jyb;186049]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?[/QUOTE]

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=Raman;136897](2) Suppose that I want to derive the Aurifeuillian factorization for a random base between 13 and 99. How will I do so?[/QUOTE]There are my old computations up to 50: [url]http://xyyxf.at.tut.by/aurifeuillean.pdf[/url]

To short the notation, for exapmle, (a[SUP]4[/SUP]+5a[SUP]3[/SUP]b+7a[SUP]2[/SUP]b[SUP]2[/SUP]+5ab[SUP]3[/SUP]+b[SUP]4[/SUP]) is written as {1, 5, 7, 5, 1}, and so on.

The factorization goes when the multiplier outside {...}[SUP]2[/SUP] 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)$$
[I]only when that value of n is odd[/I]
where L[sub]n[/sub] is the n[sup]th[/sup] Lucas number, and then
that F[sub]n[/sub] is the n[sup]th[/sup] 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}$$

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

The algebraic factors are derived in such a way that, if m is a factor of n,
Both b[sup]m[/sup]-1 and b[sup]m[/sup]+1 are factors of b[sup]n[/sup]-1, if n/m is even.
Only b[sup]m[/sup]-1 is a factor of b[sup]n[/sup]-1, if n/m is odd.
b[sup]m[/sup]+1 is a factor of b[sup]n[/sup]+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:
[SIZE=3](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[/SIZE]

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=Batalov;200921][I]only, by now itself?[/I][/quote]

[SIZE=3] 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
[/SIZE][SIZE=3] and then [I]under[/I] 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?

[SIZE=2](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 [/SIZE][/SIZE]$$\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=Raman;200923]Fibonacci Numbers/Lucas Numbers are not close to any power of integer at all.
[/QUOTE]

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]~
[/code]

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 [url]http://en.wikipedia.org/wiki/Perrin_number[/url].

All times are UTC. The time now is 21:39.