029 — Modular Exponentiation

এটা Level 2-এর engine। 028-এ গুণ শিখেছ; এখন সেই গুণকে চালাকি করে সাজিয়ে বিশাল power বের করব — 3^(10^18) % m-ও মাত্র ~60 ধাপে। interview-তে এটা হাতে লিখতে বলবে, তাই dry run-টা খাতায় নিজে করো; built-in pow জানার পাশাপাশি ভেতরের খেলাটা বোঝা চাই।

Source

• Original source: CP-Algorithms — Binary Exponentiation
• Platform: CP-Algorithms — https://cp-algorithms.com/algebra/binary-exp.html, CSES Exponentiation — https://cses.fi/problemset/task/1095
• Topic: Math-based programming fundamentals → Level 2: Modular Arithmetic
• Difficulty: Medium
• Pattern: square & multiply (binary exponentiation)
• Basic idea inherited from: 028 — Modular Multiplication (প্রতি গুণে mod)

1. Problem in simple words

তিনটে সংখ্যা a (base), b (exponent, b ≥ 0), আর m (m > 0) দেওয়া। বের করতে হবে a^b % m — মানে a-কে নিজে দিয়ে b বার গুণ, তারপর mod m।

আসল challenge: b বিশাল হতে পারে (10¹⁸ পর্যন্ত)। a-কে b বার গুণলে loop b বার ঘোরে — ও পথে মহাবিশ্বের আয়ু শেষ। চাই O(log b)-তে উত্তর।

2. What is the math idea?

মূল idea — binary exponentiation (square-and-multiply)। exponent-কে binary-তে ভাবো।

যেমন 13 = 1101₂ = 8 + 4 + 1, তাই:

a^13 = a^8 × a^4 × a^1

আর a^1, a^2, a^4, a^8 — প্রতিটা আগেরটার square:

a^2 = (a^1)², a^4 = (a^2)², a^8 = (a^4)²

মানে: base-কে বারবার square করো, আর exponent-এর binary-তে যেখানে যেখানে bit 1, সেখানকার power-টা উত্তরে গুণে নাও। প্রতি step-এ 028-এর modular multiplication। b-এর binary-তে bit সংখ্যা log₂(b) — তাই O(log b) ধাপ।

3. Which basic idea does this inherit from?

সরাসরি 028 — Modular Multiplication থেকে। binary exponentiation-এর প্রতিটা ধাপ — square (a = a*a % m) আর multiply (result = result*a % m) — দুটোই 028-এর "প্রতি গুণে mod" নিয়ম।

028 না থাকলে এখানে মাঝের সংখ্যা বিশাল হয়ে overflow/slowness হতো। আর exponent-কে binary-তে ভাঙার idea-টা Level 0-এর "শেষ bit দেখা" (b & 1) আর "bit shift" (b >> 1)-এর সাথে যুক্ত — পুরনো tool নতুন কাজে।

4. Real-life analogy

ভাবো তোমাকে একটা কাগজ 8 বার ভাঁজ করতে হবে। এক এক ভাঁজ করলে 8 বার খাটতে হয়। কিন্তু চালাকি: এক ভাঁজ করলে 2 স্তর, সেটা আবার ভাঁজ করলে 4, আবার করলে 8 — মাত্র 3 বারেই 8 স্তর! প্রতিবার আগেরটা দ্বিগুণ হচ্ছে।

power-ও তেমন: a-কে square করলে exponent দ্বিগুণ হয় (a → a² → a⁴ → a⁸)। তাই 8 power পেতে 8 গুণ নয়, 3 square যথেষ্ট। আর exponent যদি ঠিক 2-এর power না হয় (যেমন 13), তখন মাঝে মাঝে দরকারি টুকরোগুলো (a^8, a^4, a^1) আলাদা করে জমিয়ে রাখি — সেটাই "multiply" ধাপ।

5. Visual explanation

3^13 % 7 — 13-কে binary-তে ভাঙা:

13 = 1101₂ = 8 + 4 + 1
3^13 = 3^8 × 3^4 × 3^1   (যেখানে bit 1, সেই power নেব)

