Skip to content

135 — Miller-Rabin Intro

134-এ দেখলে trial division n = 10¹⁸-এ থেমে যায়; এই note-এ সেই দেয়াল ভাঙব — Miller-Rabin দিয়ে কয়েক microsecond-এ বিশাল সংখ্যার primality। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — Miller-Rabin interview-তে প্রায় আসেই না, কিন্তু CP-তে বড়-সংখ্যা primality-র সোনার কাঠি। 134 (trial division) আর 029 (binary/modular exponentiation) ঝালাই থাকলে এটা বোঝা সহজ। এটা primality trilogy-র দ্বিতীয় ধাপ।

Source

  • Original source: CP-Algorithms — Primality Tests (Miller-Rabin section)
  • Platform: CP-Algorithms — https://cp-algorithms.com/algebra/primality_tests.html
  • Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
  • Difficulty: Hard
  • Pattern: probabilistic test
  • Basic idea inherited from: 134 (Primality Test Advanced), 029 (Binary Exponentiation)

1. Problem in simple words

আগের মতোই — একটা integer n prime কি না বলা। কিন্তু এবার n বিশাল (10¹⁸ পর্যন্ত), যেখানে 134-এর O(√n) trial division (~10⁹ ধাপ) অচল।

Miller-Rabin একটা চটপটে test — কয়েকটা "সাক্ষী" (base) দিয়ে n-কে জেরা করে। মূল মজা:

  • Random base-এ এটা probabilistic — প্রতি জেরায় composite-কে ভুল করে prime বলার সম্ভাবনা ≤ ¼; কয়েকবার জেরা করলে সম্ভাবনা নগণ্য।
  • কিন্তু একটা প্রমাণিত fact: কয়েকটা নির্দিষ্ট base-এ (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) test করলে 64-bit পর্যন্ত (n < 3.3 × 10¹⁸) উত্তর deterministic (নিশ্চিত সঠিক)। তাই CP-তে এই base সেট-ই যথেষ্ট।

মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু "সাক্ষী জেরা করে রায়" — এই probabilistic-চিন্তা গণিতগতভাবে চমৎকার।

2. What is the math idea?

মূল idea Fermat's little theorem-এর ধারালো রূপ। Fermat বলে: p prime হলে a^(p−1) ≡ 1 (mod p)। কিন্তু উল্টোটা সবসময় সত্য নয় — কিছু composite (Carmichael number, যেমন 561) এই test ফাঁকি দেয়।

তাই Miller-Rabin আরও সূক্ষ্ম জেরা করে। n − 1 = 2^s · d লেখো (d বিজোড়)। তারপর দেখো এই ধারা কীভাবে 1-এ পৌঁছায়:

a^d,  a^(2d),  a^(4d),  ...,  a^(2^(s−1)·d)   (mod n)

মূল গণিত: n prime হলে, mod n-এ 1-এর বর্গমূল শুধু ±1। তাই উপরের ধারায় 1-এ পৌঁছানোর ঠিক আগের পদটা n − 1 (অর্থাৎ −1) হতেই হবে, অথবা একদম শুরুতেই a^d ≡ 1। এই দুটোর কোনোটাই না হলে — a হলো witness, n নিশ্চিত composite। এই level CP-leaning হলেও মূল সুর: "prime-এর একটা গাণিতিক স্বাক্ষর আছে; সেটা না মিললে composite ধরা পড়ে।"

3. Which basic idea does this inherit from?

দুটো শিকড়:

  • 134 (Primality Test Advanced) — 134-এর O(√n) সীমা থেকেই Miller-Rabin-এর জন্ম; ছোট prime দিয়ে দ্রুত screening-ও 134-এর trial-division-চিন্তার ধার।
  • 029 (Binary Exponentiation) — Miller-Rabin-এর কেন্দ্রে pow(a, d, n) (modular exponentiation), যা 029-এর fast power। এটা ছাড়া a^d mod n বড় n-এ বের করা যায় না।

আর এর উপরে দাঁড়াবে 136 (Pollard Rho) — factorization-এর আগে n composite নিশ্চিত করতে Miller-Rabin লাগে (prime-এ rho অনন্ত ঘোরে)। README-র recommended order: 134 → 135 → 136।

4. Real-life analogy

