Implement 64-bit modular exponentiation safely
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Implement a function to compute (a^b) mod m where 0 ≤ a,b < 2^61−1 and 1 ≤ m < 2^61−1 using only 64-bit operations without overflow. Provide implementations for fast modular multiplication that avoids overflow and fast modular exponentiation. Include comprehensive tests and analyze the time and space complexity.
Quick Answer: This question evaluates proficiency in modular arithmetic, safe 64‑bit integer operations, and algorithmic techniques for overflow‑resistant modular multiplication and exponentiation.