[xint] Utility question, how to implement...
Chad, Unfortunately I don't have time to do a review of your library (even a quick one). But I do have one question... In my general code library I have an implementation of a one-way-accumulator based on the facilities provided by the Botan library. It's an algorithmically efficient implementation using Barrett reducers for modulo exponentiation with small bases and large exponents. 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. -- -- 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
On Fri, 04 Mar 2011 10:10:36 -0600 Rene Rivera <grafikrobot@gmail.com> wrote:
Unfortunately I don't have time to do a review of your library (even a quick one). But I do have one question... In my general code library I have an implementation of a one-way-accumulator based on the facilities provided by the Botan library. It's an algorithmically efficient implementation using Barrett reducers for modulo exponentiation with small bases and large exponents. 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. -- Chad Nelson Oak Circle Software, Inc. * * *
On 3/5/2011 12:00 PM, Chad Nelson wrote:
On Fri, 04 Mar 2011 10:10:36 -0600 Rene Rivera<grafikrobot@gmail.com> wrote:
Unfortunately I don't have time to do a review of your library (even a quick one). But I do have one question... In my general code library I have an implementation of a one-way-accumulator based on the facilities provided by the Botan library. It's an algorithmically efficient implementation using Barrett reducers for modulo exponentiation with small bases and large exponents. 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. Note, it's not open-source code by any means. So other reading take that into consideration. PS. Also excuse the code itself.. It's really old and doesn't follow any of my more recent library-centric programming practices. -- -- 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
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. -- Chad Nelson Oak Circle Software, Inc. * * *
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
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. * * *
Chad Nelson wrote:
Rene Rivera <grafikrobot@gmail.com> wrote:
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?
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.)
That is, of course, very likely. The hidden part of the question is whether such an algorithm can be implemented efficiently without needing access to the internals. Note, this is the same thing being asked related to expression templates. The idea there is to reduce a non-trivial sequence of operations to some provided public function that does a combination of operations in one call taking advantage of the internals. IOW, if you provide a function that does "add two numbers and multiply the result by a third" implemented in some manner that is more efficient than the naive sequence, then you can use ETs to recognize that pattern (product of a sum and a third value) and call the special function rather than apply the naive sequence of operations. By recognizing common multi-step-in-one patterns, providing functions for those patterns, and using ETs to trigger their use, you enable more efficiency without needing to grant access to the internals for new algorithms desirous of that efficiency. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On Mon, 7 Mar 2011 10:03:37 -0500 "Stewart, Robert" <Robert.Stewart@sig.com> wrote:
[...] 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.)
That is, of course, very likely. The hidden part of the question is whether such an algorithm can be implemented efficiently without needing access to the internals.
That depends on the algorithm. There are a few (random_by_size springs to mind) that require access to the internals for maximum efficiency. However, most algorithms have no need for that. Even relatively complex ones, like powmod with the Montgomery reduction algorithm, can be efficiently expressed entirely through the current public interface.
Note, this is the same thing being asked related to expression templates. The idea there is to reduce a non-trivial sequence of operations to some provided public function that does a combination of operations in one call taking advantage of the internals. IOW, if you provide a function that does "add two numbers and multiply the result by a third" implemented in some manner that is more efficient than the naive sequence, then you can use ETs to recognize that pattern (product of a sum and a third value) and call the special function rather than apply the naive sequence of operations. [...]
Yes, I'm starting to realize that. I'm not sure that it will be of much use to most people, but it could be indispensable to a few. I'm pretty sure it can be added without changing the existing public interface or breaking client code that uses it, but I'm still pondering the possibilities. -- Chad Nelson Oak Circle Software, Inc. * * *
participants (3)
-
Chad Nelson -
Rene Rivera -
Stewart, Robert