Problem link ও উৎস
- **Original source:** CP-Algorithms — Primality Tests (Miller-Rabin section)
- **Platform:** CP-Algorithms —
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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-চিন্তা গণিতগতভাবে চমৎকার।
### Input ও output {#6-example-input-and-output}
```text
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।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা সন্দেহভাজনকে (n) জিজ্ঞাসাবাদ করছ — সে সত্যিকারের "prime নাগরিক" না "ছদ্মবেশী composite"। তুমি কয়েকজন সাক্ষী (base a) ডাকো, প্রত্যেকে একটা নির্দিষ্ট প্রশ্ন করে।
- একজন সত্যিকারের prime নাগরিক **প্রতিটা** সাক্ষীর প্রশ্নে সঠিক উত্তর দেবে (গাণিতিক স্বাক্ষর মিলবে)।
- একটা ছদ্মবেশী composite হয়তো দু-একজন সাক্ষীকে বোকা বানাতে পারে — কিন্তু সাক্ষী যত বাড়াবে, ধরা পড়ার সম্ভাবনা তত বাড়ে (প্রতি সাক্ষী composite-এর অন্তত ¾ "মিথ্যা" ধরে ফেলে)।
- আর একটা প্রমাণিত fact: 64-bit-এর মধ্যে কোনো ছদ্মবেশী composite এই **নির্দিষ্ট 12 জন** সাক্ষীর সবাইকে একসাথে বোকা বানাতে পারে না — তাই এই সেটে সবাই পাস করলে n নিশ্চিত prime।
একজন সাক্ষী "মিথ্যা" ধরলেই (witness পেলেই) — তদন্ত শেষ, n composite।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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।
### ভেতরের অঙ্ক {#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 ধরা পড়ে।"
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
"brute force" এখানে হলো 134-এর trial division — reference হিসেবে ছোট n-এ মিলিয়ে দেখতে:
```python
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 বড় হলে অচল:
```text
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-এর গাণিতিক স্বাক্ষর জেরা করো, ভাগ করার দরকার নেই।** ধাপ:
```text
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-এর জুয়া ছাড়াই নিশ্চয়তা।
### ছবিতে বোঝা {#5-visual-explanation}
`miller_rabin(561)` — Carmichael number, যা Fermat-কে ফাঁকি দেয় কিন্তু Miller-Rabin ধরে:
```text
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 ধরে ফেলল।
### ছোট input-এ ধাপে ধাপে {#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-এই ধরা পড়ত — উপরের অংশটা শুধু মূল লুপের গণিত বোঝাতে।)
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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!`।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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` লিখলে বিশাল সংখ্যায় অসম্ভব ধীর।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Counting Primes / প্রচুর বড়-n primality query** (