bit:    1    1    0    1     <- 13 = 1101, ডান থেকে পড়ি: 1,0,1,1
power:  3^8  3^4  3^2  3^1
নেব?    হ্যাঁ হ্যাঁ  না  হ্যাঁ

square করে করে এগোনো (mod 7):

3^1 = 3
3^2 = 3^1 × 3^1 = 9  % 7 = 2
3^4 = 3^2 × 3^2 = 4  % 7 = 4   (2×2)
3^8 = 3^4 × 3^4 = 16 % 7 = 2   (4×4)

উত্তর = 3^8 × 3^4 × 3^1 = 2 × 4 × 3 = 24 % 7 = 3

6. Example input and output

a    b    m    ->  a^b % m       check
-----------------------------------------------
3    13   7    ->  3             3^13 = 1594323, % 7 = 3
2    10   1000 ->  24            1024 % 1000 = 24
5    0    13   ->  1             যেকোনো^0 = 1
7    1    100  ->  7             a^1 = a
2    100  ...  ->  বিশাল         O(log) তেও ঝটপট
10   5    1    ->  0             mod 1 = সব 0!

edge case দুটো খেয়াল করো: b = 0 হলে উত্তর 1 (যেকোনো সংখ্যার শূন্যতম power 1), আর m = 1 হলে উত্তর সবসময় 0 (এক ঘরের ঘড়ি)।

7. Brute force thinking

সবচেয়ে সরল: a-কে b বার গুণো, প্রতি step-এ mod।

def power_brute(a, b, m):
    result = 1
    for _ in range(b):
        result = result * a % m     # b বার গুণ
    return result

ঠিক উত্তর দেয়, আর প্রতি step-এ mod নেওয়ায় সংখ্যা ছোটও থাকে। সমস্যা শুধু একটাই — loop চলে b বার।

8. Why brute force may be slow

loop ঘোরে ঠিক b বার। b = 10^18 হলে 10^18 বার গুণ — সেকেন্ডে 10^8-10^9 operation ধরলেও কয়েকশো বছর লাগবে। interview/CP-তে এটা অসম্ভব।

b = 10^18 হলে:
  brute (O(b)):   10^18 বার গুণ  ->  কার্যত অসম্ভব
  binary (O(log b)): ~60 বার গুণ  ->  চোখের নিমেষে

log2(10^18) ≈ 60  ->  পার্থক্য: 10^18 vs 60

মূল শিক্ষা: exponent linearly না কমিয়ে প্রতি step-এ অর্ধেক করো (binary)। তাহলেই O(b) → O(log b)।

9. Better thinking

exponent-কে binary ভেবে square-and-multiply চালাই: base বারবার square করো; exponent-এর last bit 1 হলে current base-টা result-এ গুণো; তারপর exponent-কে ডানে shift (অর্ধেক) করো।

def power_mod(a, b, m):
    result = 1
    a %= m                          # base আগে ঘড়িতে নামাই
    while b > 0:
        if b & 1:                   # exponent-এর last bit 1?
            result = result * a % m # এই power-টা উত্তরে নাও
        a = a * a % m               # base square করো (exponent দ্বিগুণ হলো)
        b >>= 1                     # পরের bit-এ যাও (exponent অর্ধেক)
    return result

প্রতি iteration-এ b অর্ধেক হয় — তাই মোটে log₂(b) বার ঘোরে। প্রতিবার একটা square, কখনো একটা multiply — সব 028-এর modular multiplication।

10. Thinking tweak

আসল "আহা!": exponent-কে এক করে না কমিয়ে binary-তে ভাবো — প্রতি step-এ base square হলে exponent দ্বিগুণ "ঢাকা" পড়ে। তাই b বার গুণের বদলে log b বার square যথেষ্ট, মাঝে মাঝে দরকারি টুকরো তুলে রেখে।

দুটো ছোট tweak মনে রাখো:

