mersenneforum.org > Math SNFS for fibonacci(1345)
 Register FAQ Search Today's Posts Mark Forums Read

 2013-01-08, 21:45 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 11001001011002 Posts 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.
 2013-01-09, 00:26 #2 frmky     Jul 2003 So Cal 8B216 Posts Based on experience with quartics, it has an "apparent" difficulty of around 285 digits. Definitely needs 16e, but doable.
 2013-01-09, 00:36 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 22×32×179 Posts 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)
 2013-01-10, 15:25 #4 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 13·457 Posts 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.
 2013-01-16, 16:56 #5 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 13×457 Posts 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.
 2013-01-16, 17:35 #6 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 644410 Posts 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).
2013-01-16, 19:49   #7
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

13·457 Posts

Quote:
 Originally Posted by fivemack 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?

 2013-01-16, 22:51 #8 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 22×32×179 Posts T should be fibonacci(1345)/(5*fibonacci(269)) which in this case is n.
2014-12-01, 08:55   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·132·19 Posts

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 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]

 2014-12-01, 19:56 #10 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 173516 Posts 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.
 2014-12-01, 22:30 #11 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×132×19 Posts 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.)

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 And now for something completely different 17 2017-06-13 03:49 efeuvete Math 7 2013-05-26 11:24 MattcAnderson Math 7 2013-01-14 23:29 robert44444uk Math 3 2007-05-19 07:15 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