mersenneforum.org > YAFU SNFS polynomials via lindep
 Register FAQ Search Today's Posts Mark Forums Read

 2011-08-22, 16:28 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 23·797 Posts SNFS polynomials via lindep Also, it's a Fibonacci number so it's SNFS-able (play around with lattice reduction of {FibN, fib(A)^6, fib(A)^5*fib(B) ... } for A,B near N/6). Code: A=fibonacci(1049) u=fibonacci(174) v=fibonacci(175) ? lindep([A,u^6,u^5*v,u^4*v^2,u^3*v^3,u^2*v^4,u*v^5,v^6]) %14 = [-1, 1, 0, 15, 20, 30, 18, 5]~ so Code: n: 11306054131787655968747547768061150919509803257954523210546639678264631549875906520129375307461813768927343896318137750949420159685553746180237040613218941447819843916894065106795775853 Y1: 1033628323428189498226463595560281832 Y0: -1672445759041379840132227567949787325 skew: 0.76 c6: 5 c5: 18 c4: 30 c3: 20 c2: 15 c0: 1 lpbr: 29 lpba: 29 mfbr: 58 mfba: 58 alambda: 2.6 rlambda: 2.6 alim: 42000000 rlim: 42000000 (sieve with 14e, -a 14M..42M; it'll take about 1500 CPU-hours on 64-bit Linux using Batalov's build of gnfs-lasieve4I14e) Last fiddled with by fivemack on 2011-08-22 at 16:31
2011-08-22, 16:35   #2
bsquared

"Ben"
Feb 2007

23×419 Posts

Quote:
 Originally Posted by fivemack Also, it's a Fibonacci number so it's SNFS-able ...
Ahh, I didn't know what number he was attempting, good catch!

@LaurV: you're a newcomer so it may not be obvious that this number had special form... let this be a lesson that a little research can be a good thing before starting what would otherwise be a years long project.

 2011-08-23, 04:20 #3 LaurV Romulan Interpreter     Jun 2011 Thailand 8,963 Posts Thanks all of you. You made my day. I was really upset about losing that amount of work. Now what's left, is for me to understand what fivemack did there... any links to a good article that explains the math? Should I try second phase with that poly? Or you did that already, too? I see there are no factors reported yet on factordb.  whoops, forget-it! just now I understood what's going on and how stupid I am (about the sieving part). I will give it a try, I don't like to let the things unfinished. 1500 hours... hmmm... Last fiddled with by LaurV on 2011-08-23 at 04:27
2012-02-21, 03:57   #4
Batalov

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

2·4,591 Posts
SNFS polynomials via lindep

Quote:
 Originally Posted by fivemack Also, it's a Fibonacci number so it's SNFS-able (play around with lattice reduction of {FibN, fib(A)^6, fib(A)^5*fib(B) ... } for A,B near N/6). Code: A=fibonacci(1049) u=fibonacci(174) v=fibonacci(175) ? lindep([A,u^6,u^5*v,u^4*v^2,u^3*v^3,u^2*v^4,u*v^5,v^6]) %14 = [-1, 1, 0, 15, 20, 30, 18, 5]~ so...
lindep helps to fill in some even uglier hunches with values!

For example, Fib(1455); 1455 is divisible by 15, so one could guess that after reducing by Fib(1455/3) and Fib(1455/5) one would expect an octic; and furthermore with a=fib(96); b=fib(98) a symmetric octic, reciprocally turned into a quartic... So let's simply call lindep et voila:
Code:
A=24495087715163847304862540972555926557873273177033866366779348623963231442165114660311395897245268799028268424981674090323016224542563692683069015229462064926081
a=fibonacci(96);b=fibonacci(98);
u=a^2+b^2;v=a*b;
lindep([A,u^4,u^3*v,u^2*v^2,u*v^3,v^4])
[61, -61, 197, 46, -632, 479]~
Beauty! A quartic with difficulty 162. (A curious reader will note that u turned out to be 3v+1, but that is of very little surprise - they are fibonacci's)

Running it now...

2012-02-21, 04:06   #5
bsquared

"Ben"
Feb 2007

335210 Posts

Quote:
 Originally Posted by Batalov lindep helps to fill in some even uglier hunches with values! For example, Fib(1455); 1455 is divisible by 15, so one could guess that after reducing by Fib(1455/3) and Fib(1455/5) one would expect an octic; and furthermore with a=fib(96); b=fib(98) a symmetric octic, reciprocally turned into a quartic... So let's simply call lindep et voila: Code: A=24495087715163847304862540972555926557873273177033866366779348623963231442165114660311395897245268799028268424981674090323016224542563692683069015229462064926081 a=fibonacci(96);b=fibonacci(98); u=a^2+b^2;v=a*b; lindep([A,u^4,u^3*v,u^2*v^2,u*v^3,v^4]) [61, -61, 197, 46, -632, 479]~ Beauty! A quartic with difficulty 162. (A curious reader will note that u turned out to be 3v+1, but that is of very little surprise - they are fibonacci's) Running it now...
