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

 2012-03-11, 14:23 #23 jcrombie     "Jonathan" Jul 2010 In a tangled web... 21410 Posts 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)
2012-03-11, 14:50   #24
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by jcrombie 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.

 2012-03-11, 22:24 #25 jcrombie     "Jonathan" Jul 2010 In a tangled web... 2·107 Posts 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.
 2012-03-11, 23:01 #26 jcrombie     "Jonathan" Jul 2010 In a tangled web... 2×107 Posts 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
2012-04-26, 20:04   #27
jcrombie

"Jonathan"
Jul 2010
In a tangled web...

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

myfactors.mooo.com

Enjoy!

2012-04-27, 03:32   #28
LaurV
Romulan Interpreter

Jun 2011
Thailand

23×1,103 Posts

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

 2012-04-27, 03:59 #29 jcrombie     "Jonathan" Jul 2010 In a tangled web... 110101102 Posts 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).
2012-07-11, 03:02   #30
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

Quote:
 Originally Posted by Raman $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)$ 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

2012-07-11, 05:45   #31
rcv

Dec 2011

11·13 Posts

Quote:
 Originally Posted by Raman ... 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.

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

 2019-10-04, 16:20 #32 Dr Sardonicus     Feb 2017 Nowhere 354810 Posts 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{.}$
2019-10-04, 17:46   #33
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.

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

Mon Oct 19 21:53:16 UTC 2020 up 39 days, 19:04, 1 user, load averages: 1.00, 1.37, 1.65