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

Re: ECM/FPGA Implementation Update

Expand Messages
  • Paul Underwood
    ... Does this help decrypting it: http://webpages.charter.net/rsdotson/button_game.js ? Paul
    Message 1 of 22 , Jul 26, 2005
      --- In primenumbers@yahoogroups.com, "jbrennen" <jb@b...> wrote:
      > --- In primenumbers@yahoogroups.com, "Ron" <Yaho6Hb3c@s...> wrote:
      >
      > > P.S.
      > > I've put up a little "Button Puzzle" on my website that is based upon
      > > prime numbers. It's at: http://xrl.us/Buttons
      > >
      > > I don't expect anyone here to solve it, but I thought it might be
      > > interesting to see how long it takes someone on the forum to
      > > recognize the puzzle for what it is and to be able to answer the
      > > question of why I would pay $1,000 for the puzzle's solution. Good
      > > luck. ;-)
      >
      > I'll work on your puzzle if you change the prize to $19,000.
      > You'll still get to keep $1,000. :)
      >
      > How about if I turn off all of the lights but one? Is that worth
      > anything?

      Does this help decrypting it:

      http://webpages.charter.net/rsdotson/button_game.js ?

      Paul
    • Paul Underwood
      ... upon ... Okay, if you feed the contents of the variable enkripsi into http://scriptasylum.com/tutorials/encdec/theft.html Ron s secreted code will be
      Message 2 of 22 , Jul 26, 2005
        --- In primenumbers@yahoogroups.com, "Paul Underwood"
        <paulunderwood@m...> wrote:
        > --- In primenumbers@yahoogroups.com, "jbrennen" <jb@b...> wrote:
        > > --- In primenumbers@yahoogroups.com, "Ron" <Yaho6Hb3c@s...> wrote:
        > >
        > > > P.S.
        > > > I've put up a little "Button Puzzle" on my website that is based
        upon
        > > > prime numbers. It's at: http://xrl.us/Buttons
        > > >
        > > > I don't expect anyone here to solve it, but I thought it might be
        > > > interesting to see how long it takes someone on the forum to
        > > > recognize the puzzle for what it is and to be able to answer the
        > > > question of why I would pay $1,000 for the puzzle's solution. Good
        > > > luck. ;-)
        > >
        > > I'll work on your puzzle if you change the prize to $19,000.
        > > You'll still get to keep $1,000. :)
        > >
        > > How about if I turn off all of the lights but one? Is that worth
        > > anything?
        >
        > Does this help decrypting it:
        >
        > http://webpages.charter.net/rsdotson/button_game.js ?
        >

        Okay, if you feed the contents of the variable "enkripsi" into

        http://scriptasylum.com/tutorials/encdec/theft.html

        Ron's secreted code will be revealed. I will not reproduce it here in
        fear of breaking copyright and therefore being sued. Or have I done it
        already with my copy and paste function I have here at my disposal.
        The cybercops are probably on their way. Enjoy!

        Paul
      • Ron
        Wow. Well that s what I get for using a free obfuscation program I guess. Looks like I should have at least removed the comments and used one of the fee based
        Message 3 of 22 , Jul 26, 2005
          Wow. Well that's what I get for using a free obfuscation program I
          guess. Looks like I should have at least removed the comments and
          used
          one of the fee based encoders. Oh well...

          The only reason for the copyright notice by the way, is a (perhaps
          lame?) attempt at preventing anyone from duplicating my code and
          posting it on their own website with themselves as the recipient of
          the
          winning numbers (although I would be *extremely* surprised if anyone
          ever solved this puzzle visually).

          -- Ron
        • Brian Ball
          It just looks like the RSA-640 challenge to me. The hex string in the code converts to the 193 digit RSA-640 challenge. And yes, solving the RSA-640 challenge
          Message 4 of 22 , Jul 26, 2005
            It just looks like the RSA-640 challenge to me. The hex string in the
            code converts to the 193 digit RSA-640 challenge.
            And yes, solving the RSA-640 challenge visually would be a nice
            trick :-)



            --- In primenumbers@yahoogroups.com, "Ron" <Yaho6Hb3c@s...> wrote:
            > Wow. Well that's what I get for using a free obfuscation program I
            > guess. Looks like I should have at least removed the comments and
            > used
            > one of the fee based encoders. Oh well...
            >
            > The only reason for the copyright notice by the way, is a (perhaps
            > lame?) attempt at preventing anyone from duplicating my code and
            > posting it on their own website with themselves as the recipient of
            > the
            > winning numbers (although I would be *extremely* surprised if anyone
            > ever solved this puzzle visually).
            >
            > -- Ron
          • 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 5 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 6 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 7 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 8 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 9 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 10 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 11 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 12 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 13 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 14 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 15 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 16 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 17 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 18 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 19 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.