mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2012-03-11, 14:23   #23
jcrombie
 
jcrombie's Avatar
 
"Jonathan"
Jul 2010
In a tangled web...

110101102 Posts
Default

Well, with surprisingly little effort the Aurifeuillian LM calculator is now online! (the system() command being the culprit).

So, presenting with minimalist style this page:

(Near the bottom should be the said calculator)
jcrombie is offline   Reply With Quote
Old 2012-03-11, 14:50   #24
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by jcrombie View Post
Well, with surprisingly little effort the Aurifeuillian LM calculator is now online! (the system() command being the culprit).

So, presenting with minimalist style this page:

(Near the bottom should be the said calculator)
I may be not knowledgeable enough to understand completely but all I've been getting playing around is L=0 M=0.
science_man_88 is offline   Reply With Quote
Old 2012-03-11, 22:24   #25
jcrombie
 
jcrombie's Avatar
 
"Jonathan"
Jul 2010
In a tangled web...

21410 Posts
Default

Yes, random values will likely produce that result. I really should put some educational type info on there.

In brief, your base will have an L,M factorization at every exponent which is an odd multiple of your base (with square parts removed). It will be a '-1' if the square-free part has a remainder of 1 when dividing by 4 else it will be a '+1'.

eg. 5239-1 is an LM

since,

square-free base = 52 / (22) = 13
exponent is 3 (an odd number) x square-free base = 13
-1 is correct since 13 / 4 = 3 remainder 1

