mp_exptmod(41, -1, 1) incorrectly errors out with MP_VAL

[MasterDuke17]

These values are in fact tested to not hang (6fa127b), and then a subsequent commit mentions that something seems off (b250ec4#diff-aa67c18ca27d74fae0446b5cd9376391R143-R146). Java, Python, Perl, and https://www.dcode.fr/modular-exponentiation all agree the answer should be 0.

[czurnieden]

The code in mp_exptmod.c takes the usual path to compute a^b mod p with b < 0 by computing the modular multiplicative inverse d to be able to compute d^(-b) mod p.

There are two algorithms to compute the modular multiplicative inverse in LibTomMath: s_mp_invmod_odd(const mp_int *a, const mp_int *b, mp_int *c) for odd p and s_mp_invmod for the rest. Here we have p = 1 which is an odd number, so s_mp_invmod_odd gets used. That code contains the lines

   /* we need y = |a| */
   if ((err = mp_mod(a, b, &y)) != MP_OKAY)                       goto LBL_ERR;

   /* if one of x,y is zero return an error! */
   if (mp_iszero(&x) || mp_iszero(&y)) {
      err = MP_VAL;
      goto LBL_ERR;
   }

Here a = a from mp_exptmod and b = p and with a = 42 and p = 1 we get 42 % 1 = 0 which triggers mp_iszero(&y) and you get your unexpected MP_VAL.

So far, so bad.

As there are several ways to solve that problem: any suggestions?

Maybe just a shortcut for p = 1, because for all n in N and n > 0, n = 0 mod 1 anyway?

[MasterDuke17]

Sounds reasonable to me (but then again, I don't know anything at all about modular multiplicative inverses...).

…

On Wed, Feb 5, 2020 at 2:36 AM Christoph Zurnieden ***@***.***> wrote: The code in mp_exptmod.c takes the usual path to compute a^b mod p with b < 0 by computing the modular multiplicative inverse d to be able to compute d^(-b) mod p. There are two algorithms to compute the modular multiplicative inverse in LibTomMath: s_mp_invmod_odd(const mp_int *a, const mp_int *b, mp_int *c) for odd p and s_mp_invmod for the rest. Here we have p = 1 which is an odd number, so s_mp_invmod_odd gets used. That code contains the lines /* we need y = |a| */ if ((err = mp_mod(a, b, &y)) != MP_OKAY) goto LBL_ERR; /* if one of x,y is zero return an error! */ if (mp_iszero(&x) || mp_iszero(&y)) { err = MP_VAL; goto LBL_ERR; } Here a = a from mp_exptmod and b = p and with a = 42 and p = 1 we get 42 % 1 = 0 which triggers mp_iszero(&y) and you get your unexpected MP_VAL. So far, so bad. As there are several ways to solve that problem: any suggestions? Maybe just a shortcut for p = 1, because for all n in *N* and n > 0, n = 0 mod 1 anyway? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#475?email_source=notifications&email_token=ACOHYUJV5FUO6IG4VAANXTTRBIQ3DA5CNFSM4KQBAEZ2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKZ57JQ#issuecomment-582213542>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACOHYUOXOXTFJ35D5APKLMLRBIQ3DANCNFSM4KQBAEZQ> .

[MasterDuke17]

Oh, and mp_exptmod(42, -1, 7) is still hanging.

…

On Wed, Feb 5, 2020 at 2:36 AM Christoph Zurnieden ***@***.***> wrote: The code in mp_exptmod.c takes the usual path to compute a^b mod p with b < 0 by computing the modular multiplicative inverse d to be able to compute d^(-b) mod p. There are two algorithms to compute the modular multiplicative inverse in LibTomMath: s_mp_invmod_odd(const mp_int *a, const mp_int *b, mp_int *c) for odd p and s_mp_invmod for the rest. Here we have p = 1 which is an odd number, so s_mp_invmod_odd gets used. That code contains the lines /* we need y = |a| */ if ((err = mp_mod(a, b, &y)) != MP_OKAY) goto LBL_ERR; /* if one of x,y is zero return an error! */ if (mp_iszero(&x) || mp_iszero(&y)) { err = MP_VAL; goto LBL_ERR; } Here a = a from mp_exptmod and b = p and with a = 42 and p = 1 we get 42 % 1 = 0 which triggers mp_iszero(&y) and you get your unexpected MP_VAL. So far, so bad. As there are several ways to solve that problem: any suggestions? Maybe just a shortcut for p = 1, because for all n in *N* and n > 0, n = 0 mod 1 anyway? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#475?email_source=notifications&email_token=ACOHYUJV5FUO6IG4VAANXTTRBIQ3DA5CNFSM4KQBAEZ2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKZ57JQ#issuecomment-582213542>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACOHYUOXOXTFJ35D5APKLMLRBIQ3DANCNFSM4KQBAEZQ> .

[minad]

@czurnieden I think these functions need a complete rewrite due to their complexity ;)

[MasterDuke17]

Oh, and mp_exptmod(42, -1, 7) is still hanging.

Whoops, sorry, accidentally tested with an old version of Rakudo, ignore that.

[czurnieden]

@czurnieden I think these functions need a complete rewrite due to their complexity ;)

What's holding you back? >;->

But serious: I think that an exception for p = 1 should do it. At least for now.
Or did you (plural) find more problems?

[minad]

@czurnieden I think these functions need a complete rewrite due to their complexity ;)
What's holding you back? >;->

No free time and I don't use and don't need the functions right now.

But serious: I think that an exception for p = 1 should do it. At least for now.

Agree.

Or did you (plural) find more problems?

When I went over the library and applied simplifications the expmod and reduction functions stood out as overly complex in contrast to the rest of the library. Maybe we could gradually apply some simplifications, which will hopefully also increase the confidence in the implementation. There is still some work to do regarding api cleanup, e.g., #466 etc.