Feature request: mp_expt

[nomeata]

trafficstars

~/build/libtommath $ grep expt tommath.h 
int mp_2expt(mp_int *a, int b);
int mp_expt_d(const mp_int *a, mp_digit b, mp_int *c);
int mp_expt_d_ex(const mp_int *a, mp_digit b, mp_int *c, int fast);
int mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y);

I am missing

int mp_expt(const mp_int *a, const mp_int *b, mp_int *c);

I know that unless a is -1, 0 or 1, a power that does not fit in a mp_digit will definitely go out-of-memory. But as a user of this library it would still be nice to have libtommath take care of handling the three bases where it does work, and also to provide a nice uniform interface.

[minad]

See here https://github.com/libtom/libtommath/pull/201. I am not a fan honestly. This function won't work in most cases. I would rather like to have mp_expt_int or mp_expt_long which doesn't depend on the possibly small size of mp_digit (MP_8BIT => sizeof(mp_digit)==1).

[czurnieden]

I am not a fan honestly.

Neither am I but something is definitely needed for the low-mp users.

But another small data type besides mp_digit does not make much sense. In that case I would prefer to deprecate int mp_expt_d(const mp_int *a, mp_digit b, mp_int *c); in favor of int mp_expt_d(const mp_int *a, unsigned long b, mp_int *c);.

Adapting to that API is nothing more than a cast for the users (unsigned long is large enough to hold all MP_DIGIT_BIT sizes). Not much work, I think.

Also not much work would it be to implement it. Again, not much work to add a macro/function to do the aforementioned casting for the users, so no API change, just additional functionality-

[minad]

Neither am I but something is definitely needed for the low-mp users.

Why? What is the advantage in contrast to mp_expt_int or mp_expt_long?

I agree that mp_expt_d should be deprecated in favor of mp_expt_int then. I generally don't like the exposure of mp_digit in the public api. Functions should take int/uint instead.

[czurnieden]

Why? What is the advantage in contrast to mp_expt_int or mp_expt_long?

I thought I made it clear that you had good enough arguments to persuade me to drop it in favor of a version that takes unsigned long? (unsigned int is too small for the 60 bit limbs and yes I'm aware of X32, I just ignore it ;-) )

I generally don't like the exposure of mp_digit in the public api.

A bigger problem for me is the unsigned character of mp_digit, especially for the arithmetical functions. Every time you need a negative input you need an extra step. It would be a large advantage if you can just do a mp_add_d(&a,-123,&b) instead of fiddling with the sign afterwards. A signed long instead of the dreaded mp_digit would be highly appreciated!

You also don't need to change the API directly, you can use the same macro/function as proposed in my last comment here (just a bit of extra for the sign) and deprecate slowly.

Yes, I really like your idea and hope I'm not the only one!

[minad]

It seems this can be closed in favor of implementing mp_expt_int etc as discussed in #243.

[sjaeckel]

We should probably discuss with @nomeata what will solve his problem, because IIUC creating a mp_expt_long() or similar won't solve it. Or am I wrong?

[nomeata]

You are correct, that it wouldn’t solve my issue (problem is too strong), but I understood that

I am not a fan honestly. This function won't work in most cases.

means the feature request was rejected which is fine, I can implement the wrapper that checks and extracts the low bits myself.

[minad]

@nomeata I didn't want to give the impression that things are already decided and closed due to your positive reaction to my second comment. I think mp_expt_bigint won't be a good addition with regards to API design and proposed a better alternative which covers most realistic use cases. In cases like yours it is probably better to extract the low bits.

[nomeata]

But unless I am missing something, essentially every user of libttommath who uses it to implement a language that offers a power operator on Integers will have to do that, meaning that their implementation of ** will be more involved than the other numeric operations, which map directly and uniformly to a mp_foo function, right?

Just to clarify: I am not proposing do anything else than to extract the low bits and use mp_expt_long. I am merely suggesting that libtommath might also offer the (more convenient, to some) interface as well.

[minad]

I understand your use case. If we have mp_expt_long we could discuss offering a convenience interface mp_expt_bigint which will extract the low bits for 0,+-1 and fail with MP_VAL for numbers larger than long and long before that due to MP_MEM.

I only want to avoid a biginteger implementation where larger than int/long exponents are allowed (as proposed in #201).

Concerning your compiler/language use case - It is a matter of where we are doing the error handling and special casing. I guess you won't win terribly much by pushing the special casing to the lower layer. Right now it seems there is no such special casing present in the library. I would just offer some kind of primitive like prim_expt : Integer -> Int32 -> Either Error Integer, with the Either somehow unboxed. But maybe the API you are suggesting is preferable for the general user.

Reopen for more discussion.

[nomeata]

For simple applications, just getting a “fake” MP_MEM (or MP_VAL) back for absurdly large exponents is very nice from the library user’s point of view, if they don’t want to handle this separately than 2*b where b might fits a long, but still overflows memory.

[czurnieden]

I think this issue has been resolved by #304 and its relatives. If that is not the case feel free to reopen.