Re: [boost] [xint] Utility question, how to implement...

Subject: Re: [boost] [xint] Utility question, how to implement...
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2011-03-05 23:31:38

On Sat, 05 Mar 2011 21:58:23 -0600
Rene Rivera <grafikrobot_at_[hidden]> 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.
*
*
*