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

2010-01-06, 14:44   #12
Andi47

Oct 2004
Austria

7×353 Posts

Quote:
 Originally Posted by fivemack 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.
So the polynomial for this one would be

Code:
c6: 1
c5: 0
c4: 15
c3: 20
c2: 30
c1: 18
c0: 5
Y0: ?
Y1: ?
?

How do I find the rational poly?

(P.S.: No, I don't plan to factor this fibonacci number)

 2010-01-06, 14:45 #13 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 24×5×79 Posts Y0=u and Y1=v as defined in the code above, I think. Perhaps you have to swap them round and fiddle with the signs.
2010-01-06, 14:47   #14
Andi47

Oct 2004
Austria

7×353 Posts

Quote:
 Originally Posted by fivemack Y0=u and Y1=v as defined in the code above, I think. Perhaps you have to swap them round and fiddle with the signs.
thanks

2010-01-06, 18:47   #15
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

Quote:
 Originally Posted by R.D. Silverman 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.
OK, that I will explain in detail. I have understood well about the SNFS polynomial selection for those homogeneous Cunningham numbers.

For example, take up with $4^{337}-3^{337}$. For a fifth degree polynomial for this number only:
we multiply by 12: in order to get $3.4^{338}-4.3^{338}$
Dividing by $3^{338}$ to get $3.\frac{4^{338}}{3^{338}}-4$
Multiplying with $\frac{16}{9}$, $27.\frac{4^{340}}{3^{340}}-64$
Now that I can take up with $m = \frac{4^{68}}{3^{68}}$ in order to get the algebraic polynomial as $27x^5-64$ and then the rational polynomial as $3^{68}x-4^{68}$
Otherwise, it can be also taken up as well as:
$16x^5-9$ with $3^{67}x-4^{67}$
too
This is for the Homogeneous Cunningham numbers part only.
------------------------------------------------------------------------
For Lucas Numbers & Fibonacci Numbers,
$L_n = \phi^n - \frac{1}{\phi^n}$
$F_n = \frac{1}{\sqrt 5} L_n$

$L_n$ becomes $\phi^{2n}-1$. Since $\phi$ itself is only $\frac{1+\sqrt{5}}{2}$, which contains the surd $\sqrt 5$, which cannot be written as a polynomial with integral coefficients at all purely, for $L_n$ as a whole, such as $\phi^2-\phi-1=0$. Thus, it is not close to any power of integer at all. Thanks, that your post gave me up with the idea.

Quote:
 Originally Posted by fivemack 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
How do you get up with this polynomial? Ok, that I will try out myself. It seems that it should be written up as close to power of one or two smaller Fibonacci/Lucas number itself.

I am not going to factor this Fibonacci number right now anyway, however that I should learn about it up actually, properly. Fibonacci/Lucas numbers, Homogeneous Cunningham numbers, even Aliquot sequences have plenty of small numbers, with small factors that pop up so frequently that it is too difficult to manage up with my larger resources itself. A waste of computing power. Most of the time, I stay away from my resources only. Automation of each job takes up a lot of time to set up. Cunningham Numbers have the higher priority among me, harder numbers, larger factors, ECM being eliminated away, only a handful of numbers.

Why two variables? SNFS polynomials, both rational side as well as algebraic side allow only one variable? I realized that dividing throughout by $v^6$ only, we can substitute up with $m = \frac{u}{v}$, such that the rational polynomial becomes $vx-u$. I realized about that before your subsequent post itself.

I will look up at Perrin number at Wikipedia, try out writing up larger Lucas/Fibonacci number as closer to power of smaller Lucas/Fibonacci numbers respectively. Then, that all becomes clear. How to write up $\phi^n$ in terms of $L_n$ and then $L_{n+1}$ only, etc.

Quote:
 Originally Posted by fivemack % 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]~
What is gp software actually? Is it an inbuilt Linux command, or that it is a program? Where can it be downloaded up from? How to install it up or is it available online itself.

Thanks to you.

By the way, @ fivemack: How much is the linear algebra for M941 completed up till now? What is the status so far? What is the expected completion date, if any predictions only...

Last fiddled with by Raman on 2010-01-06 at 19:29

2010-01-06, 19:10   #16
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

26018 Posts

Quote:
 Originally Posted by Raman What is gp software actually? Is it an inbuilt Linux command, or that it is a program? Where can it be downloaded up from? How to install it up or is it available online itself.
