Bit interleaving

DTAshley at DTAshley at
Sat Apr 3 01:26:52 CEST 2004

> 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.


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.

> 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);
>     }

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".

-------------- 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