mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2010-01-06, 14:44   #12
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

7×353 Posts
Default

Quote:
Originally Posted by fivemack View Post
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)
Andi47 is offline   Reply With Quote
Old 2010-01-06, 14:45   #13
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

24×5×79 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2010-01-06, 14:47   #14
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

7×353 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
Andi47 is offline   Reply With Quote
Old 2010-01-06, 18:47   #15
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 View Post
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 View Post
% 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.

Please, answer to questions within the post #8 as well.

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
Raman is offline   Reply With Quote
Old 2010-01-06, 19:10   #16
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26018 Posts
Default

Quote:
Originally Posted by Raman View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2010-01-06, 19:27   #17
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

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?
Raman is offline   Reply With Quote
Old 2010-01-06, 20:39   #18
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18B016 Posts
Default

(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
fivemack is offline   Reply With Quote
Old 2010-03-27, 02:49   #19
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216438 Posts
Default an excercise in triviality

\small<br />
(2^{4k-2}+1) = (2^{2k-1}-2^{k}+1) (2^{2k-1}+2^{k}+1)\\<br />
 <br />
(3^{6k-3}+1) = (3^{2k-1}+1) (3^{2k-1}-3^{k}+1) (3^{2k-1}+3^{k}+1)\\<br />
 <br />
(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)\\<br />
 <br />
(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)\\<br />
 <br />
(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
Batalov is offline   Reply With Quote
Old 2010-03-27, 06:33   #20
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,041 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2010-04-10, 06:34   #21
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

912310 Posts
Default

... 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
Batalov is offline   Reply With Quote
Old 2012-03-04, 19:53   #22
jcrombie
 
jcrombie's Avatar
 
"Jonathan"
Jul 2010
In a tangled web...

2·107 Posts
Default 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!
jcrombie 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:31.

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

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.