✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-002-074

Multiplication and Exponentiation Modulo n

Modular multiplication and exponentiation calculate products and powers while reducing intermediate or final results modulo a fixed positive integer.

(ab) mod n = ((a mod n)(b mod n)) mod n; a^k mod n can be computed using repeated squaring

Explanation

Multiplication in modular arithmetic is compatible with congruence. If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n). Therefore, large factors can be reduced before multiplication. Modular exponentiation extends this principle to powers: a^k mod n can be calculated by repeatedly reducing intermediate products. For very large exponents, repeated squaring provides an efficient method. This method expresses an exponent as a sum of powers of two and repeatedly squares the base modulo n. For example, 3^4 mod 7 can be calculated by observing that 3^2 = 9 ≡ 2 (mod 7), so 3^4 ≡ 2^2 = 4 (mod 7). Modular exponentiation is particularly important in public-key cryptography and algorithms involving large integers.

Variables

A

The base or first factor.

B

The second factor.

K

A nonnegative integer exponent.

N

The positive modulus.

Example or application

Problem

Calculate 5^4 mod 13.

Solution

First, 5^2 = 25 ≡ 12 (mod 13). Then 5^4 ≡ 12^2 = 144 ≡ 1 (mod 13), because 144 = 11 × 13 + 1.

Answer

5^4 mod 13 = 1

Text

The modular multiplication rule allows each factor to be replaced by its residue. Modular exponentiation applies repeated multiplication and reduction, with repeated squaring making large powers computationally manageable.

Key Points

  • Multiplication preserves congruence.

  • Each factor can be reduced modulo n before multiplication.

  • Exponentiation modulo n is repeated modular multiplication.

  • Repeated squaring efficiently calculates powers with large exponents.

  • Intermediate values can be reduced to prevent unnecessary growth.

  • Modular exponentiation is a central operation in several cryptographic algorithms.

Applications

  • RSA public-key cryptography.

  • Diffie–Hellman key exchange.

  • Digital signature algorithms.

  • Efficient computation with very large integers.

  • Number-theoretic algorithms and computational mathematics.

Learning Outcomes

  • Calculate products modulo n.

  • Evaluate small powers modulo n.

  • Explain the repeated-squaring method.

  • Recognize why modular exponentiation is useful for large computations.

Practice Questions

  • Calculate (12 × 17) mod 5.

  • Find 4^3 mod 7.

  • Calculate 7^4 mod 10.

  • Use repeated squaring to evaluate 3^8 mod 11.

  • Explain why modular reduction can be performed after each multiplication.

Related Concepts

  • Modular Addition

  • Congruence Relations

  • Repeated Squaring

  • Modular Inverses

  • Fermat's Little Theorem

Common Mistakes

  • Multiplying large numbers without reducing intermediate results when a simpler calculation is possible.

  • Confusing exponentiation with multiplication by the exponent.

  • Reducing the exponent modulo n without a theorem that justifies doing so.

  • Making arithmetic errors when reducing squared values.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Kenneth H. Rosen, Elementary Number Theory and Its Applications
  • Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography

Suggest a correction or source · More in Arithmetic & Number Theory