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

Re: ECM/FPGA Implementation Update

Expand Messages
  • Ron
    Hmmm, this XYYX project sounds very interesting Larry, too bad you can t discuss it - not even it s real name, har, har! Is it related to the infamous XYZ
    Message 1 of 22 , Jul 26, 2005
      Hmmm, this "XYYX" project sounds very interesting Larry, too bad you
      can't discuss it - not even it's real name, har, har! Is it related
      to the infamous "XYZ" company? ;-)

      If you mean 312 *decimal* digits (roughly 2^1036), then I probably
      couldn't fit such a beast even into an ASIC with it's millions of
      gates; but if you're referring to 312 binary digits then that's about
      the same target range I was hoping for (and still haven't given up on
      yet). Fortunately, the Verilog code is essentially the same
      regardless of the data width.

      Thank you for the estimate. I will keep it in mind.

      -- Ron
    • Ron
      Please disregard my previous remarks about your XYYX project. I have since found your XYYXF project page at: http://xyyxf.at.tut.by/default.html#0 and
      Message 2 of 22 , Jul 26, 2005
        Please disregard my previous remarks about your "XYYX" project. I have
        since found your XYYXF project page at:
        http://xyyxf.at.tut.by/default.html#0
        and realize you were serious. This being a math forum I suppose I
        should have known. :-O

        I honestly thought you were probably working on some sort of secret
        project that you couldn't discuss, and just got tired of saying "it's
        classified" so you made up an imaginary project name much like the CIA
        are reputed (according to reliable sources - ie; movies and TV ;-) to
        refer to "the company" when referring to the CIA. No offense was
        intended.

        -- Ron
      • Phil Carmody
        From: Ron ... There s little point in shipping off to external ECM hardware any number with much less than about 50 bits, as such
        Message 3 of 22 , Jul 27, 2005
          From: "Ron" <Yaho6Hb3c@...>
          > Subject: ECM/FPGA Implementation Update
          >
          > Hi folks,
          >
          > I promised an update on my effort to implement ECM in a Field
          > Programmable Gate Array (FPGA) about a month from my last message, so
          > even though there isn't much to report yet I thought I'd post an
          > update because I have yet another question. ;-)
          ...
          > My question is this: What is the smallest number of digits that a
          > fast ECM factoring FPGA would have to handle in order to be useful to
          > others? Would being able to quickly check for B-smooth numbers up to
          > 2^32 be useful for example? If not, what size data would my factoring
          > FPGA have to be able to handle in order to be useful: 2^63, 2^128,
          > 2^256, 2^512, or what? Any thoughts?

          There's little point in shipping off to external ECM hardware any number
          with much less than about 50 bits, as such numbers can be whacked by Rho,
          P-1, SQUFOF, and QS on a PC quite easily. (So much so that I'd bet many
          people just use Pari/GP or Mathematica to use the whole gamut of techniques
          however it sees fit.)

          However, I'd guess that there's not a huge amount of time spent factoring
          less than ~200 bit numbers, simply as everything smaller doesn't take
          long, and things that are larger typically take a lot longer. So in order
          to help save the most time, your target should be where the most time is
          spent.

          I have a whole bunch of things from 80-250 digits that I'd love factored.
          (My ECM server is at 83.143.57.194 port 8192). If anything it's the smaller
          ones I'm more interested in, as they're the ones I believe should be mostly
          crackable. So even 256 bits is somewhat interesting to me. 320 bits is
          definitely interesting, and 400 bits undoubtedly so. On the assumption that
          the 'bang per buck' is vastly better than a general purpose PC, which it
          should be by quite a long way.

          Phil

          () ASCII ribbon campaign () Hopeless ribbon campaign
          /\ against HTML mail /\ against gratuitous bloodshed

          [stolen with permission from Daniel B. Cristofani]

          __________________________________________________
          Do You Yahoo!?
          Tired of spam? Yahoo! Mail has the best spam protection around
          http://mail.yahoo.com
        • Ron
          ... Ok thanks Phil. That and Larry s earlier comment give me a target range. Ideally I would like to be able to factor 640 bit numbers (Ha!), but I realize
          Message 4 of 22 , Jul 30, 2005
            --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@y...>
            wrote:
            > ... So even 256 bits is somewhat interesting to me.
            > 320 bits is definitely interesting, and 400 bits undoubtedly so.

            Ok thanks Phil. That and Larry's earlier comment give me a target
            range. Ideally I would like to be able to factor 640 bit numbers (Ha!),
            but I realize that's probably out of the question on anything less than
            an ASIC so I'd be very happy with 320 bits. So far it looks unlikely,
            but I haven't yet gotten far enough to vary the data bus width and see
            how that effects the gate count, so all is not lost - yet. :^)

            By the way, what's the story on your ECM server? Do you have an
            explanatory web page somewhere - ie; what is it's purpose?

            Thanks,

            -- Ron
          • Paul Leyland
            ... Are there really any as small as 80 digits? Wow. Each one takes only an hour or few with a modern QS implementation. Perhaps a couple of us should get
            Message 5 of 22 , Jul 30, 2005
              On Wed, 2005-07-27 at 14:05, Phil Carmody wrote:
              > From: "Ron" <Yaho6Hb3c@...>

              > > My question is this: What is the smallest number of digits that a
              > > fast ECM factoring FPGA would have to handle in order to be useful to
              > > others? Would being able to quickly check for B-smooth numbers up to
              > > 2^32 be useful for example? If not, what size data would my factoring
              > > FPGA have to be able to handle in order to be useful: 2^63, 2^128,
              > > 2^256, 2^512, or what? Any thoughts?

              ...

              > However, I'd guess that there's not a huge amount of time spent factoring
              > less than ~200 bit numbers, simply as everything smaller doesn't take
              > long, and things that are larger typically take a lot longer. So in order
              > to help save the most time, your target should be where the most time is
              > spent.
              >
              > I have a whole bunch of things from 80-250 digits that I'd love factored.

              Are there really any as small as 80 digits? Wow. Each one takes only
              an hour or few with a modern QS implementation. Perhaps a couple of us
              should get together and clear them out to 100 digits or so.

              > (My ECM server is at 83.143.57.194 port 8192). If anything it's the smaller
              > ones I'm more interested in, as they're the ones I believe should be mostly
              > crackable. So even 256 bits is somewhat interesting to me. 320 bits is
              > definitely interesting, and 400 bits undoubtedly so. On the assumption that
              > the 'bang per buck' is vastly better than a general purpose PC, which it
              > should be by quite a long way.

              These days I very rarely have numbers under 100 digits to factor and the
              ones that do crop up occasionally are usually runts from finding, say, a
              40-digit factor by ECM and the remaining runt is unlikely to have
              factors below 35 or 40 digits. These cases are almost always much
              easier to finish with QS than with more ECM work.

              Personally I'd say 384 bits (116 digits) is the bare minimum for general
              use and 512 bits (155 digits) is *much* more use.

              Paul
            • elevensmooth
              ... to ... I ve been trying to imagine how a fast ECM factoring FPGA would be used by OddPerfect.org. I d want to keep special hardware busy doing something
              Message 6 of 22 , Jul 30, 2005
                --- In primenumbers@yahoogroups.com, Paul Leyland <pcl@w...> wrote:

                > From: "Ron" <Yaho6Hb3c@s...>
                >
                > My question is this: What is the smallest number of digits that a
                > fast ECM factoring FPGA would have to handle in order to be useful
                to
                > others?

                > Paul Leyland <pcl@w...>
                >
                > Personally I'd say 384 bits (116 digits) is the bare minimum for
                > general use and 512 bits (155 digits) is *much* more use.

                I've been trying to imagine how a fast ECM factoring FPGA would be
                used by OddPerfect.org. I'd want to keep special hardware busy doing
                something of at least marginal usefulness all the time. I don't think
                I could generate enough 116 digit composites to keep the hardware
                busy. Today these numbers get factored by volunteers almost as fast as
                I can post them on OddPerfect.org's composites page.

                The next range - up to 155 digits - is much more interesting.
                Presently we completely factor any composite under 125 digits because
                it's easy and there is a chance the factors might be useful someday.
                An FPGA would probably change that threshold to 155 digits.

                William
                Chief Poohbah, OddPerfect.org
              • Phil Carmody
                ... But how did they get to that stage? aaaaAAAaaaah! Phil () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail /
                Message 7 of 22 , Jul 30, 2005
                  --- Paul Leyland <pcl@...> wrote:
                  > Personally I'd say 384 bits (116 digits) is the bare minimum for general
                  > use

                  But how did they get to that stage?

                  aaaaAAAaaaah!

                  Phil

                  () ASCII ribbon campaign () Hopeless ribbon campaign
                  /\ against HTML mail /\ against gratuitous bloodshed

                  [stolen with permission from Daniel B. Cristofani]

                  __________________________________________________
                  Do You Yahoo!?
                  Tired of spam? Yahoo! Mail has the best spam protection around
                  http://mail.yahoo.com
                • Paul Leyland
                  ... Fair enough, but how often is an entirely new class of numbers started, and how many are in such a class. Extending the GCW tables six years ago added 20
                  Message 8 of 22 , Jul 31, 2005
                    On Sat, 2005-07-30 at 23:35, Phil Carmody wrote:
                    > --- Paul Leyland <pcl@...> wrote:
                    > > Personally I'd say 384 bits (116 digits) is the bare minimum for general
                    > > use
                    >
                    > But how did they get to that stage?

                    Fair enough, but how often is an entirely new class of numbers started,
                    and how many are in such a class.

                    Extending the GCW tables six years ago added 20 or 30K new numbers, the
                    vast majority of which began at well over 100 digits. The smallest in
                    the table was 101*3^101-1 which has 51 digits. The 3+ and 3- tables
                    exceeded 100 digits at index 204 and the other tables at correspondingly
                    smaller values (the 9 tables at 103, so only four values made the cut
                    and the 10, 11 and 12 tables had none at all).

                    All in all, only a few hundred, or around 1%, had under 100 digits.
                    Some of those were factored by TD or were prime to start with.


                    Paul
                  • Ron
                    ... Ok, thanks Paul. That helps give me a target to shoot for. -- Ron
                    Message 9 of 22 , Jul 31, 2005
                      --- In primenumbers@yahoogroups.com, Paul Leyland <pcl@w...> wrote:
                      > On Wed, 2005-07-27 at 14:05, Phil Carmody wrote:
                      > ... Personally I'd say 384 bits (116 digits) is the bare minimum
                      > for general use and 512 bits (155 digits) is *much* more use.


                      Ok, thanks Paul. That helps give me a target to shoot for.

                      -- Ron
                    • Ron
                      Thanks William. I ve bookmarked your web site for further perusal. Perhaps when I get my design completed I can hook the development board up to the Internet
                      Message 10 of 22 , Jul 31, 2005
                        Thanks William. I've bookmarked your web site for further perusal.
                        Perhaps when I get my design completed I can hook the development
                        board up to the Internet so that anyone can use it remotely. :-) I'd
                        have to have a simple textual command line type interpreter for it,
                        but Ethernet IP cores are (I believe) free these days and since I was
                        planning on using an Ethernet interface anyway, it would be a simple
                        additional step to hook it up to my LinkSys router and turn it into an
                        ECM web server - Ha! Actually that sounds very plausible and I may
                        just try it. :-)

                        -- Ron
                      • elevensmooth
                        ... OOOhhh! That s interesting. I d been thinking that I d need to purchase a system and run it myself. The issues I was mulling were a cost outlay and the
                        Message 11 of 22 , Aug 1, 2005
                          --- In primenumbers@yahoogroups.com, "Ron" <Yaho6Hb3c@s...> wrote:

                          > Perhaps when I get my design completed I can hook the development
                          > board up to the Internet so that anyone can use it remotely. :-)

                          OOOhhh! That's interesting. I'd been thinking that I'd need to
                          purchase a system and run it myself. The issues I was mulling were a
                          cost outlay and the difficulty of keeping the FPGA busy enough to
                          justify the expenditure. But if my only cost is the coordination
                          effort, it becomes interesting even if I only have a small amount of
                          work. And if it turns out I have a large amount of work, then the
                          purchase option would still be available.

                          William
                          Poohbah, OddPerfect.org
                        • Paul Leyland
                          ... I ve been doing some investigation on the net because I m quite keen on such number crunchers but have been put off by the expense. Like dope pedlars, the
                          Message 12 of 22 , Aug 1, 2005
                            On Mon, 2005-08-01 at 20:44, elevensmooth wrote:
                            > --- In primenumbers@yahoogroups.com, "Ron" <Yaho6Hb3c@s...> wrote:
                            >
                            > > Perhaps when I get my design completed I can hook the development
                            > > board up to the Internet so that anyone can use it remotely. :-)
                            >
                            > OOOhhh! That's interesting. I'd been thinking that I'd need to
                            > purchase a system and run it myself. The issues I was mulling were a
                            > cost outlay and the difficulty of keeping the FPGA busy enough to
                            > justify the expenditure. But if my only cost is the coordination
                            > effort, it becomes interesting even if I only have a small amount of
                            > work. And if it turns out I have a large amount of work, then the
                            > purchase option would still be available.

                            I've been doing some investigation on the net because I'm quite keen on
                            such number crunchers but have been put off by the expense.

                            Like dope pedlars, the hardware manufacturers give out (almost) free
                            samples to get their customers hooked but charge real money for a long
                            term relationship. In particular, the software costs serious bucks even
                            though quite a lot of development hardware is available for a couple
                            hundred or less.

                            If there is a way of amortizing the software costs over a number of
                            fielded systems, I'd be *much* more interested in joining in and
                            contributing to others' efforts. That said, my extremely limited
                            hardware design experience dates from the early 80s when it was very
                            much 7400 TTL, PROMS, AMD 2900 series bit slices and the earliest PLA
                            implementations. I've a steep learning curve to climb.


                            Paul
                          • Ron
                            ... Yep, and I finally shelled out $500 for Lattice s full ispLever development software simply so that I could synthesise (ie; implement designs for) the
                            Message 13 of 22 , Aug 1, 2005
                              --- In primenumbers@yahoogroups.com, Paul Leyland <pcl@w...> wrote:
                              > On Mon, 2005-08-01 at 20:44, elevensmooth wrote:
                              > Like dope pedlars, the hardware manufacturers give out (almost) free
                              > samples to get their customers hooked but charge real money for a long
                              > term relationship. In particular, the software costs serious
                              > bucks even though quite a lot of development hardware is
                              > available for a couple hundred or less.

                              Yep, and I finally shelled out $500 for Lattice's full ispLever
                              development software simply so that I could synthesise (ie; implement
                              designs for) the high-end expensive Lattice FPGAs. The ispLever tools
                              (both the free and pay versions) can *only* be used to synthesize
                              designs for Lattice FPGAs, so it seems bizarre to me that Lattice
                              should be charging for the software. Seems like they should be giving
                              it away for free and encouraging as many people as possible to use
                              it!? Even so, the Lattice software tools are only about half the cost
                              of similar tools from Altera and Xilinx.


                              > If there is a way of amortizing the software costs over a number of
                              > fielded systems, I'd be *much* more interested in joining in and
                              > contributing to others' efforts.

                              Not sure what you mean by this, but there is an option for a
                              "floating" license. It's mostly used within companies but I see no
                              reason a group of people located anywhere couldn't do the same thing
                              as long as everyone has Internet access. The way it works is that only
                              one person can have the license "checked-out" at any given time, and
                              the Lattice license server verifies this as the key is checked in and
                              out by different users.


                              > That said, my extremely limited
                              > hardware design experience dates from the early 80s when it was very
                              > much 7400 TTL, PROMS, AMD 2900 series bit slices and the earliest PLA
                              > implementations. I've a steep learning curve to climb.

                              Don't worry about it Paul. I designed my very first VLSI
                              implementation of a Linear Iterative Array Multiplier/Adder (the one I
                              mentioned earlier that's described in Knuth) in 1983 by writing
                              a Pascal program to draw a plot of the different layers of the VLSI
                              traces I wanted in different colors. You would make a transistor by
                              crossing a plot line representing silicon over a different colored
                              plot line representing (I think) silicon dioxide. It took me several
                              evenings and weekends (it was a one day a week class lasting six weeks
                              that I took at my place of employment) to complete the literally
                              graphical design using Pascal. Whenever I start complaining about
                              Verilog I think back to those days. ;-) I never pursued VLSI design
                              after that, but some 26 years later I was able to produce functionally
                              the same circuit in Verilog in a single afternoon! Some higher level
                              languages (SystemC for one) are on the horizon, but so far the
                              software vendors charge an arm and leg for their software. There are
                              Open Source efforts at software design tools - and indeed I use the
                              totally free Icarus simulator to debug my own design - but the
                              "higher-level" design tools like Open SystemC are mostly in the "Beta"
                              or pre-release stages.

                              Anyhow I think hardware design in Verilog is kind of fun, albeit very
                              tedious. Now that I only have a couple more modules to debug it's
                              starting to get more exciting for me. I even ordered a LFEC20E-L-EV
                              LatticeEC20 Standard Evaluation Board for $175 from Lattice - less
                              than half the cost of the software I purchased from them! As you said,
                              software costs more than hardware in many cases. The LFEC20E is one of
                              their larger FPGA's but is still very affordable. I hope that it will
                              be large enough to actually implement a useful design with.

                              Regards,

                              Ron
                            • Ron
                              Actually I was just thinking more in terms of a simple ASCII text command line type interface. Ethernet interface IP designs are (I believe) freely
                              Message 14 of 22 , Aug 1, 2005
                                Actually I was just thinking more in terms of a simple ASCII text
                                command line type interface. Ethernet interface "IP" designs are (I
                                believe) freely available, so the only work I would have to do is
                                implement a simple ASCII command line interpreter that accepts an
                                input (the number to be factored) and then spits a factor over the
                                same port just as if it were talking over a TTY port. All it would
                                take is a simple script of some sort (either Javascript or TCL would
                                do) to connect an ethernet virtual socket to a virtual ethernet socket
                                on the FPGA. Hopefully all the ethernet level protocol is part of the
                                free ethernet interface design so that the FPGA would only have to
                                worry about reading and writing data. That's the nice thing about
                                FPGAs or hardware design in general - it can do everything truly in
                                parallel without time slicing like computer operating systems do. Not
                                sure what I'd do about collisions if more than one user were trying to
                                access the device, but I could probably have it put out a busy message
                                of some sort when it's busy calculating. It would be nice to at least
                                implement Telnet, but I'm sure that would be too much of a burden for
                                an FPGA.

                                Regards,

                                Ron
                              • Ron
                                Hi Folks, Consider this just a quick note to announce that tonight for the first time ever I HAVE SUCCESSFULLY TESTED MY VERILOG ECM DESIGN!!! It will be
                                Message 15 of 22 , Sep 16, 2005
                                  Hi Folks,

                                  Consider this just a quick note to announce that tonight for the
                                  first time ever I HAVE SUCCESSFULLY TESTED MY VERILOG ECM DESIGN!!!

                                  It will be awhile before I have any hard statistics on how wide the
                                  data bus can be versus type of FPGA because there are an enormous
                                  number of choices of FPGAs, and quite a bit of "clean-up" work and
                                  testing remaining to be done, but initially at least the stats
                                  probably won't be very impressive. Most likely the maximum size
                                  composite it will be able to factor will be between 2^64 and 2^128 as
                                  a guess.

                                  Anyhow, for the first time in many years I feel like opening a bottle
                                  of some very old Cognac. :-)

                                  -- Ron
                                Your message has been successfully submitted and would be delivered to recipients shortly.