ভাবো একটা সন্দেহভাজনকে (n) জিজ্ঞাসাবাদ করছ — সে সত্যিকারের "prime নাগরিক" না "ছদ্মবেশী composite"। তুমি কয়েকজন সাক্ষী (base a) ডাকো, প্রত্যেকে একটা নির্দিষ্ট প্রশ্ন করে।

  • একজন সত্যিকারের prime নাগরিক প্রতিটা সাক্ষীর প্রশ্নে সঠিক উত্তর দেবে (গাণিতিক স্বাক্ষর মিলবে)।
  • একটা ছদ্মবেশী composite হয়তো দু-একজন সাক্ষীকে বোকা বানাতে পারে — কিন্তু সাক্ষী যত বাড়াবে, ধরা পড়ার সম্ভাবনা তত বাড়ে (প্রতি সাক্ষী composite-এর অন্তত ¾ "মিথ্যা" ধরে ফেলে)।
  • আর একটা প্রমাণিত fact: 64-bit-এর মধ্যে কোনো ছদ্মবেশী composite এই নির্দিষ্ট 12 জন সাক্ষীর সবাইকে একসাথে বোকা বানাতে পারে না — তাই এই সেটে সবাই পাস করলে n নিশ্চিত prime।

একজন সাক্ষী "মিথ্যা" ধরলেই (witness পেলেই) — তদন্ত শেষ, n composite।

5. Visual explanation

miller_rabin(561) — Carmichael number, যা Fermat-কে ফাঁকি দেয় কিন্তু Miller-Rabin ধরে:

n = 561 = 3 × 11 × 17  (composite, কিন্তু a^560 ≡ 1 অনেক a-তে — Fermat বোকা হয়)

n − 1 = 560 = 2^4 · 35,  তাই s = 4, d = 35

base a = 2 দিয়ে জেরা:
  x = 2^35 mod 561 = 263
  263 == 1?  না।   263 == 560 (n−1)?  না।
  বর্গ করতে থাকি (s−1 = 3 বার):
    x = 263² mod 561 = 166   (== 560? না)
    x = 166² mod 561 = 67    (== 560? না)
    x = 67²  mod 561 = 1      (== 560? না — কিন্তু 1 হয়ে গেল!)
  পুরো ধারায় −1 (560) এল না, অথচ 1 এসে গেল
  -> 2 হলো WITNESS -> 561 COMPOSITE ✓

তুলনায় prime — miller_rabin(97):
  n−1 = 96 = 2^5 · 3,  s=5, d=3
  a=2:  2^3 mod 97 = 8;  বর্গ: 64, 22, 96(=n−1!) -> এই base পাস
  ... সব base পাস করে -> 97 PRIME

লক্ষ করো — 561-এর জন্য Fermat test (2^560 mod 561) আসলে 1 দেয়, তাই Fermat বোকা হতো; কিন্তু Miller-Rabin মাঝপথে "−1 ছাড়াই 1" দেখে witness ধরে ফেলল।

6. Example input and output

input n        ->  is_prime
----------------------------------------------------------------
   1           ->  False
   2           ->  True
  97           ->  True
 561           ->  False    (Carmichael — Fermat-কে ফাঁকি দেয়, MR ধরে)
1105           ->  False    (আরেকটা Carmichael)
1000000007     ->  True     (CP-র প্রিয় mod)
1000000000000000003 ->  True   (~10¹⁸, trial division অচল, MR মুহূর্তে)
2305843009213693951 ->  True   (Mersenne prime 2⁶¹ − 1)

খেয়াল করো: Carmichael number (561, 1105) — composite যারা Fermat test ফাঁকি দেয়, কিন্তু Miller-Rabin ঠিক ধরে। আর ~10¹⁸ বা Mersenne prime (2⁶¹−1)-এর মতো বিশাল সংখ্যাও Miller-Rabin তাৎক্ষণিক রায় দেয়, যেখানে 134-এর √n অচল। edge case: 1 → False, 2 → True।

7. Brute force thinking

"brute force" এখানে হলো 134-এর trial division — reference হিসেবে ছোট n-এ মিলিয়ে দেখতে:

def is_prime_trial(n):
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

ছোট ও মাঝারি n-এ (10¹² পর্যন্ত) এটা নিখুঁত ও নির্ভরযোগ্য। তাই আমরা Miller-Rabin-এর উত্তর এই trial division-এর সাথে (ছোট range-এ) মিলিয়ে যাচাই করব — দুটো একমত হলে আস্থা বাড়ে।

8. Why brute force may be slow

trial division O(√n) — n বড় হলে অচল:

