Re: SNFS v SIQS
- A recent addition to
benefitted from Satoshi Tomabechi's SNFS.
> prime digs who Cmin F1 F2 proofwas missing 80 digits to achieve the Williams-Lenstra threshold
> lucasU(5621,-1,1801) 6750 x25 117 0.1786 0.1666 WL
F1+F3>1/3. In N-1 there was a C90 with a neat quartic representation:
C90 = primU(5621,-1,45) = x^4+x^3-4*x^2-4*x+1
x = 1+primU(5621,-1,9) = 31541445621788159525778
which Satoshi's beta version factored in under 7 hours
on an 1GHz Athlon:
===== data of factorization by NFS =====
polynomial (x^4+x^3-4*x^2-4*x+1) x=31541445621788159525778
RFB 22190 AFB 16985 QCB 28
FF FP PF PP PPF
9577 21888 45226 102100 45845 7873 36993 102402 5512
large prime upper bound 5118638 3667837
36356 relations by LPV
sieve region |a| < 39424 b < 78350
[reduction of square]
reduced square 13 digit 349 iteration
square root 7 digit
embedding : ln(abs(\prod(a+b\theta)))
initial 1642.89 2408.59 1301.75 1633.35
final 1.37421 2.95243 1.43862 -1.38182
[block Lanczos method]
#trial 1 #pseudo dependencies 29 #real dependencies 29
final matrix 38337*37991 5753K
#nonzero entry 1472548 38.7604/row
#dependencies 65156 trial 1 severe error 0
construct matrix 0:05:04:09
Lanczos All 0:03:21:27
LLL reduction 0:02:23:88
reduced square 0:00:00:08
ideal decomposition 0:00:03:43
Hensel lift 0:00:00:06)
Square All 0:08:32:69
It can be seen that the sieve takes 90% of the time,
so I am itching for Satoshi to upgrade it using the
methods that Kida has implemented for quintics.
The final phases, which contain the smart Montgomery
math, went very quickly.
- David Broadhurst wrote:
> It can be seen that the sieve takes 90% of the time,I'm sorry that I'm late to reply.
> so I am itching for Satoshi to upgrade it using the
> methods that Kida has implemented for quintics.
I'm now so busy that I cannot read too many messages
in this list.
Our Japanese project is started today.
I and Kida decide to develop GNFS.
We need to study several things.
One of them is to improve sieving process.
We shall employ lattice sieve instead of
usual linear sieve.
I hope that it will be an answer to your request.