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

Re: ECM/FPGA Implementation Update

Expand Messages
  • 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 1 of 22 , Jul 26, 2005
    • 0 Attachment
      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 2 of 22 , Jul 27, 2005
      • 0 Attachment
        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 3 of 22 , Jul 30, 2005
        • 0 Attachment
          --- 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 4 of 22 , Jul 30, 2005
          • 0 Attachment
            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 5 of 22 , Jul 30, 2005
            • 0 Attachment
              --- 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 6 of 22 , Jul 30, 2005
              • 0 Attachment
                --- 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 7 of 22 , Jul 31, 2005
                • 0 Attachment
                  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 8 of 22 , Jul 31, 2005
                  • 0 Attachment
                    --- 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 9 of 22 , Jul 31, 2005
                    • 0 Attachment
                      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 10 of 22 , Aug 1, 2005
                      • 0 Attachment
                        --- 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 11 of 22 , Aug 1, 2005
                        • 0 Attachment
                          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 12 of 22 , Aug 1, 2005
                          • 0 Attachment
                            --- 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 13 of 22 , Aug 1, 2005
                            • 0 Attachment
                              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 14 of 22 , Sep 16, 2005
                              • 0 Attachment
                                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.