What does BigInteger.modPow do, and why is it central to public-key cryptography like RSA?
answer
- (base^exp) mod m without building the full power
- Square-and-multiply + reduce mod m each step → O(log exp)
- RSA encrypt m^e mod n, decrypt c^d mod n
- Negative exponent only if base invertible mod m
- Not constant-time → don't hand-roll production crypto
basics
~10 smodPow(exp, m) computes (this ^ exp) mod m efficiently, without ever building the gigantic full power. RSA encryption and decryption are exactly this modular exponentiation on huge numbers.
solid answer
~50 sBigInteger.modPow(exponent, modulus) returns (base ^ exponent) mod modulus. The point is efficiency and tractability: a naive base.pow(exponent).mod(m) would first materialize an astronomically large intermediate — for RSA-2048 the exponent alone is ~2048 bits — which is impossible to store. modPow uses square-and-multiply (exponentiation by squaring) and reduces modulo m at every step, so intermediates never exceed the modulus size, turning an exponential cost into roughly O(log exponent) multiplications. This is the core operation of RSA: encryption is c = m^e mod n and decryption is m = c^d mod n, and Diffie-Hellman key exchange is g^x mod p. The JDK implementation also uses Montgomery reduction and is the building block real crypto relies on. It additionally accepts a negative exponent when the base is invertible mod m (it then exponentiates the modular inverse). Note modPow is not guaranteed constant-time, so for production secrets you use vetted crypto libraries, not hand-rolled modPow on secret keys.
go deeper
Knows modPow computes a power then takes a remainder, and that it relates to encryption.
Explains why pow().mod() is infeasible for big exponents and that modPow uses square-and-multiply with per-step reduction.
Maps modPow onto RSA/Diffie-Hellman, knows the O(log exp) cost, the negative-exponent rule, and that it isn't constant-time.
Discusses side-channel/timing risks, Montgomery reduction, why production code must use vetted crypto providers rather than hand-rolled modPow, and the factoring-hardness security assumption.
## What modular exponentiation is "Modular" arithmetic is arithmetic on the **remainder** after dividing by a fixed number called the **modulus**. `17 mod 5 = 2` because 17 leaves remainder 2. **Modular exponentiation** is computing `base^exponent mod modulus` — raise a number to a power, then take the remainder. `BigInteger.modPow(BigInteger exponent, BigInteger modulus)` returns exactly `(this ^ exponent) mod modulus`. ## Why you can't just compute it the obvious way The naive approach `base.pow(exponent).mod(modulus)` first builds the **full power** `base^exponent`. In cryptography the exponent is hundreds or thousands of bits. `2^2048` has over 600 decimal digits; for realistic crypto sizes the full power would need more memory than exists on Earth. So you can never materialize it. ## The trick: square-and-multiply with reduction every step Two ideas combine: 1. **Exponentiation by squaring.** To compute `x^13`, note 13 in binary is `1101`. You don't multiply x by itself 13 times; you repeatedly square and conditionally multiply, walking the bits of the exponent. This takes about `log2(exponent)` squarings — for a 2048-bit exponent, roughly 2048 steps instead of 2^2048. 2. **Reduce modulo m after every operation.** The identity `(a * b) mod m = ((a mod m) * (b mod m)) mod m` means you can take the remainder at each step. So every intermediate stays smaller than the modulus, never blowing up. Combining the two gives the answer in about O(log exponent) big-number multiplications, each on numbers no larger than the modulus. The JDK goes further and uses **Montgomery reduction**, a technique that replaces the expensive division in each `mod` with cheaper shifts and multiplications. ## Why this is the heart of RSA **RSA** is a public-key cryptosystem. You have a modulus `n` (product of two large primes), a public exponent `e`, and a private exponent `d`. The math is: - **Encrypt:** `ciphertext = message^e mod n` - **Decrypt:** `message = ciphertext^d mod n` Both are *exactly* `modPow`. Its security rests on the fact that going forward (modPow) is fast, but reversing it — recovering `d`, which requires factoring `n` — is believed to be infeasible for large `n`. **Diffie-Hellman** key exchange is the same operation: each party computes `g^secret mod p`. ## Useful details - The modulus must be positive; an even modulus is allowed but uses a slower path. - A **negative exponent** is allowed *only* if the base has a multiplicative inverse modulo m (i.e. `gcd(base, m) = 1`); modPow then exponentiates that inverse. Otherwise it throws `ArithmeticException`. - `modPow` is **not guaranteed constant-time**, so its running time can leak information about secret exponents through timing side channels. For that reason you **do not roll your own RSA** with modPow on real secrets — use audited libraries (JCA/JCE providers) that defend against timing attacks. modPow is, however, the right tool for math problems, competitive programming, and understanding the primitive.
- Why is modPow vastly faster than pow().mod()?pow() builds the full, astronomically large power before reducing; modPow uses square-and-multiply and reduces modulo m at every step, keeping intermediates small and costing only ~O(log exponent) multiplications.
- When can modPow accept a negative exponent?Only when the base is invertible modulo m (gcd(base, m) = 1). It then computes the power of the modular inverse; otherwise it throws ArithmeticException.
saying these in an interview costs you the question
- Computing base.pow(exp).mod(m) for large exponents (intractable intermediate)
- Assuming modPow is constant-time / safe against timing attacks
- Thinking modPow security comes from the operation being hard to compute forward
- Forgetting the modulus must be positive