Re: CLN, GMP inputs

[Kevin Ryde]

Hans Aberg <address@hidden> writes:
> 
> As for the Z/nZ types, I have the idea of a type binary<n> with exactly n
> bits, where n is natural number, which should be the generalization of the
> C/C++ integral types. C/C++ are so written that one never can ensure the
> exact number of bits from compiler to compiler, so therefore I think a
> library with such a low-level optimized type might be useful.

I suppose the mpn routines make such a thing possible.  But for small
"n" no doubt just inlined "adc"s etc would be wanted for additions
etc, which starts to stray away from gmp's current features.

> Then, when n is not 2^k (or 0), one gets the other Z/nZ. I also know that
> in cryptology, one uses the finite fields F_{p^k}, where p is a prime
> number, and k is an integer >= 1. As speed is crucial in such contexts, it
> might be interesting to have library functions for such fields.

Yes, that idea has been kicked around for a while, Paul Zimmermann's
ecm factoring could use it for a start.  It'll no doubt get done at
some stage, though in fact remainders just with mpz_mod or whatever
aren't too bad.  I don't think REDC or Barrett etc have big
algorithmic advantages, just some practical considerations on smallish
sizes.

> As for the ref count and the unboxed number representation, perhaps it is
> possible to implement it on the C-level: One only mimics what one might do
> in C++.

An idea to store one limb values in the mpz_t itself, not through
_mp_d[0] got kicked around for a while.  I think it's been dropped as
too much work for too little gain.

> typedef struct {
>   union {
>     mp_int     _mp_n;
>     mp_limb_t* _mp_all;        /* Pointer to all.  */
>   };
>   int unboxed;
> } __mpz_struct;
> 
> #define _mpz_alloc  _mp_all[0]
> #define _mpz_count  _mp_all[1]
> #define _mpz_size   _mp_all[2]
> #define _mpz_d      _mp_all + 3

I guess that's an idea, but geared towards c++ where those reference
counts can be maintained magically.  I think the current scheme
probably suits plain c better.

> -- I figure that the library isn't thread safe as it now stands, because
> the functions gets references to objects, and if those referenced objects
> are not locked, another thread might screw it up by changing them too in
> mid-computation.

Two threads writing the same mpz_t, or a thread attempting to read
while another is writing, will fail.  That's clarified in the manual
for the next release.  The same considerations no doubt apply to any
non-atomic objects, gmp isn't special in that regard.