On Sat, 05 Mar 2011 21:58:23 -0600 Rene Rivera <grafikrobot@gmail.com> wrote:
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?
Certainly. When I implemented it, I don't recall any need to use any deep access to the library, just the public functions and operators. For that matter, pretty much everything in the library is implemented in terms of addition, subtraction, multiplication, division, modulus, comparisons, and the occasional bit-manipulation function or is_odd/is_even. All of which are in the public interface. Lower-level access might occasionally allow for a faster implementation, but it's almost never required. (I'd go so far as to say never, but there's an exception to every rule.)
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 :-\
Every integer algorithm I'm aware of can be implemented in terms of XInt's public interface, no low-level access required. It can't really be any other way, since math is nothing more or less than a language to elegantly and precisely describe reality, and we've never had low-level access to reality either. ;-) -- Chad Nelson Oak Circle Software, Inc. * * *