mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2011-08-22, 16:28   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

23·797 Posts
Default 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
fivemack is offline   Reply With Quote
Old 2011-08-22, 16:35   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

23×419 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
bsquared is offline   Reply With Quote
Old 2011-08-23, 04:20   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

8,963 Posts
Default

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
LaurV is online now   Reply With Quote
Old 2012-02-21, 03:57   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
Default SNFS polynomials via lindep

Quote:
Originally Posted by fivemack View Post
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...
Batalov is offline   Reply With Quote
Old 2012-02-21, 04:06   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

335210 Posts
Default

Quote:
Originally Posted by Batalov View Post
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?
bsquared is offline   Reply With Quote
Old 2012-02-21, 08:12   #6
Random Poster
 
Random Poster's Avatar
 
Dec 2008

101100112 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
Random Poster is offline   Reply With Quote
Old 2012-02-21, 13:07   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Batalov View Post
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 is offline   Reply With Quote
Old 2012-02-21, 13:11   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by bsquared View Post
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 is offline   Reply With Quote
Old 2012-02-21, 13:19   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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)
R.D. Silverman is offline   Reply With Quote
Old 2012-02-22, 06:55   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

8,963 Posts
Default

Ye all putting salt on the cut...
LaurV is online now   Reply With Quote
Old 2012-02-22, 19:42   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by LaurV View Post
Do L1018. It is smaller than F1049; only 213 digits. A few weeks on a
single i7.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
QS polynomials Till Factoring 5 2018-02-12 16:30
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

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

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