Sorry, an error occurred while loading the content.

## Re: SNFS v SIQS

Expand Messages
• A recent addition to http://groups.yahoo.com/group/primeform/files/GenLuc/luctop.txt benefitted from Satoshi Tomabechi s SNFS. ... was missing 80 digits to
Message 1 of 19 , Jan 3, 2002
A recent addition to

http://groups.yahoo.com/group/primeform/files/GenLuc/luctop.txt

benefitted from Satoshi Tomabechi's SNFS.

> prime digs who Cmin F1 F2 proof
> lucasU(5621,-1,1801) 6750 x25 117 0.1786 0.1666 WL

was missing 80 digits to achieve the Williams-Lenstra threshold
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
[factor base]
RFB 22190 AFB 16985 QCB 28
FF FP PF PP PPF
9577 21888 45226 102100 45845 7873 36993 102402 5512
#free-rel 4246
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
[trial]
#dependencies 65156 trial 1 severe error 0
[factor]
103589852304634507491928934924568241 *
9554526362492897852956064429176725960566683505187322321
[cputime] 6:48:58:94
(sieve 6:22:04:51
LPV 0:02:08:46
construct matrix 0:05:04:09
Lanczos 0:03:21:27
Lanczos All 0:03:21:27
productR 0:00:37:34
productA 0:02:40:31
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.

Ohkini, Satoshi!

David
• ... I m sorry that I m late to reply. I m now so busy that I cannot read too many messages in this list. Our Japanese project is started today. I and Kida
Message 2 of 19 , Jan 7, 2002

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

I'm sorry that I'm late to reply.
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.

Satoshi Tomabechi
Your message has been successfully submitted and would be delivered to recipients shortly.