CDR: Re: why should it be trusted?

[Riad S. Wahby]

Sampo A Syreeni <ssyreeni at cc.helsinki.fi> wrote:
> I think addition is bounded by something more like o(n) - carry propagation
> limits it. Anyway, your point is accurate. There are proven NP-hard problems
> and there have even been attempts to find ones with easy inverses for use in
> crypto. I don't think any of them have succeeded.

If you're talking about the carries actually falling through full
adders, there is a method called carry lookahead that computes carries
in a tree (with branching factor 2).  Computing the sum bits from the
carries is a constant time independent of the number of bits in the
adder, so the process is overall Theta(log(N)).

On the other hand, if you're talking about speed of propagation
through traces, you're right for large gate size.  However, as gates
get smaller, the speed of propagation becomes less important, and the
adder speed asymptotically approaches Theta(log(N)).

--
Riad Wahby
rsw at mit.edu
MIT VI-2/A 2002

5105
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 1188 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks-legacy/attachments/20001018/d504d881/attachment.sig>