Loading ...
Sorry, an error occurred while loading the content.

Re: SNFS v SIQS

Expand Messages
  • djbroadhurst
    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
    • 0 Attachment
      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
    • Satoshi TOMABECHI
      ... 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
      • 0 Attachment
        David Broadhurst wrote:

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