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

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

22·3·311 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 online now   Reply With Quote
Old 2011-08-23, 04:20   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

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

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

22·3·311 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 online now   Reply With Quote
Old 2012-02-21, 08:12   #6
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 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
 
"Bob Silverman"
Nov 2003
North of Boston

165248 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
 
"Bob Silverman"
Nov 2003
North of Boston

11101010101002 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
 
"Bob Silverman"
Nov 2003
North of Boston

1D5416 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
 
"name field"
Jun 2011
Thailand

19·541 Posts
Default

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

22·1,877 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 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

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

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