mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2013-01-08, 21:45   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11001001011002 Posts
Default SNFS for fibonacci(1345)

Mathew asked if I could find an SNFS polynomial for the remaining cofactor (a C225) of fibonacci(2690). This is, because fib(2x) = fib(x) * luc(x), a factor of fibonacci(1345).

1345 = 5*269, and in fact the cofactor is precisely fibonacci(1345)/(5*fibonacci(269))

Using
Code:
for(a=260,280,for(b=260,280,x=fibonacci(a);y=fibonacci(b);L=lindep([T,x^4,x^3*y,x^2*y^2,x*y^3,y^4]);print([a,b,vecmax(abs(L)),L])))))
to seek a homogeneous quartic with small coefficients, I find

[268, 270, 1, [-1, 1, -1, 1, -1, 1]~]

giving polynomial file

Code:
n: 148501521951378534185281716440203842465380460289149434295752591954403775487759593606058565352849180127851269740820151254973107152548919853813649906088407985097127774422380900511286761321229724764175275295877628042261637251801
c4: 1
c3: 1
c2: 1
c1: 1
c0: 1
Y0: 45624969256769882625644229676772632057353264935332782291
Y1: 119447720249892581203851665820676436622934188700177088360
skew: 1
This is quite a large quartic, so parameter choice is a bit difficult; rational-side sieving, unbalanced large-prime bounds (3 rational-side LP), 15e at least and maybe 16e, probably two CPU-years of sieving.
fivemack is offline   Reply With Quote
Old 2013-01-09, 00:26   #2
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

8B216 Posts
Default

Based on experience with quartics, it has an "apparent" difficulty of around 285 digits. Definitely needs 16e, but doable.
frmky is offline   Reply With Quote
Old 2013-01-09, 00:36   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22×32×179 Posts
Default

If I were doing it myself, I'd use something like

Code:
lpbr: 31
lpba: 29
mfbr: 93
mfba: 58
alambda: 2.6
rlambda: 3.6
alim: 30000000
rlim: 150000000
and sieve -r with 15e from 30M to 150M - yes, it'll be three CPU-years, but I think using 3LP in order not to have to use 16e is a reasonable trade-off.

Code:
% gnfs-lasieve4I15e F1345.snfs -r -f 150000000 -c 1001
total yield: 1895, q=150001039 (0.62532 sec/rel)
fivemack is offline   Reply With Quote
Old 2013-01-10, 15:25   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

13·457 Posts
Default

Does this have to be a quartic? How much larger would higher degrees be?
Is it possible to double the degree and use an octic? Obviously this has its own problems.
henryzz is offline   Reply With Quote
Old 2013-01-16, 16:56   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

13×457 Posts
Default

Are all of these unusable?
[268, 269, 5, [-1, -1, -3, -5, -5, 0, 2, 1]~]
[268, 270, 5, [-1, 1, -4, 5, -5, 5, -4, 1]~]
[269, 268, 5, [1, -1, -2, 0, 5, 5, 3, 1]~]
[269, 270, 5, [1, -1, 2, 0, -5, 5, -3, 1]~]
[270, 268, 5, [-1, 1, -4, 5, -5, 5, -4, 1]~]
[270, 269, 5, [-1, -1, 3, -5, 5, 0, -2, 1]~]

Trying to test sieve [268, 269, 5, [-1, -1, -3, -5, -5, 0, 2, 1]~] I came up with:
Code:
n: 148501521951378534185281716440203842465380460289149434295752591954403775487759593606058565352849180127851269740820151254973107152548919853813649906088407985097127774422380900511286761321229724764175275295877628042261637251801
c6:  1
c5:  2
c4:  0
c3: -5
c2: -5
c1: -3
c0: -1
Y0: 45624969256769882625644229676772632057353264935332782291
Y1: 73822750993122698578207436143903804565580923764844306069
skew: 1
lpbr: 31
lpba: 29
mfbr: 93
mfba: 58
alambda: 2.6
rlambda: 3.6
alim: 30000000
rlim: 150000000
qintsize: 10000
type: snfs
What did I do wrong? That seems to be how you created the poly in http://www.mersenneforum.org/showthread.php?t=16571.
henryzz is offline   Reply With Quote
Old 2013-01-16, 17:35   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

644410 Posts
Default

I don't know exactly what you've done wrong, but that polynomial is pretty clearly nonsense; it's a sextic in F(268) and F(269) so corresponds to a cofactor of something around F(1600).
fivemack is offline   Reply With Quote
Old 2013-01-16, 19:49   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

13·457 Posts
Default

Quote:
Originally Posted by fivemack View Post
I don't know exactly what you've done wrong, but that polynomial is pretty clearly nonsense; it's a sextic in F(268) and F(269) so corresponds to a cofactor of something around F(1600).
Should T be fibonacci(1345) or n?
henryzz is offline   Reply With Quote
Old 2013-01-16, 22:51   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22×32×179 Posts
Default

T should be fibonacci(1345)/(5*fibonacci(269)) which in this case is n.
fivemack is offline   Reply With Quote
Old 2014-12-01, 08:55   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·132·19 Posts
Default

Code:
n=fibonacci(1345)/fibonacci(269)/5;
x=fibonacci(269);
lindep([n,x^4,x^2,1])
%6 = [-1, 5, -5, 1]~

# using lucas(269), we also can get a neat quartic, but the above one is better
x=fibonacci(268)+fibonacci(270);
lindep([n,x^4,x^2,1])
%8 = [-5, 1, 3, 1]~
...and with 30/29 limits and 3LP on the r side, it is now done.
_____________________

Quote:
Originally Posted by henryzz View Post
Are all of these unusable?
...Trying to test sieve [268, 269, 5, [-1, -1, -3, -5, -5, 0, 2, 1]~] I came up with:
Code:
c6:  1
c5:  2
c4:  0
c3: -5
c2: -5
c1: -3
c0: -1
What did I do wrong? That seems to be how you created the poly in http://www.mersenneforum.org/showthread.php?t=16571.
This sextic has a quartic hidden inside of it (and a heavy baggage -- cofactor (x^2 - x - 1) -- dragged along)
Code:
gp > factor(x^6+2*x^5-5*x^3-5*x^2-3*x-1)
%1 =
[                  x^2 - x - 1 1]
[x^4 + 3*x^3 + 4*x^2 + 2*x + 1 1]
Batalov is offline   Reply With Quote
Old 2014-12-01, 19:56   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

173516 Posts
Default

I produced an octic [134, 135, 25, [-1, 1, -6, 17, -18, 25, 18, 17, 6, 1]~] which basically switches the size of the polys.
Octics could be useful for numbers that are a bit larger.
henryzz is offline   Reply With Quote
Old 2014-12-01, 22:30   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×132×19 Posts
Default

Note that (x^2 - x - 1) is treacherous in the context of Fib+Lucas'.
(Where x = rational ratio of consecutive sequence elements, i.e., as well known, "almost ϕ".
For x=ϕ, x^2 - x - 1 = 0, but for "almost ϕ", it is +- 1/some_denominator, so it easily jumps on to the polynomials and makes for the same resultant.)
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
Odd Fibonacci pseudoprimes efeuvete Math 7 2013-05-26 11:24
Fibonacci Formula MattcAnderson Math 7 2013-01-14 23:29
Fibonacci modulo Fibonacci robert44444uk Math 3 2007-05-19 07:15
Fibonacci numbers Citrix Math 27 2006-11-20 17:18

All times are UTC. The time now is 10:11.


Thu Dec 9 10:11:09 UTC 2021 up 139 days, 4:40, 0 users, load averages: 1.38, 1.41, 1.41

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.