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 2·7·461 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

22·3·311 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     "name field" Jun 2011 Thailand 282716 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

89·113 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

22·3·311 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

179 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

"Bob Silverman"
Nov 2003
North of Boston

165248 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

"Bob Silverman"
Nov 2003
North of Boston

11101010101002 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

"Bob Silverman"
Nov 2003
North of Boston

1D5416 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     "name field" Jun 2011 Thailand 19·541 Posts Ye all putting salt on the cut...
2012-02-22, 19:42   #11
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 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 12 2021-08-04 21:01 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 03:04.

Fri Feb 3 03:04:50 UTC 2023 up 169 days, 33 mins, 1 user, load averages: 0.74, 0.92, 0.88