Bit interleaving

[DTAshley at aol.com]

<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