• শুরুতেই a %= m — base বড় হলে আগেই ছোট করে নাও।
• b & 1 (last bit পড়া) + b >>= 1 (অর্ধেক করা) — Level 0-এর bit tool-ই এখানকার চাবি।

11. Step-by-step dry run

power_mod(3, 13, 7) — 13 = 1101₂:

step	b (binary)	last bit (b&1)	result	a (square হয়ে)
শুরু	1101	—	1	3 % 7 = 3
1	1101	1	1×3 % 7 = 3	3×3 % 7 = 2
2	110	0	3 (অপরিবর্তিত)	2×2 % 7 = 4
3	11	1	3×4 % 7 = 5	4×4 % 7 = 2
4	1	1	5×2 % 7 = 3	2×2 % 7 = 4

b এখন 0, loop থামল। উত্তর 3। Check: 3^13 = 1594323 = 7×227760 + 3 ✓।

লক্ষ করো: step 1-এ bit 1 → result-এ গুণ; step 2-এ bit 0 → শুধু square, result অপরিবর্তিত। আর a প্রতি step-এ square হয়ে 3 → 2 → 4 → 2 (= 3^1, 3^2, 3^4, 3^8 mod 7)।

12. Python solution

def power_mod(a, b, m):
    """a^b % m, square-and-multiply দিয়ে O(log b)। b >= 0, m > 0।"""
    result = 1
    a %= m
    while b > 0:
        if b & 1:                   # last bit 1 হলে এই power নাও
            result = result * a % m
        a = a * a % m               # base square
        b >>= 1                     # exponent অর্ধেক
    return result


def power_brute(a, b, m):
    """যাচাইয়ের জন্য সরল O(b) version।"""
    result = 1
    for _ in range(b):
        result = result * a % m
    return result


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert power_mod(3, 13, 7) == 3          # 3^13 % 7
assert power_mod(2, 10, 1000) == 24      # 1024 % 1000
assert power_mod(5, 0, 13) == 1          # যেকোনো^0 = 1
assert power_mod(7, 1, 100) == 7         # a^1 = a
assert power_mod(10, 5, 1) == 0          # mod 1 -> 0

# Python-এর built-in pow(a, b, m) এর সাথে মিলিয়ে দেখা:
assert power_mod(3, 13, 7) == pow(3, 13, 7)
assert power_mod(2, 1000, 1000000007) == pow(2, 1000, 1000000007)
assert power_mod(123456, 789, 1000000007) == pow(123456, 789, 1000000007)

# brute force-এর সাথেও ছোট input-এ মিল:
assert power_mod(3, 13, 7) == power_brute(3, 13, 7)
assert power_mod(2, 20, 97) == power_brute(2, 20, 97)

print(power_mod(3, 13, 7))               # 3
print(power_mod(2, 10, 1000))            # 24
print(power_mod(2, 1000, 1000000007))    # বড় উত্তর, ঝটপট
print("সব test pass!")

13. Line-by-line explanation

    result = 1
    a %= m

result শুরু 1 (গুণের identity)। a %= m-এ base আগেই ঘড়িতে নামাই, যাতে পরের গুণগুলো ছোট থাকে।

    while b > 0:
        if b & 1:
            result = result * a % m

b > 0 যতক্ষণ চলে। b & 1 দেখে exponent-এর last bit 1 কিনা — হলে current a (যেটা এখন a^(2^k) রূপ) result-এ গুণে নিই। এটাই "multiply" ধাপ, প্রতি গুণে % m।

        a = a * a % m
        b >>= 1

a = a * a % m — base square, মানে exponent এখন দ্বিগুণ ঢাকা পড়ল (a^1 → a^2 → a^4 ...)। b >>= 1 — exponent-কে ডানে shift, অর্থাৎ অর্ধেক, পরের bit-এ যাওয়া।

assert ... == pow(a, b, m) লাইনগুলো Python-এর built-in তিন-argument pow-এর সাথে মিলিয়ে দেখছে — এটাই সবচেয়ে শক্ত যাচাই। সব ঠিক থাকলে শেষে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

3
24
... (একটা বড় সংখ্যা)
সব test pass!

প্রথম লাইন power_mod(3, 13, 7) → 3। দ্বিতীয় power_mod(2, 10, 1000) → 24 (1024 mod 1000)। তৃতীয় power_mod(2, 1000, 1000000007) → একটা বড় সংখ্যা, কিন্তু O(log b)-তে চোখের নিমেষে। আগের সব assert (built-in pow-এর সাথে মিল সহ) চুপচাপ pass — তারপর সব test pass!।

15. Time complexity

O(log b) — প্রতি iteration-এ b অর্ধেক হয় (b >>= 1), তাই মোটে log₂(b) বার loop ঘোরে। প্রতিবার একটা square + কখনো একটা multiply — সব O(1) (interview-মাপে)। b = 10^18-এও মোটে ~60 ধাপ।

16. Space complexity

O(1) — শুধু result, a, b variable; কোনো list/array/recursion stack লাগছে না। (recursive লিখলে stack O(log b) হতো; iterative-এ O(1)।)

17. Common mistakes

• a %= m ভুলে যাওয়া — base বড় হলে আগে ছোট না করলে গুণফল অযথা বড়; C++-এ overflow।
• b = 0 ভুলে handle করা — loop শুরুই হবে না, result থাকবে 1 — যা সঠিক (a^0 = 1)। কিন্তু ভুল করে result = a শুরু করলে b=0-তে ভুল।
• square আর multiply-এর ক্রম গুলিয়ে ফেলা — আগে multiply (যদি bit 1), তারপর square। উল্টো করলে এক ধাপ এগিয়ে square হয়ে ভুল।
• mod 1 ভুলে যাওয়া — m = 1-এ উত্তর 0 হওয়া উচিত; a %= m থাকায় a হয় 0, তাই ঠিক আসে — কিন্তু result 1 দিয়ে শুরু বলে সাবধান (এখানে b>0 হলে ঠিক; b=0 আর m=1 হলে গণিতে 1%1=0, আমাদের code 1 দেবে — সাধারণত m=1 এ b=0 আসে না, তবু সচেতন থাকো)।
• pow(a, b) লিখে তারপর % m — Python-এ pow(a, b, m) (তিন argument) ব্যবহার করো; নাহলে আগে অতিকায় সংখ্যা বানিয়ে তারপর mod — অর্থহীন slow।
• negative exponent — এই version b ≥ 0 ধরে; negative হলে inverse লাগবে (030-এ দেখবে)।

18. Harder problems that inherit this idea

• CSES — Exponentiation (https://cses.fi/problemset/task/1095) — হুবহু এই problem; বড় b mod 10⁹+7 সহ।
• LeetCode — Pow(x, n) (https://leetcode.com/problems/powx-n/) — float আর negative exponent twist (030-এ এটাই)।
• 032 (Modular Inverse Basic) — Fermat-এ inverse = a^(p-2) mod p, যা সরাসরি এই power-এর প্রয়োগ। আর matrix exponentiation, Fibonacci in O(log n) — সব এই কাঠামোর সম্প্রসারণ।

19. Pattern learned

Binary exponentiation (square-and-multiply) — exponent-কে binary ভাবো; base বারবার square করো (a = a*a % m), bit 1 হলে result-এ গুণো (result = result*a % m), b >>= 1। O(log b)-তে বিশাল power। এটাই Level 2-এর engine।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "a^b % m = square-and-multiply: while b>0 — bit 1 হলে result×=a, সবসময় a=aa, b>>=1; সব mod m। O(log b)। 'বড় exponent দেখলেই binary' — এই signal মনে রাখি; interview-তে হাতে লিখতে চাইবে।"*

পরের ধাপ → 030 — Fast Power (একই engine, negative/float twist সহ)। সম্পর্কিত → 028 — Modular Multiplication, 032 — Modular Inverse Basic।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)

এখানে a * a সহজেই 2^53 ছাড়িয়ে যায় (যেমন mod ~10⁹ হলে গুণফল ~10¹⁸), তাই সাধারণ number-এ নির্ভুলতা হারায় — BigInt দিয়ে লিখি।

// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

// a^b % m — square-and-multiply, BigInt-এ (b >= 0, m > 0)
function powMod(a, b, m) {
  a = BigInt(a); b = BigInt(b); m = BigInt(m);
  let result = 1n;
  a %= m;                          // base আগে ঘড়িতে নামাই
  while (b > 0n) {
    if (b & 1n) result = (result * a) % m;  // last bit 1 → এই power নাও
    a = (a * a) % m;                         // base square
    b >>= 1n;                                // exponent অর্ধেক
  }
  return result;
}

// ---- test cases (file-এর example + edge case) ----
assert(powMod(3, 13, 7) === 3n, "3^13%7");
assert(powMod(2, 10, 1000) === 24n, "1024%1000");
assert(powMod(5, 0, 13) === 1n, "যেকোনো^0=1");
assert(powMod(7, 1, 100) === 7n, "a^1=a");
assert(powMod(10, 5, 1) === 0n, "mod 1 → 0");
// বড় mod-এও নির্ভুল (BigInt বলে overflow নেই)
assert(powMod(2, 1000, 1000000007) === 688423210n, "2^1000 mod 1e9+7");
assert(powMod(123456, 789, 1000000007) === 182677862n, "123456^789 mod 1e9+7");
console.log("সব JS test pass!");

JS টীকা: সাধারণ number-এ a * a % m করলে m বড় হলে (mod ~10⁹) গুণফল ~10¹⁸ > 2^53 — silently ভুল উত্তর। তাই modular exponentiation-এ BigInt (1n, b & 1n, b >>= 1n) লাগে; literal-এ n suffix ভুলো না। (Python বড় int নিজেই সামলায় বলে সেখানে এটা লাগে না।)

22. TypeScript solution (with test cases)

function powMod(aIn: number | bigint, bIn: number | bigint, mIn: number | bigint): bigint {
  let a = BigInt(aIn), b = BigInt(bIn);
  const m = BigInt(mIn);
  let result = 1n;
  a %= m;
  while (b > 0n) {
    if (b & 1n) result = (result * a) % m;
    a = (a * a) % m;
    b >>= 1n;
  }
  return result;
}

function expect(actual: bigint, expected: bigint, msg = ""): void {
  if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}

const cases: ReadonlyArray<readonly [number, number, number, bigint]> = [
  [3, 13, 7, 3n], [2, 10, 1000, 24n], [5, 0, 13, 1n],
  [7, 1, 100, 7n], [10, 5, 1, 0n], [2, 1000, 1000000007, 688423210n],
];
for (const [a, b, m, want] of cases) expect(powMod(a, b, m), want, `${a}^${b}%${m}`);
console.log("সব TS test pass!");

TS টীকা: return type bigint স্পষ্ট করায় ভুলে number-এর সাথে মেশানো (bigint আর number একসাথে * করা TS-এ error) compile-time-এই ধরা পড়ে — modular exponentiation-এ এই type-সীমাই overflow bug ঠেকায়।

23. কোথায় কাজে লাগে (real-world use)

• Public-key cryptography (RSA, Diffie-Hellman): এদের হৃদয়ই a^b mod m বিশাল exponent-এ — square-and-multiply ছাড়া অসম্ভব।
• Hashing (Rabin-Karp, rolling hash): polynomial hash-এ বড় power mod prime দ্রুত বের করা।
• Modular inverse (Fermat): a^(p-2) mod p দিয়ে inverse — modular division, combinatorics (nCr mod p)-তে নিত্য।
• Pseudo-random / fast doubling: matrix exponentiation দিয়ে Fibonacci/linear recurrence O(log n)-এ — একই square-and-multiply কাঠামো। মূল pattern — "exponent-কে binary ভেবে প্রতি step-এ অর্ধেক (O(b) → O(log b))" — fast exponentiation, matrix power, divide-and-conquer জুড়ে বড় ছবিতে ফেরে।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" / "CP-তে নিত্য দরকারি" লেখা।