Codacoda
Back to Academy

math misc

Modular Arithmetic

Modular arithmetic performs operations within a fixed range defined by a modulus. Modular exponentiation efficiently computes large powers modulo a number using repeated squaring. Key properties include distributivity over addition and multiplication.

Use Cases

  • •Cryptographic systems like RSA and Diffie-Hellman
  • •Hashing functions and hash table implementations
  • •Competitive programming problems involving large number computations

Complexity Analysis

MetricBestAverageWorst
TimeO(log n)O(log n)O(log n)
SpaceO(1)

Visualization

3^13 mod 7BitValuePowerResult
Binary of 13: 1101₂
Speed:1x
Compute 3^13 mod 7 using fast exponentiationStep 1 / 7

Implementation

Output

Click "Run Code" to see output...