CODEWITHSUNDEEP
moduloexponentlargenumbercomputation
user3063864
user3063864

Reputation: 721

How to calculate the mod of large exponents?

For example I want to calculate (reasonably efficiently)

2^1000003 mod 12321

And finally I want to do (2^1000003 - 3) mod 12321. Is there any feasible way to do this?

Upvotes: 4

Views: 5364

Answers (4)

RARE Kpop Manifesto
RARE Kpop Manifesto

Reputation: 2809

so this is a particular special case where intentionally NOT using an integer type is advantageous :

echo '2 1000003 12321' |

   function ________(___, __, _____,
                     _, ____, ______, _______) {

       #   ___| pow-base
       #    __| pow-expn
       # _____| modulus
       #      |
       #      |—-> ___^__ % _____

 1     ___ =   (_ =  ___ = int(___))^(((__ = int(__)) - \
             (__ %= ____ =               ___ = (_ += _)^(\
                 _______ = --_ + --_))) / ___) % (_____ = int(_____))

 1     ______ = (_+_______+_) * ____

 5     while (_______--)
 5         ___ = (___<______ ? ___ : ___-_____)^_^_ * \
                        _^((__ += __) < ____          \
                ? (____ <= (__ += __)         && (__ -= ____) + _) \
                : (____ <= (__ += __ -= ____) && (__ -= ____) + _) + _) % _____

 1     return ___
    }

4610

This is NOT a generic powmod() function,

but a tailored one specifically to take advantage of small modulus, exponentiation base of 2, and double-precision floating point ("double" hereafter).

It handles bits from MSB downwards without requiring any bit-shifting, division or modulo ops.

For modulus under 2^53, double data type allows one to jump ahead a few steps at the start - instead of dealing with the bits layer by layer, step 1 one could directly do the most significant 10-bits all at once (but only for base of 2, as that'll put it just shy of 2^1024)

In this example, exponent is split 1,000,003 (or base 4 : 3310021003) =>

high-10 bits of 976 (b4 : 33100), and 
 low-10-bits of 579 (b4 : 21003)

Since the modulus is only 12321, and 4th-root of 2^53 is roughly ~9741 (and you get 1 extra even for free), each round can go at double speed of 2-squares at once, thus halving number of expensive modulo operations needed. when the value is in this half-open range of (9742, 12320], simply subtract the modulus before squaring. that way it always stays under this 9741-2 upper bound, enabling 2-squarings each round.

That's why the profiler output only showed 5 rounds of the while( ) loop, despite not using any big-integer module - out of base 4 : 33100-21003, left half handled by 10-bits up front, then 5 rounds each for right side base-4 digits of 2, 1, 0, 0, and 3.

In double floating point, scaling mantissa by powers of 2 comes free of charge, which is why this function directly only performs 1 modulo each loop cycle.

That's a lot of time savings compared to 20-cycles of the loop.

Or say, you wanna verify the Mersenne Prime 8191, which is 13-bits full of 1s :

Instead of doing it by 13 rounds of the loop, this expression is literally all you need (without any big-integer library, as long as the data type of double floating-point)

(( 2^((8190 - 8190 % 8) / 8) % 8191 )^4 % 8191 )^2 * 2^(8190 % 8) % 8191

(( 2^((8190 - 8190 % 8) / 8)                % 8191 \
                         )^4                % 8191 \
                         )^2 * 2^(8190 % 8) % 8191

(( 2^((8190 - (x = 8190 % 8)) / 8) % 8191)^4 % 8191)^2 * 2^x % 8191

Upvotes: 0

Daniel Martin
Daniel Martin

Reputation: 23548

In some reasonably C- or java-like language:

def modPow(Long base, Long exponent, Long modulus) = {
  if (exponent < 0) {complain or throw or whatever}
  else if (exponent == 0) {
    return 1;
  } else if (exponent & 1 == 1) { // odd exponent
    return (base * modPow(base, exponent - 1, modulus)) % modulus;
  } else {
    Long halfexp = modPow(base, exponent / 2, modulus);
    return (halfexp * halfexp) % modulus;
  }
}

This requires that modulus is small enough that both (modulus - 1) * (modulus - 1) and base * (modulus - 1) won't overflow whatever integer type you're using. If modulus is too large for that, then there are some other techniques to compensate a bit, but it's probably just easier to attack it with some arbitrary-precision integer arithmetic library.

Then, what you want is:

(modPow(2, 1000003, 12321) + (12321 - 3)) % 12321

Upvotes: 3

lindgrenj6
lindgrenj6

Reputation: 13

Well in Java there's an easy way to do this:

Math.pow(2, 1000003) % 12321;

For languages without the Math.* functions built in it'd be a little harder. Can you clarify which language this is supposed to be in?

Upvotes: -1

peppe
peppe

Reputation: 22724

Basic modulo properties tell us that

1) a + b (mod n) is (a (mod n)) + (b (mod n)) (mod n), so you can split the operation in two steps

2) a * b (mod n) is (a (mod n)) * (b (mod n)) (mod n), so you can use modulo exponentiation (pseudocode):

x = 1
for (10000003 times) {
    x = (x * 2) % 12321; # x will never grow beyond 12320
}

Of course, you shouldn't do 10000003 iterations, just remember that 21000003 = 2 * 21000002 , and 21000002 = (2500001)2 and so on...

Upvotes: 4

Related Questions