Bit interleaving
DTAshley at aol.com
DTAshley at aol.com
Sat Apr 3 01:26:52 CEST 2004
<BEGIN EXCERPT>
> Operations with points on an elliptic curve, in any number system, have
> the same effect. Once you provide for the basic operations (addition,
> multiplication, division, modulo, etc) to be efficient (which may, in
> turn, simply be providing more fundamental operations in an efficient
> manner), there are a finite number of high level function calls to
> implement ECs. So they shouldn't be in GMP.
<END EXCERPT>
I agree with you there, if by "finite number" you mean "won't have a profound
effect on efficiency".
If the user has to write a layer over the GMP to do what they want--that is
OK. But if the GMP does not provide the fundamental operations necessary for
the user to do this and get efficiency--that is a problem.
<BEGIN EXCERPT>
> With respect to the original question, is there a better way to implement
> his request behavior than something like:
>
> for (i = 0; i < nbits; ++i) {
> dst[(i*spread)/GMP_NUMB_BITS] |=
> ((src[i/GMP_NUMB_BITS] >> (i % GMP_NUMB_BITS)) & 1)
> << ((i * spread) % GMP_NUMB_BITS);
> }
<END EXCERPT>
I'm not seeing anything that will get better than O(N). The above looks O(N)
to me. (N is the number of bits in the argument.)
If spread is always 2, I'm seeing a lookup table enhancement that doesn't
change the order. But with arbitrary spread, I'm not seeing any enhancement over
the bit-testing above.
"seeing" = "envisioning in my head".
Dave.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /list-archives/gmp-discuss/attachments/20040402/2d961485/attachment.htm
More information about the gmp-discuss
mailing list