Very neat! Have you played around with this technique on other fibonacci's?

2012-02-21, 08:12   #6
Random Poster

Dec 2008

101100112 Posts

Quote:
 Originally Posted by Batalov Code: A=24495087715163847304862540972555926557873273177033866366779348623963231442165114660311395897245268799028268424981674090323016224542563692683069015229462064926081 a=fibonacci(96);b=fibonacci(98); u=a^2+b^2;v=a*b; lindep([A,u^4,u^3*v,u^2*v^2,u*v^3,v^4]) [61, -61, 197, 46, -632, 479]~ Beauty! A quartic with difficulty 162. (A curious reader will note that u turned out to be 3v+1, but that is of very little surprise - they are fibonacci's)
Or you could do it The Right Way and use x^4+9x^3+26x^2+24x+1 with x=lucas(97)^2.

2012-02-21, 13:07   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Batalov lindep helps to fill in some even uglier hunches with values! For example, Fib(1455); 1455 is divisible by 15, so one could guess that after reducing by Fib(1455/3) and Fib(1455/5) one would expect an octic; and furthermore with a=fib(96); b=fib(98) a symmetric octic, reciprocally turned into a quartic... So let's simply call lindep et voila: Code: A=24495087715163847304862540972555926557873273177033866366779348623963231442165114660311395897245268799028268424981674090323016224542563692683069015229462064926081 a=fibonacci(96);b=fibonacci(98); u=a^2+b^2;v=a*b; lindep([A,u^4,u^3*v,u^2*v^2,u*v^3,v^4]) [61, -61, 197, 46, -632, 479]~ Beauty! A quartic with difficulty 162. (A curious reader will note that u turned out to be 3v+1, but that is of very little surprise - they are fibonacci's) Running it now...

Yep! F1049 is only C219 with an SNFS sextic; quite doable with even
modest resources. Indeed, one could pick off the first 5 to 10 holes
in the Lucas and Fibonacci tables.

Unfortunately, right now I don't even have "modest" resources. I have
a laptop and 3 PCs.......

2012-02-21, 13:11   #8
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by bsquared Very neat! Have you played around with this technique on other fibonacci's?
Yes, it has been extensively studied and even presented in this venue.

The technique is applicable to (say) quintics, septics etc.

2012-02-21, 13:19   #9
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by R.D. Silverman Yep! F1049 is only C219 with an SNFS sextic; quite doable with even modest resources. Indeed, one could pick off the first 5 to 10 holes in the Lucas and Fibonacci tables. Unfortunately, right now I don't even have "modest" resources. I have a laptop and 3 PCs.......
I just checked..... F1049 was picked off! Kudos to Sean Irvine.

F1097 is the first hole now.
It is perhaps better done by GNFS (C162) [borderline; the size ratio is .70]
By SNFS it is C229; still quite doable.

The first Lucas hole is at 1018; Very doable by SNFS (C213)

 2012-02-22, 06:55 #10 LaurV Romulan Interpreter     Jun 2011 Thailand 8,963 Posts Ye all putting salt on the cut...
2012-02-22, 19:42   #11
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by LaurV Ye all putting salt on the cut...
Do L1018. It is smaller than F1049; only 213 digits. A few weeks on a
single i7.

 Similar Threads Thread Thread Starter Forum Replies Last Post Till Factoring 5 2018-02-12 16:30 chris2be8 FactorDB 1 2012-03-10 16:49 yemsy Aliquot Sequences 1 2011-02-17 10:25 mdettweiler Factoring 15 2010-01-14 21:13 Orgasmic Troll Puzzles 4 2003-09-16 16:23

All times are UTC. The time now is 02:53.

Fri Dec 4 02:53:28 UTC 2020 up 23:04, 0 users, load averages: 2.21, 2.00, 1.67