That is PARI-GP, see here: http://pari.math.u-bordeaux.fr/, it's free.

 2010-01-06, 19:27 #17 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts I have understood on how to derive the Aurifeuillian factorizations for any base, by just simply glancing up through the Cunningham book only... $x^2+1 = (x+1)^2 - 2x$ Substituting up with $x = 2^{2k-1}$, the right hand side is a difference of two squares: we can make use of the identity $(a^2-b^2) = (a+b)(a-b)$ $x^3+1 = (x+1)^3 - 3x(x+1)$ $x^3+1 = (x+1)[(x+1)^2 - 3x]$ In this case, besides $x = 3^{2k-1}$, this works out for $x=12^{2k-1}$ as well. Since $12^{2k-1} = 4^{2k-1}.3^{2k-1}$, since 4 is a perfect square, thus $3x$ remains as a perfect square even if $x = 12^{2k-1}$ only. Thus, I noticed up that the interval between Aurifeuillian factorizations is retained up as $2a$ only, for any base $b = k^2.a$ For example, in that above example, the interval between Aurifeuillian factorizations of 3 is 6, for 12 it is 6 as well, but for all other bases N other than 12, it is only 2N. Similar to what you said out for Aurifeuillian factorizations for minus side: if the base p = 1 (mod 4), other bases of the form $k^2.p$ as well. Here, is it necessary that value of p is prime, or any value of p with no factor of any perfect squares at all? I tried out to derive up with the Aurifeuillian factorization of base 5 as well, only: $x^5-1 = (x-1)^5 + 5x^4 - 10x^3 + 10x^2 - 5x$ $x^5-1 = (x-1)^5 - 5x (1 - 2x + 2x^2 - x^3)$ Substituting up with $x = 5^{2k-1}$ within that above equation, I get up that $5^{10k-5}-1 = (5^{2k-1}-1)^5 - 5^{2k} (1 - 2.5^{2k-1} + 2.5^{4k-2} - 5^{6k-3})$ $5^{10k-5}-1 = (5^{2k-1}-1) [(5^{2k-1}-1)^4 - 5^2k (-1 + 5^{2k-1} - 5^{4k-2})]$ Here, that the expression $-1 + 5^{2k-1} - 5^{4k-2}$ is of the form $-1 + x - x^2$ only, with $x = 5^{2k-1}$ which is not a perfect square at all. The other terms within the box brackets are perfect squares only, hence the terms within the box brackets cannot be written as difference of two perfect squares at all. How to write it up in that way, then factorize up with $5^{10k-5}-1$ only, accordingly, thus? Note that, for the term $-1 + x - x^2$, in order to be a perfect square, that $x$ should be replaced up with $2x$, even then the entire expression within the box brackets becomes the sum of two squares, but not the difference of two squares at all. Where did I go wrong?
 2010-01-06, 20:39 #18 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 18B016 Posts (5^5*x^10-1) is divisible by (5*x^2-1), naturally The ratio is 625*x^8 + 125*x^6 + 25*x^4 + 5*x^2 + 1 which it turns out is $(25*x^4+15*x^2+1)^2-(25*x^3+5*x)^2$ but I did this backwards - I got pari to factor 5^5*x^10-1 into irreducibles, and noticed that the two quartic factors had a nice plus-and-minus form. Last fiddled with by fivemack on 2010-01-06 at 20:40
 2010-03-27, 02:49 #19 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 216438 Posts an excercise in triviality $\small (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)\\ (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)\\ (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) (..11M..)$ There are fairly many 2L and 2M, 3L and 3M prime numbers. They can only be prime for prime 2k-1, because if 2k-1=pq (with odd p), then they have algebraic factorizations. The situation is different for 5L/M, 7L/M, 11L/M. They also have algebraic factorizations when 2k-1=pq but unlike 2L/M, 3L/M, this leads to a Fermat-like restriction 2k-1=bN ("their exponent already has a factor of b so they can only stack them up", one can say simplistically). Indeed, 11,11L is prime, and (for example) 5,25L. Very few. When they are composite, their factors also follow a Fermat-esque form (like 2*k*11s+1 for 11L/Ms). And just like Fermat primes, primes of each of these sets can be argued to be finite. Similar for 12L/M and 6L/M (with b=3). Example of a larger prime: 12,81M. Did I get this right? What is the simplest explanation for the Mersenne-esque to Fermat-esque restriction transition? (I guess, the absence of algebraic factorization for the exponents for the factor of b. Did I actually overlook some other forbidden algebraic factorizations?) What could be the largest known prime Aurifeuillian factor (excluding 2 and 3LM)? And I guess there can be no other than 2 and 3LM of the first kind (where the search space is in primes)? << (2p+1)/3 search space is of the first kind, too. This line of thinking probably segues into Lucas Aurifeuillian primitive parts, for which there's a special category at UTM. >> Last fiddled with by Batalov on 2010-03-27 at 03:18 Reason: hopelessly cleaning up the language; but some silliness will stay, no doubt
 2010-03-27, 06:33 #20 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×3,041 Posts Silly me! Actually, 3,27L/M numbers are prime. Because 3,(3n)L/M don't have an algebraic factorization, they may be prime for n prime or a power of 3.
 2010-04-10, 06:34 #21 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 912310 Posts ... I found all the answers for the 3LM primes (after seeing the similarly "converging" sequences A007670+A007671 to a super-sequence A057429 for the 2LM primes). Thank you for not bashing my skull in and letting me find the answers in a leisurely fashion: the A066408 sequence with a great reference set; Oakes: http://tech.groups.yahoo.com/group/p...s/message/4607 and Posting to the Number Theory list; 3534827-3267414+1 (in disguise) 21203793-2601897+1
 2012-03-04, 19:53 #22 jcrombie     "Jonathan" Jul 2010 In a tangled web... 2·107 Posts Utility program Here is a little program that should show the L & M values for a^n +/- 1. http://myfactors.mooo.com/source/cyclo.cpp Enjoy!

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

Mon Oct 19 21:31:42 UTC 2020 up 39 days, 18:42, 1 user, load averages: 1.85, 2.09, 2.04