search

peterolson / BigInteger.js

An arbitrary length integer library for Javascript
The Unlicense
1.12k stars 187 forks source link

Changed modPow to also handle negative exponents #185

Closed pepijno closed 5 years ago

pepijno commented 5 years ago

Allow modPow to also handle negative exponents as a modular inverse followed by a normal modular exponentiation.

Right now modPow returns 0 which is unexpected behaviour since then (a^b mod n)*(a^(-b) mod n) mod n != 1. With the proposed changes modInv can throw an error if a has no multiplicative inverse but it is a more descriptive error than simply letting modPow return 0. Applying the changes results in the same behaviour as implementations of other languages such as Java's BigIntegers's modPow, PHP's bmodpow and python's pow.

For a reference on how to calculate negative exponents, see for example: https://ipfs.io/ipfs/QmXoypizjW3WknFiJnKLwHCnL72vedxjQkDDP1mXWo6uco/wiki/Modular_exponentiation.html

See also #184

coveralls commented 5 years ago

Coverage Status

Coverage increased (+0.02%) to 94.235% when pulling c0f80af2c2834d791100c834eedf44ea648e5b3d on pepijno:feature/modpow-negative-exponents into 2e0619371f90aedb8e44cb3ab983b18a5ac699aa on peterolson:master.

coveralls commented 5 years ago

Coverage Status

Coverage increased (+0.02%) to 94.235% when pulling c0f80af2c2834d791100c834eedf44ea648e5b3d on pepijno:feature/modpow-negative-exponents into 2e0619371f90aedb8e44cb3ab983b18a5ac699aa on peterolson:master.

coveralls commented 5 years ago

Coverage Status

Coverage increased (+0.02%) to 94.235% when pulling c0f80af2c2834d791100c834eedf44ea648e5b3d on pepijno:feature/modpow-negative-exponents into 2e0619371f90aedb8e44cb3ab983b18a5ac699aa on peterolson:master.

peterolson commented 5 years ago

Thanks