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

Subject: Re: [boost] [xint] Utility question, how to implement...
From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2011-03-05 22:58:23

On 3/5/2011 9:44 PM, Chad Nelson wrote:
> On Sat, 05 Mar 2011 14:00:51 -0600
> Rene Rivera<grafikrobot_at_[hidden]>  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