Feature requests for BigInt

[danwallach]

I'm looking at porting some code from java.math.BigInteger to use BigInt, and thus hopefully be multiplatform. Here are the missing features that would be handy:

• Conversion to and from strings with arbitrary radix (or, at least base 10 and base 16). The current toString() method only supports base 16.
• Conversion to and from various binary representations, like ByteArray (you might want to offer little endian and big endian options, since who knows what other libraries might be doing; some libraries are even doing two's complement for negative numbers, but it's unclear they'll write them out that way)
• modInverse (although this could be done less efficiently by using modPow to the modulus minus one)
• For the JVM, conversions to and from BigInteger

[altavir]

Thank you very much for the issue. Can you clarify about ByteArray representation? Are there any specifications for it? Right now we use Int array for the magnitude so it is quite easy to dump it somewhere. I guess that in big-endian it will look the same for byte-based representation, but for little-endian, it will depend on the size of the chunk.

[danwallach]

Here's what java.math.BigInteger says for its toByteArray method:

Returns a byte array containing the two's-complement representation of this BigInteger. The byte array will be in big-endian byte-order: the most significant byte is in the zeroth element. The array will contain the minimum number of bytes required to represent this BigInteger, including at least one sign bit, which is (ceil((this.bitLength() + 1)/8)). (This representation is compatible with the (byte[]) constructor.)

Meanwhile, if you look at the gmpy Python front-end for GMP, it has functions like to_binary and from_binary with wildly unhelpful documentation:

to_binary(x) -> bytes Return a Python byte sequence that is a portable binary representation of a gmpy2 object x. The byte sequence can be passed to gmpy2.from_binary() to obtain an exact copy of x's value. Works with mpz, xmpz, mpq, mpfr, and mpc types. Raises TypeError if x is not a gmpy2 object.

And what exactly is this "portable" representation? So far as I can tell from here (https://gmplib.org/manual/I_002fO-of-Integers):

The integer is written in a portable format, with 4 bytes of size information, and that many bytes of limbs. Both the size and the limbs are written in decreasing significance order (i.e., in big-endian).

So, it would make some sense for kmath to work interchangeably with BigInteger, and perhaps to have some support for GMP.

[altavir]

Looks good. If you could make a PR, it would be quite welcome. Otherwise, I will return to this issue when I have a little bit more free time.

[danwallach]

I can't promise anything, but I'll see if I can work on it.