(I'm sure the math types here are having a heart attack looking at my primitive analysis)

If that doesn't work, then there really is a problem.
jcrombie is offline   Reply With Quote
Old 2012-03-11, 23:01   #26
jcrombie
 
jcrombie's Avatar
 
"Jonathan"
Jul 2010
In a tangled web...

2×107 Posts
Default

Oh, I forgot to mention that those rules don't apply to bases that are perfect powers.

eg. base 1000 = 103 is a perfect power.

The solution is of course to just convert your number to a non-perfect power.

100050+1 = (103)50+ 1
= 103x50+1
= 10150+1

Cheers

[Edit: Actually that was a bad example. But if your base was say 100 = 102 then I think you can see there would be a problem.]

Last fiddled with by jcrombie on 2012-03-11 at 23:11 Reason: logic error
jcrombie is offline   Reply With Quote
Old 2012-04-26, 20:04   #27
jcrombie
 
jcrombie's Avatar
 
"Jonathan"
Jul 2010
In a tangled web...

2·107 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?
Thanks for that info. It's been incorporated into an online calculator for primitives.

myfactors.mooo.com

Enjoy!
jcrombie is offline   Reply With Quote
Old 2012-04-27, 03:32   #28
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

882410 Posts
Default

mooo dot com blocked by barracuda:
Quote:
The link you are accessing has been blocked by the Barracuda Web Filter because it contains spyware. The name of the spyware is: Exploit.Host.Mooo
If you believe this is an error or need to access this link please contact your administrator (it@xxxxxxxxxxx).
It may be that my filter need readjusting, but better don't click on that link unless you are sure what are you doing.

Last fiddled with by LaurV on 2012-04-27 at 03:33
LaurV is offline   Reply With Quote
Old 2012-04-27, 03:59   #29
jcrombie
 
jcrombie's Avatar
 
"Jonathan"
Jul 2010
In a tangled web...

2×107 Posts
Default

mooo.com is a domain registered to freedns.afraid.org. Anyone is allowed to add their
subdomain onto it for free. (My guess, some malware was also put there on a different
subdomain).
jcrombie is offline   Reply With Quote
Old 2012-07-11, 03:02   #30
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

23518 Posts
Default

Quote:
Originally Posted by Raman View Post
 11^{22n-11}+1 = (11^{2n-1}+1) (11^{10n-5}-11^{9n-4}+5.11^{8n-4}-11^{7n-3}-11^{6n-3}+11^{5n-2}-11^{4n-2}-11^{3n-1}+5.11^{2n-1}-11^{n}+1) (11^{10n-5}+11^{9n-4}+5.11^{8n-4}+11^{7n-3}-11^{6n-3}-11^{5n-2}-11^{4n-2}+11^{3n-1}+5.11^{2n-1}+11^{n}+1)
 12^{6n-3}+1 = (12^{2n-1}+1) (12^{2n-1}-6.12^{n-1}+1) (12^{2n-1}+6.12^{n-1}+1)
 13^{26n-13}-1 = (13^{2n-1}-1) (13^{12n-6}-13^{11n-5}+7.13^{10n-5}-3.13^{9n-4}+15.13^{8n-4}-5.13^{7n-3}+19.13^{6n-3}-5.13^{5n-2}+15.13^{4n-2}-3.13^{3n-1}+7.13^{2n-1}-13^n+1) (13^{12n-6}+13^{11n-5}+7.13^{10n-5}+3.13^{9n-4}+15.13^{8n-4}+5.13^{7n-3}+19.13^{6n-3}+5.13^{5n-2}+15.13^{4n-2}+3.13^{3n-1}+7.13^{2n-1}+13^n+1)
 14^{28n-14}+1 = (14^{4n-2}+1) (14^{12n-6}-14^{11n-5}+7.14^{10n-5}-2.14^{9n-4}+3.14^{8n-4}+14^{7n-3}-7.14^{6n-3}+14^{5n-2}+3.14^{4n-2}-2.14^{3n-1}+7.14^{2n-1}-14^n+1) (14^{12n-6}+14^{11n-5}+7.14^{10n-5}+2.14^{9n-4}+3.14^{8n-4}-14^{7n-3}-7.14^{6n-3}-14^{5n-2}+3.14^{4n-2}+2.14^{3n-1}+7.14^{2n-1}+14^n+1)
 15^{30n-15}+1 = (15^{2n-1}+1) (15^{4n-2}-15^{2n-1}+1) (15^{8n-4}-15^{6n-3}+15^{4n-2}-15^{2n-1}+1) (15^{8n-4}-15^{7n-3}+8.15^{6n-3}-3.15^{5n-2}+13.15^{4n-2}-3.15^{3n-1}+8.15^{2n-1}-15^n+1) (15^{8n-4}+15^{7n-3}+8.15^{6n-3}+3.15^{5n-2}+13.15^{4n-2}+3.15^{3n-1}+8.15^{2n-1}+15^n+1)

 17^{34n-17}-1 = (17^{2n-1}-1) (17^{16n-8}-17^{15n-7}+9.17^{14n-7}-3.17^{13n-6}+11.17^{12n-6}-17^{11n-5}-5.17^{10n-5}+3.17^{9n-4}-15.17^{8n-4}+3.17^{7n-3}-5.17^{6n-3}-17^{5n-2}+11.17^{4n-2}-3.17^{3n-1}+9.17^{2n-1}-17^n+1) (17^{16n-8}+17^{15n-7}+9.17^{14n-7}+3.17^{13n-6}+11.17^{12n-6}+17^{11n-5}-5.17^{10n-5}-3.17^{9n-4}-15.17^{8n-4}-3.17^{7n-3}-5.17^{6n-3}+17^{5n-2}+11.17^{4n-2}+3.17^{3n-1}+9.17^{2n-1}+17^n+1)
 18^{4n-2}+1 = (18^{2n-1}-6.18^{n-1}+1) (18^{2n-1}+6.18^{n-1}+1)
 19^{38n-19}+1 = (19^{2n-1}+1) (19^{18n-9}-19^{17n-8}+9.19^{16n-8}-3.19^{15n-7}+17.19^{14n-7}-5.19^{13n-6}+27.19^{12n-6}-7.19^{11n-5}+31.19^{10n-5}-7.19^{9n-4}+31.19^{8n-4}-7.19^{7n-3}+27.19^{6n-3}-5.19^{5n-2}+17.19^{4n-2}-3.19^{3n-1}+9.19^{2n-1}-19^n+1) (19^{18n-9}+19^{17n-8}+9.19^{16n-8}+3.19^{15n-7}+17.19^{14n-7}+5.19^{13n-6}+27.19^{12n-6}+7.19^{11n-5}+31.19^{10n-5}+7.19^{9n-4}+31.19^{8n-4}+7.19^{7n-3}+27.19^{6n-3}+5.19^{5n-2}+17.19^{4n-2}+3.19^{3n-1}+9.19^{2n-1}+19^n+1)

<snip> means what
I realize right now that the Aurifeuillian factorizations come out from the polynomial factorization for the values for
For the prime bases b
NNx2N-1, if b = 1 mod 4 (Totally the forms b = k2p, for the primes p = 1 mod 4?)
NNx2N+1, if b = 2, 3 mod 4 (Case elsewhere?)

By the way, what are being the best known fastest algorithms for the polynomial factorization, as such?
Berlekamp Algorithm?
Or which otherwise that works out only inside the finite fields, off actually?

This way, away

Question
For the Cunningham numbers, for the bases b below 12,
why does the base 12 alone have the Aurifeuillian coefficient's power to be 6n-3,
while whereas the rest of the bases have got their respective powers to be precisely 2bn-b ?


What are the other bases that are likely being to have such a property as this,
the left hand side coefficient's power is not being equivalent to the value for 2bn-b at all?

If so, then what is being the dividing factor? Is it always being likely to be an integer value, again?
Is it being the largest square value that divides the base b ?

Is it the case that all the square free bases b have got their left hand side powers to be precisely 2bn-b
to being likely to be the true case? Such as the cases b = 12, 18 where the bases are not being the square free
themselves at all.
Thinking for it, I hope that it is not! For this example, consider the observation for the base value system
for b = 15. It unusually splits out into three parts for the degree 8 coefficient parts. Does that mean that the
base 15 has got the Aurifeuillian factors away into the three parts 15A, 15B, 15C as such?!

Or otherwise not the case at all!?

Last fiddled with by Raman on 2012-07-11 at 04:02
Raman is offline   Reply With Quote
Old 2012-07-11, 05:45   #31
rcv
 
Dec 2011

100011112 Posts
Default

Quote:
Originally Posted by Raman View Post
...
By the way, what are being the best known fastest algorithms for the polynomial factorization, as such ...
Professor R. P. Brent's publications, http://wwwmaths.anu.edu.au/~brent/pub/pub127.html and http://wwwmaths.anu.edu.au/~brent/pub/pub135.html, which are referenced early in this thread, should answer many of your questions. You can just use his magic recursive formulas. To better understand why his magic recursive formulas work, read up on Newton's Sums.

I think the previous comments in this thread also should answer many of your questions. But, here are some examples based on some of your specific questions...

Among the bases in the Cunningham Tables (2, 3, 5, 6, 7, 10, 11, 12), 12 is the only base that is not square free. (12=3\times 2^2). If you exclude the "square-full" part of the base, what is left determines which exponents will have Aurifeuillean Factors. (I.e., 12^n+1 will have Aurifeuillean Factors at the same exponents where 3^n+1 would have Aurifeuillean Factors. So, if 3^{39}+1 has Aurifeuillean Factors, then 12^{39}+1 also has Aurifeuillean Factors.) Similarly, 18=2 \times 3^2, so 18^2+1, 18^6+1, 18^{10}+1 have Aurifeuillean Factors, just as 2^2+1, 2^6+1, and 2^{10}+1 have Aurifeuillean Factors.

If a number has Aurifeuillean Factors, by convention, it has exactly two Aurifeuillean Factors. However, for a number that has algebraic factors as well as Aurifeuillean Factors, some of the algebraic factors may interact with the Aurifeuillean Factors. For example, 2^{30}+1 = L \times M, where L=32513 and M=33025. But 2^{30}+1 is divisible by 2^{10}+1=25\times 41, which are its Aurifeuillean factors. (41|32513, \quad 25|33025.) But, 2^{30}+1 is also divisible by 2^6+1 = 5\times 13, which are its Aurifeuillean factors. (13|32513, \quad 5|33025.) But 2^{30}+1, 2^{10}+1, and 2^6+1 are all divisible by 2^2+1 = 1\times 5, which are its Aurifeuillean factors. [Thanks to jcrombie's Web Site at http://myfactors.mooo.com/ for serving these Aurifeuillean factors up on a silver platter.] By combining the Aurifeuillean factors of the algebraic factors of 2^{30}+1, the complete factorization 2^{30}+1 = 5\times 5\times 13\times 41\times 61\times 1321 is obtained.

In general, a number that has two Aurifeuillean Factors will also have a non-Aurifeuillean component. Base 2 is a special case where the non-Aurifeuillean factor is unity.

Your question about 15^{30n-15}+1 is a case that always combines Aurifeuillean Factors with algebraic factors. 15^{30n-15}+1 is always divisible by 15^{10n-5}+1, 15^{6n-3}+1, and 15^{2n-1}+1. Your computer-generated(?) factorization appears to be providing a combination of Aurifeuillean and algebraic factors.

Last fiddled with by rcv on 2012-07-11 at 06:00
rcv is offline   Reply With Quote
Old 2019-10-04, 16:20   #32
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×887 Posts
Default Aurifeuillian factorizations of Lucas-type numbers...

I have been going over the basics of generalized Lucas and Fibonacci sequences based on the quadratic polynomials

x^2 - a*x - 1 (a = positive integer)

and have gotten to the generalization of the well-known Aurifeuillian factorization for a = 1, and odd n,

\frac{L_{5n}}{L_{n}} \; = \; (5F_{n}^{2} \; + \; 5F_{n} \; + \; 1)(5F_{n}^{2} \; - \; 5F_{n} \; + \; 1)\text{.}

As mentioned, e.g. here, it is based on the algebraic identity

\frac{x^{5} \; \ + \; y^{5}}{x \; + \; y} \; = \;  (x^{2} \; - \; 3xy \; + \; y^{2})^{2} \; + \; 5xy(x \; - \; y)^{2}\text{.}

The hypothesis that n is odd manifests itself with xy being -1 rather than +1.

I am sure the following has been well known for a long time, but it proved easier to derive it from scratch than to dig up a reference. If anyone knows a reference for the generalized version, I'd like to know it.

If the coefficient a is odd, there will be a similar algebraic identity, with the coefficient 5 above replaced by N = a2 + 4, based on the algebraic factorization (x2N + 1)/(x2 + 1) over the quadratic field defined by t2 + N. The situation is simplest when N is prime.

For the case a = 3, N = 13 the appropriate identity for L13n/Ln, n odd, is

\frac{x^{13} \; \ + \; y^{13}}{x \; + \; y} \; = \; P_{1}^{2} \; + \; 13xyP_{2}^2\text{, where}\\P_{1} \; \; = x^{6} \; - \; 7x^{5}y \; + \; 15x^{4}y^{2} \; - \; 19x^{3}y^{3} \; + \; 15x^{2}y^{4} \; - \; 7xy^{5} \; + \; y^{6}\text{, and}\\P_{2} \; = \; x^{5} \; - \; 3x^{4}y \; + \; 5x^{3}y^{2} \; - \; 5x^{2}y^{3} \; + \; 3xy^{4} \; - \; y^{5}\text{.}
Dr Sardonicus is offline   Reply With Quote
Old 2019-10-04, 17:46   #33
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
I have been going over the basics of generalized Lucas and Fibonacci sequences based on the quadratic polynomials

x^2 - a*x - 1 (a = positive integer)

and have gotten to the generalization of the well-known Aurifeuillian factorization for a = 1, and odd n,

\frac{L_{5n}}{L_{n}} \; = \; (5F_{n}^{2} \; + \; 5F_{n} \; + \; 1)(5F_{n}^{2} \; - \; 5F_{n} \; + \; 1)\text{.}

As mentioned, e.g. here, it is based on the algebraic identity

\frac{x^{5} \; \ + \; y^{5}}{x \; + \; y} \; = \;  (x^{2} \; - \; 3xy \; + \; y^{2})^{2} \; + \; 5xy(x \; - \; y)^{2}\text{.}

The hypothesis that n is odd manifests itself with xy being -1 rather than +1.

I am sure the following has been well known for a long time, but it proved easier to derive it from scratch than to dig up a reference. If anyone knows a reference for the generalized version, I'd like to know it.

If the coefficient a is odd, there will be a similar algebraic identity, with the coefficient 5 above replaced by N = a2 + 4, based on the algebraic factorization (x2N + 1)/(x2 + 1) over the quadratic field defined by t2 + N. The situation is simplest when N is prime.

For the case a = 3, N = 13 the appropriate identity for L13n/Ln, n odd, is

\frac{x^{13} \; \ + \; y^{13}}{x \; + \; y} \; = \; P_{1}^{2} \; + \; 13xyP_{2}^2\text{, where}\\P_{1} \; \; = x^{6} \; - \; 7x^{5}y \; + \; 15x^{4}y^{2} \; - \; 19x^{3}y^{3} \; + \; 15x^{2}y^{4} \; - \; 7xy^{5} \; + \; y^{6}\text{, and}\\P_{2} \; = \; x^{5} \; - \; 3x^{4}y \; + \; 5x^{3}y^{2} \; - \; 5x^{2}y^{3} \; + \; 3xy^{4} \; - \; y^{5}\text{.}
I don't have the reference at hand, but I know that the general case is discussed
in Riesel's book. I believe that Brent wrote a paper on an algorithm to derive the coefficients.
R.D. Silverman 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:49.

Mon Oct 19 21:49:59 UTC 2020 up 39 days, 19 hrs, 1 user, load averages: 1.13, 1.52, 1.75

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.