Re: [boost] Big Int

From: Christoph Ludwig (cludwig_at_[hidden])
Date: 2005-03-05 06:38:29

On Fri, Mar 04, 2005 at 08:53:15AM +0100, Richard Peters wrote:
> I have been working on a big integer library, and it is almost ready for
> review. However, at the moment I haven't got much time to work on the
> library, because I'm graduating in three months. After those three months, I
> will try to get the library really ready for review. In the meantime, you
> can try out the library which is available from
> http://groups.yahoo.com/group/boost/files/big_integer/. I use it myself in
> my crypto library, and it works quite well IMHO, although every now and then
> a bug shows up.

I only superficially looked through the documentation and the headers of your
library. And as much as I liked to, I cannot invest much time in the
evaluation of your work. Nevertheless, here are some random notes in no
particular order:

 * The documentation is obviously unfinished. What I'd like to see besides the
   missing parts of the reference are some statements that clarify
    - what sets your library apart from other bigint libraries (The maintained
      ones that I am aware of are GnuMP / cln, NTL, Piologie, MIRACL. I am
      sure there are more.)
    - how your library relates to the proposal for a bigint type for the C++
      standard library (papers N1692 and N1744).

 * Specification of div_and_mod(): The formal input parameters are named x and
   y, but the effect section refers to e and f.

 * You always refer to the parameter types as "IntegerType", but some
   parameters need obviously to be references. What can IntegerType actually
   be? Only big_integer and types resulting from the expression template
   machinery built around big_integer? Or also int, long etc.? If the latter,
   what happens if there is an overflow?

 * I am glad you defined conversions to bit-strings in little / big endian
   format. That's something I missed from time to time in other libraries.

 * Did I miss the functions that convert big_integer to long, double etc.? And
   the other way around, how can I convert a double to a big_integer? (Such
   conversion functions are essential in my area of interest, lattice basis
   reduction.) 

 * The function names group_divide and group_inverse are too generic, IMO.
   They don't convey that you are referring to the prime residue group mod
   m. As soon as you start implementing, e.g., EC arithmetic or the arithmetic
   in GF(p^n), the names become confusing because there are several groups
   involved. I'd prefer something along the lines of divide_mod, inverse_mod.

 * There are some functions in NTL I found convenient and that I didn't see
   in your library: E.g., bit-wise operators, Hamming-weight, CRT,
   logarithm with result type double. Do you plan to support these? (There are
   even more functions in NTL, like Jacobi symbol, primality tests etc. that
   are required in any library for computational number theory. Do you have a
   clear policy what belongs in your big_integer library and what you consider
   to be too specialized?)

Again, this is after a superficial look only, so it's likely I missed
something. 

Regards

Christoph

-- 
http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/cludwig.html