n = 10¹²:            √n = 10⁶ ভাগ — চলে (সেকেন্ড)
n = 10¹⁸:            √n = 10⁹ ভাগ — TLE (কয়েক সেকেন্ড থেকে মিনিট)
Miller-Rabin:        ~12 base × O(log n) modular গুণ ≈ কয়েকশো operation — microsecond

n = 10¹⁸-এ √n = 10⁹ — একটা প্রশ্নেই TLE, আর CP-তে প্রায়ই হাজার হাজার এমন query। Miller-Rabin প্রতিটা n-এ মাত্র ~12টা base × log n modular exponentiation — তাই বিশাল n-এও তাৎক্ষণিক। এটাই O(√n) → O(log³ n)-জাতীয় লাফ।

9. Better thinking

মূল insight — prime-এর গাণিতিক স্বাক্ষর জেরা করো, ভাগ করার দরকার নেই। ধাপ:

1. ছোট prime (2..37) দিয়ে দ্রুত screen: n সেগুলোর একটা হলে True, ভাগ গেলে False
2. n − 1 = 2^s · d লেখো (d বিজোড় হওয়া পর্যন্ত 2 দিয়ে ভাগ)
3. প্রতিটা base a (নির্দিষ্ট সেট) জন্য:
     x = pow(a, d, n)                  [029-এর fast modular power]
     যদি x == 1 বা x == n−1:  এই base পাস (continue)
     নাহলে s−1 বার বর্গ করো:
        x = x² mod n
        যদি x == n−1:  এই base পাস (break)
     যদি কখনো n−1 না আসে:  a witness -> return False (composite)
4. সব base পাস -> return True (prime)

কেন নির্দিষ্ট base: গণিতবিদরা প্রমাণ করেছেন {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}-এ test করলে n < 3.3 × 10¹⁸ পর্যন্ত কোনো ভুল হয় না (deterministic)। তাই random-এর ঝুঁকি ছাড়াই 64-bit-এ নিশ্চিত উত্তর। মূল ভারী কাজ pow(a, d, n) — O(log n)।

10. Thinking tweak

আসল "আহা" মুহূর্ত: prime modulus-এ 1-এর বর্গমূল শুধু ±1 — তাই a^d থেকে বর্গ করতে করতে 1-এ পৌঁছানোর আগে অবশ্যই −1 আসতে হবে; না এলে composite ধরা।

trial division সব ভাজক খুঁজছিল; tweak হলো — ভাগ বাদ, বরং Fermat-এর a^(n−1) ≡ 1-কে আরও সূক্ষ্ম করে "1-এর আগে −1 আসছে কি না" দেখো। এটা Carmichael-দেরও ধরে ফেলে (যাদের সাধারণ Fermat ফাঁকি দিত)। আর দ্বিতীয় tweak: নির্দিষ্ট base সেট নিলে probabilistic test 64-bit-এ deterministic হয়ে যায় — random-এর জুয়া ছাড়াই নিশ্চয়তা।

11. Step-by-step dry run

miller_rabin(221) — 221 = 13 × 17 (composite):

step কী করছি মান
1 ছোট prime screen: 221 কি 2..37-এর কোনোটা? ভাগ যায়? না (13, 17 > আমরা শুধু ≤37 prime দিয়ে ভাগ দেখি; 13 ভাগ করে!)

দাঁড়াও — 221 % 13 == 0, আর 13 আমাদের screening prime সেটে আছে। তাই screening ধাপেই composite ধরা পড়ে (return False)। পরিষ্কার উদাহরণের জন্য বরং n = 25 নিই (25 = 5², কিন্তু 5 screening-এ ধরা পড়বে)...

ঠিক আছে, screening বাইপাস করে মূল Miller-Rabin লুপ দেখতে n = 561-এ base a = 2 (এর factor 3, 11, 17 সব ≤ 37 screening-এ ধরা পড়বে আসলে — তাই বাস্তবে screening-ই ধরে)। মূল লুপের গণিত বোঝাতে তাই screening ছাড়া শুধু base-জেরা দেখি, n = 561, a = 2:

step কী করছি মান
1 n−1 = 560 = 2⁴·35 → s = 4, d = 35 s=4, d=35
2 x = pow(2, 35, 561) 263
3 x == 1? না। x == 560? না চলো বর্গে
4 বর্গ 1: x = 263² % 561 = 166; == 560? না 166
5 বর্গ 2: x = 166² % 561 = 67; == 560? না 67
6 বর্গ 3: x = 67² % 561 = 1; == 560? না 1
7 s−1 = 3 বার বর্গ শেষ, কখনো 560 আসেনি a=2 witness
8 return False 561 COMPOSITE ✓

