SNFS polynomials via lindep

fivemack · 2011-08-22, 16:28

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)

bsquared · 2011-08-22, 16:35

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.

LaurV · 2011-08-23, 04:20

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.

[edit] 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...

Batalov · 2012-02-21, 03:57

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

bsquared · 2012-02-21, 04:06

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?

Random Poster · 2012-02-21, 08:12

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.

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

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

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

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.

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

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)

LaurV · 2012-02-22, 06:55

Ye all putting salt on the cut...

R.D. Silverman · 2012-02-22, 19:42

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.

2011-08-23, 04:20	#3
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2827₁₆ 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. [edit] 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
QS polynomials	Till	Factoring	12	2021-08-04 21:01
SNFS polynomials.	chris2be8	FactorDB	1	2012-03-10 16:49
orthogonal polynomials	yemsy	Aliquot Sequences	1	2011-02-17 10:25
SNFS polynomials for k*b^n+-1	mdettweiler	Factoring	15	2010-01-14 21:13
Polynomials and Probability	Orgasmic Troll	Puzzles	4	2003-09-16 16:23

2012-02-22, 06:55	#10
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 19·541 Posts	Ye all putting salt on the cut...