From: "Christoph Ludwig" <cludwig@cdc.informatik.tu-darmstadt.de>
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
missing parts of the reference are some statements that clarify - what sets your library apart from other bigint libraries (The
Thank you for going through my library :) 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).
Yes, the documentation is not finished. I would like to use boostbook for documentation, but I haven't been able to set it up right. This library is written purely in portable c++, and is therefore platform independent. An assembly implementation is probably a lot faster, but my library has the option to plug in other libraries. At the moment, cln and GnuMP can be used as back-end. My library will be released under the boost license. The bigint type proposed for the C++ standard library does not permit the use of expression templates. Using expression templates has a positive and a negative aspect: A significant speedup can be gained using expression templates. The downside is that templates cannot deduce the correct type of expressions, for example: template<class T> void f(T a, T b) will not work when invoked as f(x + y, x - y), because x + y returns an object of type different from x - y. Because the C++ standard library proposal specifies the result type of the operators to be of type const integer, a library implementing that proposal cannot use expression templates.
* 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?
The idea is to allow big_integer, types resulting from expression templates and int, long, etc. There's still some work in specifying all of this.
* 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.
I use these functions very much in my cryptography-related software. I wouldn't know what to do without them :)
* 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.)
I don't have functions converting to/from floating point types. Actually, I have never had the need for floating point values, and I'm wouldn't know how to implement them. If you'd like, I can contact you when I resume work on this library, so that we can work something out.
* 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.
Good point. 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?)
Well... I try to aim at core operations only. At the moment, I support jacobi symbol and primality testing, but I will almost certainly remove them. Bit-wise operators should probably be available. The other operations that you mentioned are without doubt useful, but I think they belong in a separate library.
Again, this is after a superficial look only, so it's likely I missed something.
Regards
Christoph
best regards, Richard Peters