চূড়ান্ত: False। লক্ষ করো — ধারায় (263 → 166 → 67 → 1) কখনো −1 (560) এল না, অথচ 1 এসে গেল; এটাই composite-এর প্রমাণ (witness 2)। (বাস্তব কোডে অবশ্য 561-এর factor 3 screening-এই ধরা পড়ত — উপরের অংশটা শুধু মূল লুপের গণিত বোঝাতে।)

12. Python solution

def miller_rabin(n):
    """Deterministic Miller-Rabin — n < 3.3×10¹⁸ (64-bit) পর্যন্ত নিশ্চিত সঠিক।"""
    if n < 2:
        return False
    # ছোট prime দিয়ে দ্রুত screen
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for p in small_primes:
        if n % p == 0:
            return n == p
    # n − 1 = 2^s · d  (d বিজোড়)
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    # নির্দিষ্ট base — এই সেটে 64-bit পর্যন্ত deterministic
    for a in small_primes:
        x = pow(a, d, n)                  # 029-এর fast modular power
        if x == 1 or x == n - 1:
            continue                      # এই base পাস
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False                  # a witness -> composite
    return True


# --- ছোট test গুলো (সব pass করা উচিত) ---
def is_prime_trial(n):
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

# Miller-Rabin বনাম trial division — 0..5000 সব মেলাও
for n in range(0, 5001):
    assert miller_rabin(n) == is_prime_trial(n), f"MR({n}) অমিল"

# Carmichael numbers: composite, Fermat-কে ফাঁকি দেয় — MR ধরবে
for c in [561, 1105, 1729, 2465, 2821, 6601, 8911]:
    assert miller_rabin(c) is False, f"Carmichael {c} ভুল"

# জানা বড় prime
assert miller_rabin(1000000007) is True
assert miller_rabin(1000000009) is True
assert miller_rabin(999999937) is True          # 10⁹-এর নিচে বড় prime

# বিশাল সংখ্যা — trial division অচল, MR তাৎক্ষণিক
assert miller_rabin(1000000000000000003) is True       # ~10¹⁸ prime
assert miller_rabin(2305843009213693951) is True       # Mersenne 2⁶¹ − 1, prime
assert miller_rabin(1000000000000000000) is False      # 10¹⁸ = 2^18·5^18, composite
assert miller_rabin(9223372036854775783) is True       # 64-bit-এর কাছাকাছি বড় prime

# trial division-এর সাথে কিছু বড় composite-ও মেলাও
assert miller_rabin(1000003 * 1000033) is False        # দুই prime-এর গুণফল

print(miller_rabin(97))                  # True
print(miller_rabin(561))                 # False (Carmichael)
print(miller_rabin(1000000000000000003)) # True (~10¹⁸)
print("সব test pass!")

13. Line-by-line explanation

    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for p in small_primes:
        if n % p == 0:
            return n == p

দ্রুত screening — n যদি এই ছোট prime-গুলোর গুণিতক হয়, তবে n composite (যদি না n নিজেই সেই prime)। এটা ছোট composite দ্রুত ফেলে দেয়, আর n = এই prime-গুলো হলে সরাসরি True।

    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1

n − 1 = 2^s · d decompose — d বিজোড় না হওয়া পর্যন্ত 2 দিয়ে ভাগ, প্রতিবার s বাড়াই। এই s আর d-ই Miller-Rabin-এর ধারার ভিত্তি।

    for a in small_primes:
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue

প্রতিটা base a-এর জন্য a^d mod n (fast power)। শুরুতেই 1 বা n−1 (−1) এলে এই base prime-এর সাথে সঙ্গতিপূর্ণ — পরের base-এ যাই।

        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False

নাহলে s−1 বার বর্গ করি; কোথাও n−1 (−1) এলে এই base পাস (break, else চলে না)। কিন্তু পুরো লুপে n−1 না এলে (for-else-এর else চলে) — a হলো witness, n composite।

    return True

সব base পাস করলে n prime (64-bit-এ deterministic)।

বাকি test অংশে Miller-Rabin বনাম trial division (0..5000), Carmichael সেট (561, 1105, ...), জানা বড় prime, আর ~10¹⁸/Mersenne/64-bit-কাছাকাছি বিশাল সংখ্যা সব যাচাই হয়। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough

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

