On 3/5/2011 9:44 PM, Chad Nelson wrote:
On Sat, 05 Mar 2011 14:00:51 -0600 Rene Rivera<grafikrobot@gmail.com> wrote:
[...] My question is: How would I go about implementing the equivalent in your library?
NOTE: I can post my code if need be to make this a clearer question.
I'm afraid you'll have to, as I can't tell exactly what it does from your description. I'll be happy to try to port it to XInt.
OK, attached is the source code for my class that implements the algo. [...]
Thanks. I've taken a look, but unfortunately I don't recall much about Barrett reduction except that I implemented it once last year, for the xint::powmod function, and ended up replacing it with Montgomery reduction for some reason. As that seems to be the key part of your algorithm, I'd have to re-learn it to answer your question properly.
So the short answer is, someone (you or I) would have to implement Barrett reduction. Everything after that looks like it would be a pretty straightforward one-to-one conversion.
So I guess the key question, for the purposes of your library design, is: Is it possible to implement the Barret reduction as your library stands at the moment, without access to implementation details? Note, I'm not asking as an uber-expert on cryptography. The algorithm I'm using is almost straight from Applied Cryptology 2nd ed. So it seems somewhat key to be able to implement such book-algorithms in any arbitrary size integer library. Because face it, if users have to wait for the library author to implement such things, it will never get implemented in the general case. And the library will be of limited value and likely be a failure. I know, I'm sounding doom-and-gloom, but that's what I've seen repeatedly :-\ -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail