search

peterolson / BigInteger.js

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

Allow modPow to handle negative exponents #184

Closed pepijno closed 5 years ago

pepijno commented 5 years ago

When b is negative the equation a^b mod n is the same as c^-b mod n where c is the multiplicative inverse of a modulo n. It should be a relative small change to the code to also allow for negative exponents in the modPow method.

peterolson commented 5 years ago

This is an integer library. Allowing negative exponents would require handling of non-integer values. For example, 2^(-3) is not an integer.

pepijno commented 5 years ago

I am only talking about modular arithmetic in which case a negative exponent does result in an integer, for example 2^(-3) mod 11=7.

Happypig375 commented 5 years ago

2^(-3) mod 11 = 8^(-1) mod 11 = 1/8 mod 11 Since 11*0 < 1/8 < 11*1, = 1/8

pepijno commented 5 years ago

Modular exponentiation will always result in an element from the group (Z/nZ)*, since 1/8 is not an element of (Z/nZ)* we have that 2^(-3) mod n != 1/8 mod n. (See also https://www.wolframalpha.com/input/?i=PowerMod[2,+-3,+11])

For reference on how to calculate the negative exponent modulo n: https://math.stackexchange.com/questions/1015713/how-to-deal-with-negative-exponents-in-modular-arithmetic https://ipfs.io/ipfs/QmXoypizjW3WknFiJnKLwHCnL72vedxjQkDDP1mXWo6uco/wiki/Modular_exponentiation.html