True
False
True
সব test pass!

miller_rabin(97) → True (prime, সব base পাস)। miller_rabin(561) → False (Carmichael — Fermat ফাঁকি দিত, কিন্তু এখানে factor 3 screening-এ ধরা)। miller_rabin(1000000000000000003) → True (~10¹⁸ prime, তাৎক্ষণিক — trial division হলে 10⁹ ভাগ লাগত)। তার আগে 0..5000 trial-এর সাথে মিল, সব Carmichael ও বিশাল সংখ্যা pass — তাই সব test pass!।

15. Time complexity

O(k · log³ n) মোটামুটি — যেখানে k = base সংখ্যা (এখানে 12, ধ্রুবক)। প্রতিটা base-এ একটা pow(a, d, n) (O(log n) modular গুণ), আর প্রতিটা modular গুণ বড় সংখ্যায় ~O(log² n)। তাই কার্যত n-এর bit-সংখ্যার polynomial — n = 10¹⁸-এও কয়েকশো operation, microsecond। trial division-এর O(√n)-এর তুলনায় বিশাল লাফ।

16. Space complexity

O(1) — base array ধ্রুব আকারের (12টা), আর গুটিকয় variable (d, s, x)। কোনো n-নির্ভর array নেই। pow-ও in-place modular exponentiation, extra space নগণ্য। তাই বিশাল n-এও memory ধ্রুব।

17. Common mistakes

  1. n − 1 = 2^s · d decompose-এ off-by-one — d বিজোড় না হওয়া পর্যন্ত 2 দিয়ে ভাগ; s ভুল গুনলে ভুল রায়। যাচাই: শেষে 2^s · d == n − 1 হওয়া উচিত।
  2. for-else ভুল বোঝা — ভেতরের for ... else মানে "লুপ break ছাড়া শেষ হলে else চলে"; এখানে n−1 না এলে witness। else-কে if-এর সাথে গুলিয়ে ফেলো না।
  3. base-এ n নিজেই থাকলে — n ছোট prime (যেমন 3) হলে screening-এ n == p-তে True; না সামলালে base a = n হয়ে pow(n, d, n) == 0, ভুল। screening আগে রাখলে নিরাপদ।
  4. ভুল base সেট/range — {2,...,37} শুধু n < 3.3×10¹⁸-এ deterministic; এর বেশি বড় n-এ আরও base বা random লাগবে।
  5. pow(a, d, n)-এর বদলে নিজে ধীর exponentiation — Python-এর built-in pow(a, d, n) fast modular power; loop-এ a**d % n লিখলে বিশাল সংখ্যায় অসম্ভব ধীর।

18. Harder problems that inherit this idea

  • CSES — Counting Primes / প্রচুর বড়-n primality query (https://cses.fi/problemset/) — যেখানে trial division অচল।
  • Codeforces — বড় n factorization/primality problems (https://codeforces.com/problemset) — Miller-Rabin দিয়ে n prime কি না, তারপর Pollard rho দিয়ে factor।
  • 136 (Pollard Rho Intro) — এই repo-রই পরের ধাপ; rho চালানোর আগে Miller-Rabin দিয়ে composite নিশ্চিত করতে হয়। ভিত্তি 134, 029।

19. Pattern learned

Probabilistic primality via Miller-Rabin — n−1 = 2^s·d, প্রতিটা base a-তে a^d, a^(2d), ... ধারায় "1-এর আগে −1" খোঁজো; না পেলে composite। নির্দিষ্ট 12 base-এ 64-bit deterministic। বড় শিক্ষা: বড় n-এ "ভাগ করে খোঁজা" বাদ দিয়ে prime-এর গাণিতিক স্বাক্ষর (square-root of unity) যাচাই করো — তখন O(√n) থেকে O(log³ n)-এ নামা যায়।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Miller-Rabin: n−1 = 2^s·d; base a-তে x = a^d, বর্গ করতে করতে n−1 খোঁজো; না পেলে witness → composite; base {2..37}-এ n < 3.3e18 deterministic; ভারী কাজ pow(a,d,n)।" Signal: "বিশাল n prime কি না" বা "বড় n factorize-এর আগে primality" — দেখলেই Miller-Rabin মনে পড়বে।

পরের ধাপ → 136 — Pollard Rho Intro (বড় composite-এর factor শিকার)। ভিত্তি → 134 — Primality Test Advanced, 029 (Binary Exponentiation)।

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

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