Combinatorics — গোনার শিল্প

আগে এটা বুঝি

“এই password কতটা শক্তিশালী?”

উত্তর দিতে হলে গুনতে হবে: কতগুলো সম্ভাব্য password আছে?

“এই algorithm কি চলবে?”

উত্তর দিতে হলে গুনতে হবে: কতগুলো সম্ভাবনা পরীক্ষা করতে হবে?

“এই bug কি reproduce করা যাবে?”

উত্তর দিতে হলে গুনতে হবে: কতগুলো thread interleaving সম্ভব?

Combinatorics হলো গোনার নিয়মতান্ত্রিক পদ্ধতি — আর computer science-এ প্রায় প্রতিটা “কি সম্ভব?” প্রশ্নের নিচে একটা গণনার প্রশ্ন লুকিয়ে আছে।

আর সবচেয়ে গুরুত্বপূর্ণ পাঠটা হলো: সংখ্যাগুলো কত দ্রুত বাড়ে। মানুষের অন্তর্জ্ঞান exponential বৃদ্ধি ধরতে পারে না, আর সেই ব্যর্থতাই নিরাপত্তা ভুল আর performance বিপর্যয়ের উৎস।

মূল ধারণা

দুইটা মৌলিক নিয়ম

সবকিছু এই দুইটা থেকে আসে।

Sum rule — “অথবা”

দুইটা পরস্পর-বিচ্ছিন্ন পছন্দের মধ্যে একটা:

$|A \cup B| = |A| + |B| \qquad \text{যখন } A \cap B = \emptyset$

৩টা চা আর ৫টা কফি আছে। একটা পানীয় বেছে নেওয়ার উপায়: 3 + 5 = 8

বিচ্ছিন্ন না হলে inclusion–exclusion লাগে (গত লেসনে দেখেছি)।

Product rule — “এবং”

পরপর স্বাধীন পছন্দ:

$|A \times B| = |A| \cdot |B|$

৩টা শার্ট আর ৪টা প্যান্ট। পোশাকের সমন্বয়: 3 × 4 = 12

Product rule-ই combinatorics-এর ইঞ্জিন। প্রায় প্রতিটা জটিল গণনা শেষ পর্যন্ত এটার পুনরাবৃত্তি।

কোডে এটা nested loop

# sum rule — পরপর
for x in A: ...        # |A| বার
for y in B: ...        # |B| বার        মোট |A| + |B|

# product rule — nested
for x in A:
    for y in B: ...    # মোট |A| × |B| বার

এই কারণেই nested loop-এর complexity গুণ হয় আর পরপর loop-এর যোগ। Complexity analysis আসলে combinatorics-এর প্রয়োগ।

চারটা মৌলিক গণনা

n টা জিনিস থেকে k টা বাছার চারটা ভিন্ন প্রশ্ন:

	ক্রম গুরুত্বপূর্ণ	ক্রম গুরুত্বপূর্ণ নয়
পুনরাবৃত্তি হয়	`n^k`	`C(n+k−1, k)`
পুনরাবৃত্তি হয় না	`P(n,k) = n!/(n−k)!`	`C(n,k) = n!/(k!(n−k)!)`

ক্রম গুরুত্বপূর্ণ কি না, আর পুনরাবৃত্তি অনুমোদিত কি না — এই দুই প্রশ্নই চারটা সূত্র নির্ধারণ করে।

১. পুনরাবৃত্তি সহ, ক্রম সহ — `n^k`

প্রতিটা position-এ n টা পছন্দ, k টা position:

$\underbrace{n \times n \times \cdots \times n}_{k \text{ বার}} = n^k$

উদাহরণ: ৪-অঙ্কের PIN। প্রতিটা অঙ্কে ১০টা পছন্দ: 10⁴ = 10,000

CS-এ: k bit-এর সম্ভাব্য মান 2^k। k অক্ষরের password alphabet n-এ n^k।

২. পুনরাবৃত্তি ছাড়া, ক্রম সহ — Permutation

প্রথম position-এ n টা পছন্দ, দ্বিতীয়তে n−1, …

$P(n,k) = n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!}$

উদাহরণ: ১০ জন থেকে সভাপতি, সম্পাদক, কোষাধ্যক্ষ বাছা: P(10,3) = 10 × 9 × 8 = 720

k = n হলে P(n,n) = n! — পুরো সাজানোর সংখ্যা।

৩. পুনরাবৃত্তি ছাড়া, ক্রম ছাড়া — Combination

Permutation থেকে শুরু করুন, তারপর ক্রমের পুনরাবৃত্তি ভাগ করে দিন:

$C(n,k) = \binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{k!\,(n-k)!}$

উদাহরণ: ১০ জন থেকে ৩ জনের কমিটি: C(10,3) = 720 / 6 = 120

Permutation-এর ৭২০ থেকে ভাগ করে ১২০ — কারণ একই ৩ জনকে ৬ ভাবে সাজানো যায়, কিন্তু কমিটি হিসেবে সেগুলো একই।

৪. পুনরাবৃত্তি সহ, ক্রম ছাড়া — Multiset

$\binom{n+k-1}{k}$

“Stars and bars” যুক্তি: k টা তারা (★) আর n−1 টা দাগ (|) সাজানো। দাগগুলো তারাদের n ভাগে ভাগ করে।

n = 3 ধরনের ফল, k = 5 টা কিনব

★★ | ★ | ★★     →  2 আপেল, 1 কলা, 2 আম
★★★★★ | |       →  5 আপেল, 0 কলা, 0 আম

মোট k + (n−1) টা প্রতীক, তার মধ্যে k টা তারার position বাছা: C(5+2, 5) = C(7,5) = 21

কোনটা ব্যবহার করবেন — দুইটা প্রশ্ন

১. ক্রম বদলালে কি ভিন্ন উত্তর?

হ্যাঁ → permutation ধরনের
না → combination ধরনের

২. একই জিনিস দুইবার নেওয়া যায়?

হ্যাঁ → পুনরাবৃত্তি সহ
না → পুনরাবৃত্তি ছাড়া

উদাহরণ:

Password → ক্রম হ্যাঁ, পুনরাবৃত্তি হ্যাঁ → n^k
Lottery নম্বর → ক্রম না, পুনরাবৃত্তি না → C(n,k)
Race-এ প্রথম তিন → ক্রম হ্যাঁ, পুনরাবৃত্তি না → P(n,3)
Ice cream scoop → ক্রম না, পুনরাবৃত্তি হ্যাঁ → multiset

Binomial coefficient-এর ধর্ম

C(n,k) এত ঘন ঘন আসে যে এর ধর্মগুলো জানা থাকা দরকার।

Pascal’s identity

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

যুক্তি: একটা নির্দিষ্ট element বেছে নিন। হয় সেটা আপনার subset-এ আছে (তখন বাকি n−1 থেকে k−1 বাছতে হবে), নয় নেই (তখন বাকি n−1 থেকে k বাছতে হবে)।

এটাই Pascal’s triangle:

n=0:            1
n=1:          1   1
n=2:        1   2   1
n=3:      1   3   3   1
n=4:    1   4   6   4   1
n=5:  1   5  10  10   5   1

আর এটাই dynamic programming-এর সবচেয়ে সরল উদাহরণ — Level 6-এ আমরা এই recurrence-টা memoize করব।

Symmetry

$\binom{n}{k} = \binom{n}{n-k}$

যুক্তি: k টা বাছা আর n−k টা বাদ দেওয়া একই কাজ।

ব্যবহারিক: C(100, 98) হিসাব করতে C(100, 2) = 4950 করুন — অনেক কম গুণ।

Binomial theorem

$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$

x = y = 1 বসালে:

$\sum_{k=0}^{n} \binom{n}{k} = 2^n$

অর্থাৎ সব আকারের subset মিলে মোট 2ⁿ — যা আমরা induction-এর লেসনে প্রমাণ করেছি। দুইটা সম্পূর্ণ ভিন্ন পথে একই উত্তর।

Combinatorial explosion

এটাই combinatorics-এর সবচেয়ে গুরুত্বপূর্ণ ব্যবহারিক পাঠ।

`n`	`n²`	`n³`	`2ⁿ`	`n!`
5	25	125	32	120
10	100	1,000	1,024	3.6 × 10⁶
20	400	8,000	10⁶	2.4 × 10¹⁸
30	900	27,000	10⁹	2.7 × 10³²
50	2,500	125,000	10¹⁵	3 × 10⁶⁴
100	10,000	10⁶	10³⁰	9 × 10¹⁵⁷

সেকেন্ডে ১ বিলিয়ন (10⁹) operation ধরে নিলে:

Algorithm	`n = 20`	`n = 50`	`n = 100`
`n²`	তাৎক্ষণিক	তাৎক্ষণিক	তাৎক্ষণিক
`2ⁿ`	১ ms	১৩ দিন	10¹³ বছর
`n!`	৭৭ বছর	10⁴৮ বছর	—

ভেতরে কী ঘটছে

Password strength — combinatorics-এর সরাসরি প্রয়োগ

k অক্ষরের password, alphabet-এ n টা অক্ষর:

$\text{সম্ভাব্য password} = n^k$

Entropy (bit-এ):

$H = \log_2(n^k) = k \log_2 n$

Alphabet	`n`	প্রতি অক্ষরে bit
শুধু অঙ্ক	10	3.32
Lowercase	26	4.70
Lower + upper	52	5.70
Alphanumeric	62	5.95
+ সাধারণ চিহ্ন	95	6.57

একটা তুলনা:

"Tr0ub4dor&3"      — ১১ অক্ষর, ৯৫-অক্ষর alphabet
                      H = 11 × 6.57 ≈ 72 bit  (তাত্ত্বিকভাবে)

"correct horse battery staple"
                    — ৪টা শব্দ, ২০০০-শব্দের অভিধান থেকে random
                      H = 4 × log₂(2000) ≈ 44 bit

প্রথমটার entropy বেশি মনে হচ্ছে। কিন্তু এটা ভুল হিসাব।

Entropy হিসাব করতে হয় জেনারেশন প্রক্রিয়ার উপর, ফলাফলের উপর নয়

Tr0ub4dor&3 random নয় — এটা “troubadour” শব্দটাকে পূর্বানুমেয় নিয়মে বদলানো:

একটা সাধারণ শব্দ বাছা (~২০০০ পছন্দ)
প্রথম অক্ষর বড় হাতের (~২ পছন্দ)
o → 0, a → 4 (~কয়েকটা পছন্দ)
শেষে একটা চিহ্ন + অঙ্ক (~১০০ পছন্দ)

আসল entropy প্রায় 28 bit — 2²⁸ ≈ 2.7 × 10⁸, যা একটা GPU সেকেন্ডে ভেঙে ফেলে।

Attacker সব 95¹¹ combination চেষ্টা করে না। সে মানুষ যেভাবে password বানায় সেই pattern চেষ্টা করে। এটাই dictionary attack আর rule-based cracking (hashcat-এর rule file)।

XKCD 936-এর মূল বক্তব্য এটাই — আর গণিতটা সঠিক।

Cracking-এর সময় হিসাব:

আধুনিক GPU দিয়ে (RTX 4090 শ্রেণির), hash অনুযায়ী গতি:

Hash	অনুমান/সেকেন্ড
MD5	~10¹¹
SHA-256	~10¹⁰
bcrypt (cost 12)	~10⁴
argon2id (ভালো params)	~10³

44 bit entropy = 1.8 × 10¹³ সম্ভাবনা:

Hash	গড় সময় (অর্ধেক space)
MD5	~৯০ সেকেন্ড
SHA-256	~১৫ মিনিট
bcrypt	~২৯ বছর
argon2id	~২৯০ বছর

পাঠ: password entropy যত গুরুত্বপূর্ণ, hash function-এর ধীরগতি তত গুরুত্বপূর্ণ। এই কারণেই password কখনো MD5 বা SHA-256 দিয়ে hash করা হয় না — সেগুলো দ্রুত হওয়ার জন্য ডিজাইন করা, আর এখানে দ্রুত মানে দুর্বল।

Level 10-এ আমরা password hashing বিস্তারিত দেখব।

Concurrency — interleaving গোনা

দুইটা thread, প্রতিটায় n টা atomic operation। কতগুলো সম্ভাব্য interleaving?

$\binom{2n}{n}$

যুক্তি: মোট 2n টা slot, তার মধ্যে n টা বেছে নিন thread A-র জন্য; বাকিগুলো B-র।

`n`	interleaving
2	6
5	252
10	184,756
20	1.4 × 10¹¹

তিনটা thread হলে multinomial:

$\frac{(3n)!}{(n!)^3}$

n = 10, ৩ thread → 5.6 × 10¹²

এই কারণেই race condition ধরা এত কঠিন

১০টা operation-এর দুইটা thread — ১,৮৪,৭৫৬টা সম্ভাব্য ক্রম। তার মধ্যে হয়তো ৩টায় bug প্রকাশ পায়।

Test চালালে OS scheduler সাধারণত একই কয়েকটা interleaving বেছে নেয় — তাই bug কখনো দেখা যায় না। তারপর production-এ ভিন্ন load-এ সেই ৩টার একটা ঘটে।

“Works on my machine” -এর গাণিতিক ব্যাখ্যা এটাই।

সমাধান তিনটা:

Systematic exploration — যেমন CHESS, model checking (সব interleaving চেষ্টা, ছোট প্রোগ্রামে)
Race detector — ThreadSanitizer, যা happens-before সম্পর্ক track করে; একটা execution দেখেই সম্ভাব্য race ধরে
Design দিয়ে এড়ানো — shared mutable state না রাখা

Level 4-এ আমরা এই তিনটাই দেখব।

State space explosion

একটা distributed system-এ p টা process, প্রতিটার s টা state:

$\text{মোট state} = s^p$

৫টা process, প্রতিটার ১০টা state → 10⁵ = 100,000 ১০টা process → 10¹⁰

আর message-in-flight যোগ করলে সংখ্যাটা আরো বিস্ফোরিত হয়।

এই কারণেই model checker (TLA+, SPIN) ছোট configuration-এ চালানো হয় — ৩টা node, ২টা message। যুক্তি: বেশিরভাগ protocol bug ছোট configuration-এই প্রকাশ পায় (“small scope hypothesis”)।

Level 9-এ আমরা TLA+ দিয়ে একটা protocol verify করব।

Combinatorial explosion যেখানে যেখানে সীমা টানে

Password space n^kকত দ্রুত ভাঙা যাবে
Key space 2^128brute force অসম্ভব করে
Thread interleaving C(2n,n)race condition ধরা কঠিন
Test case spaceexhaustive testing অসম্ভব
Model checker state s^pছোট scope-এ চালাতে হয়
SAT/NP-complete 2^nতাত্ত্বিক কঠিনতার উৎস
Chess/Go game treeকেন heuristic লাগে, exhaustive নয়

উদাহরণ

Birthday problem — আশ্চর্যজনক ফল

একটা ঘরে কতজন থাকলে দুইজনের জন্মদিন মেলার সম্ভাবনা ৫০% ছাড়ায়?

অন্তর্জ্ঞান বলে ~১৮০ (৩৬৫-এর অর্ধেক)। সঠিক উত্তর ২৩।

হিসাব — উল্টোটা গোনা সহজ।

k জনের কারো জন্মদিন না মেলার সম্ভাবনা:

$P(\text{সবাই আলাদা}) = \frac{365}{365} \times \frac{364}{365} \times \cdots \times \frac{365-k+1}{365}$

$= \frac{P(365, k)}{365^k}$

`k`	কেউ মেলে না	অন্তত দুইজন মেলে
10	88.3%	11.7%
20	58.9%	41.1%
23	49.3%	50.7%
30	29.4%	70.6%
50	3.0%	97.0%
70	0.08%	99.9%

কেন এত কম: আপনি ব্যক্তি গুনছেন না, জোড়া গুনছেন। ২৩ জনের জোড়া সংখ্যা C(23,2) = 253 — আর ২৫৩টা সুযোগে 1/365 সম্ভাবনা অনেকবার।

Hash collision-এ এটাই ফিরে আসে

N টা সম্ভাব্য hash মান থাকলে, প্রায় √N টা input-এর পরেই ৫০% সম্ভাবনায় collision:

$k \approx 1.177 \sqrt{N}$

Hash আকার	`N`	৫০% collision-এর জন্য
16 bit	65,536	~301
32 bit	4.3 × 10⁹	~77,000
64 bit	1.8 × 10¹⁹	~5.1 × 10⁹
128 bit	3.4 × 10³⁸	~2.2 × 10¹⁹
256 bit	1.2 × 10⁷⁷	~4 × 10³⁸

৩২-bit hash কখনো unique id হিসেবে নয়

৭৭ হাজার item-এই ৫০% collision। একটা মাঝারি ওয়েবসাইটের একদিনের session সংখ্যাই এর চেয়ে বেশি।

আর এই কারণেই cryptographic hash-এর নিরাপত্তা তার আকারের অর্ধেক। SHA-256-এর collision resistance ১২৮ bit, ২৫৬ নয় — কারণ birthday attack।

Git SHA-1 (১৬০ bit) ব্যবহার করত, অর্থাৎ ৮০-bit collision resistance। ২০১৭-তে Google দেখাল সেটা ব্যবহারিকভাবে ভাঙা যায় (SHAttered)। তাই Git SHA-256-এ সরছে।

Counting arguments in algorithms

কেন comparison sort `Ω(n log n)`

n টা element-এর সম্ভাব্য বিন্যাস: n!

একটা comparison-ভিত্তিক algorithm-কে একটা decision tree হিসেবে ভাবুন — প্রতিটা internal node একটা তুলনা (দুইটা শাখা), প্রতিটা leaf একটা সম্ভাব্য output বিন্যাস।

n! টা ভিন্ন output দিতে হলে অন্তত n! টা leaf লাগবে।

গত লেসনে আমরা প্রমাণ করেছি: L টা leaf-এর binary tree-র height অন্তত log₂ L।

$\text{height} \ge \log_2(n!) = \Theta(n \log n)$

শেষ সমতাটা Stirling’s approximation থেকে:

$n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \implies \log_2(n!) \approx n\log_2 n - 1.44n$

Height মানে worst-case তুলনার সংখ্যা। তাই কোনো comparison sort n log n-এর চেয়ে ভালো হতে পারে না। ∎

এটা একটা lower bound proof — শুধু গোনা দিয়ে।

নিজে চালিয়ে দেখুন

EXPERIMENT

Birthday paradox simulate করুন

Python 3· ১০ মিনিট

import random, math
from collections import Counter

def simulate(space, k, trials=20000):
    """k টা random মান space থেকে নিলে collision হওয়ার অনুপাত"""
    hits = 0
    for _ in range(trials):
        seen = set()
        for _ in range(k):
            v = random.randrange(space)
            if v in seen:
                hits += 1
                break
            seen.add(v)
    return hits / trials

def theoretical(space, k):
    """P(অন্তত একটা collision) — উল্টোটা হিসাব করে"""
    p_none = 1.0
    for i in range(k):
        p_none *= (space - i) / space
    return 1 - p_none

print("── জন্মদিন (space = 365) " + "─" * 28)
print(f"{'k':>4} {'simulate':>10} {'theory':>10}")
for k in [10, 20, 23, 30, 50]:
    print(f"{k:>4} {simulate(365, k):>10.3f} {theoretical(365, k):>10.3f}")

print("\n── বিভিন্ন hash আকারে ৫০% collision " + "─" * 15)
print(f"{'bits':>6} {'space':>16} {'√N নিয়ম':>12} {'নির্ভুল':>10}")
for bits in [8, 12, 16, 20, 24]:
    space = 2 ** bits
    approx = 1.177 * math.sqrt(space)
    # binary search করে নির্ভুল k বের করুন
    lo, hi = 1, space
    while lo \< hi:
        mid = (lo + hi) // 2
        if theoretical(space, mid) >= 0.5: hi = mid
        else: lo = mid + 1
    print(f"{bits:>6} {space:>16,} {approx:>12.0f} {lo:>10,}")

Output:

── জন্মদিন (space = 365) ────────────────────────────
   k   simulate     theory
  10      0.117      0.117
  20      0.410      0.411
  23      0.505      0.507
  30      0.708      0.706
  50      0.971      0.970

── বিভিন্ন hash আকারে ৫০% collision ───────────────
  bits            space      √N নিয়ম     নির্ভুল
     8              256           19          20
    12            4,096           75          76
    16           65,536          301         302
    20        1,048,576        1,205       1,205
    24       16,777,216        4,822       4,823

Simulation তত্ত্বের সাথে মেলে, আর 1.177√N আনুমানিক সূত্রটা প্রায় নিখুঁত।

এবার বাস্তব hash দিয়ে যাচাই করুন:

import hashlib

def find_collision(bits):
    """ছোট করে কাটা SHA-256-এ প্রথম collision কতগুলো input পরে"""
    seen = {}
    i = 0
    mask = (1 \<\< bits) - 1
    while True:
        h = int.from_bytes(hashlib.sha256(str(i).encode()).digest()[:8], 'big') & mask
        if h in seen:
            return i + 1, seen[h], i
        seen[h] = i
        i += 1

for bits in [16, 20, 24]:
    n, a, b = find_collision(bits)
    expected = 1.177 * math.sqrt(2 ** bits)
    print(f"{bits} bit: {n:,} input-এ collision  "
          f"(আশা করেছিলাম ~{expected:.0f})   "
          f"'{a}' আর '{b}' একই hash")

আসল SHA-256-এর কাটা রূপেও একই আচরণ — কারণ ভালো hash-এর output কার্যত uniform random।

এটা কী প্রমাণ করে

Collision তত্ত্বের সংখ্যাগুলো বাস্তবে মিলে যায় — আর √N নিয়মটা যেকোনো hash আকারে খাটে, শুধু জন্মদিনে নয়।

EXPERIMENT

Password entropy বনাম বাস্তব crack time

Python 3· ১৫ মিনিট

import math, itertools, hashlib, time

CHARSETS = {
    "digits":       "0123456789",
    "lowercase":    "abcdefghijklmnopqrstuvwxyz",
    "alphanumeric": "abcdefghijklmnopqrstuvwxyz0123456789",
    "full":         "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*",
}

RATES = {                      # অনুমান/সেকেন্ড, আধুনিক GPU
    "MD5":       1e11,
    "SHA-256":   1e10,
    "bcrypt-12": 1e4,
    "argon2id":  1e3,
}

def entropy(charset, length):
    return length * math.log2(len(charset))

def humanize(seconds):
    for unit, n in [("সেকেন্ড",1), ("মিনিট",60), ("ঘণ্টা",3600),
                    ("দিন",86400), ("বছর",31_536_000)]:
        if seconds \< n * 1000:
            return f"{seconds/n:.1f} {unit}"
    y = seconds / 31_536_000
    if y > 1e12: return f"{y:.1e} বছর"
    return f"{y:,.0f} বছর"

print(f"{'charset':>14} {'len':>4} {'entropy':>9}   " +
      "  ".join(f"{h:>12}" for h in RATES))
for name, cs in CHARSETS.items():
    for length in (8, 12, 16):
        H = entropy(cs, length)
        row = f"{name:>14} {length:>4} {H:>7.1f}b   "
        for h, rate in RATES.items():
            secs = (2 ** H) / 2 / rate         # গড়ে অর্ধেক space
            row += f"{humanize(secs):>12}  "
        print(row)

এবার dictionary attack-এর হিসাব:

print("\n── বাস্তব pattern-এর entropy ─────────────────────")

patterns = [
    ("Tr0ub4dor&3", "শব্দ + leetspeak + চিহ্ন",
     math.log2(2000) + math.log2(2) + 3*math.log2(3) + math.log2(100)),
    ("correct horse battery staple", "৪টা random শব্দ (২০০০-শব্দ অভিধান)",
     4 * math.log2(2000)),
    ("Password123!", "সবচেয়ে সাধারণ pattern",
     math.log2(1000)),
    ("xK9#mQ2vL@8p", "সত্যিকার random, ১২ অক্ষর, ৭০-charset",
     12 * math.log2(70)),
]

for pw, desc, H in patterns:
    secs_md5 = (2 ** H) / 2 / 1e11
    secs_arg = (2 ** H) / 2 / 1e3
    print(f"\n  {pw}")
    print(f"    {desc}")
    print(f"    entropy ≈ {H:.0f} bit")
    print(f"    MD5-এ    : {humanize(secs_md5)}")
    print(f"    argon2-এ : {humanize(secs_arg)}")

দুইটা শিক্ষা:

১. Entropy জেনারেশন প্রক্রিয়ার ধর্ম, string-এর নয়। Tr0ub4dor&3 দেখতে random, কিন্তু বানানোর নিয়মটা পূর্বানুমেয়।

২. Hash-এর ধীরগতি entropy-র চেয়ে বেশি কাজ করে। ৪৪-bit entropy + argon2id > ৭২-bit entropy + MD5।

এই কারণেই OWASP-এর সুপারিশ: password হাতে বানাবেন না, password manager দিয়ে সত্যিকার random বানান — আর server-এ argon2id ব্যবহার করুন।

এটা কী প্রমাণ করে

তাত্ত্বিক entropy আর প্রকৃত নিরাপত্তা এক জিনিস নয় — কারণ attacker uniform random চেষ্টা করে না, মানুষের pattern চেষ্টা করে।

নিজে বানান

BUILD IT

Combinatorics Toolkit

Python · ●●●○○

চারটা মৌলিক গণনা সূত্র implement করুন
Pascal triangle দিয়ে C(n,k) — overflow ছাড়া
Enumeration লিখুন এবং সূত্রের সাথে সংখ্যা মিলিয়ে দেখুন
একটা password strength calculator বানান

from math import comb, perm, factorial, log2
from itertools import product, permutations, combinations, combinations_with_replacement


# ── চারটা মৌলিক সূত্র ────────────────────────────────────────
def with_rep_ordered(n, k):      return n ** k
def no_rep_ordered(n, k):        return perm(n, k)
def no_rep_unordered(n, k):      return comb(n, k)
def with_rep_unordered(n, k):    return comb(n + k - 1, k)


# ── Pascal's triangle — বড় সংখ্যায়ও নিরাপদ ──────────────────
def binomial_pascal(n, k):
    """C(n,k), Pascal's identity দিয়ে — factorial overflow এড়ায়"""
    if k \< 0 or k > n: return 0
    k = min(k, n - k)                       # symmetry
    row = [1]
    for i in range(1, n + 1):
        row = [1] + [row[j] + row[j+1] for j in range(len(row)-1)] + [1]
        if len(row) > k + 1:
            row = row[:k+1] + row[k+1:]     # শুধু দরকারি অংশ
    return row[k] if k \< len(row) else 0


def binomial_fast(n, k):
    """C(n,k) গুণ-ভাগ দিয়ে, মধ্যবর্তী মান ছোট রেখে"""
    if k \< 0 or k > n: return 0
    k = min(k, n - k)
    result = 1
    for i in range(k):
        result = result * (n - i) // (i + 1)
    return result


# ── সূত্র বনাম গণনা — মিলিয়ে দেখুন ──────────────────────────
def verify(n, k):
    items = list(range(n))
    checks = [
        ("n^k          ", with_rep_ordered(n, k),
         sum(1 for _ in product(items, repeat=k))),
        ("P(n,k)       ", no_rep_ordered(n, k),
         sum(1 for _ in permutations(items, k))),
        ("C(n,k)       ", no_rep_unordered(n, k),
         sum(1 for _ in combinations(items, k))),
        ("C(n+k-1,k)   ", with_rep_unordered(n, k),
         sum(1 for _ in combinations_with_replacement(items, k))),
    ]
    print(f"\nn={n}, k={k}")
    for name, formula, counted in checks:
        mark = "ok" if formula == counted else "MISMATCH"
        print(f"  {name} সূত্র={formula:>8}  গোনা={counted:>8}  {mark}")

verify(5, 3)
verify(4, 2)
verify(6, 4)

# Pascal আর fast একই উত্তর দেয় কি?
for n, k in [(10,3), (50,25), (100,50), (500,250)]:
    a, b = binomial_fast(n, k), comb(n, k)
    print(f"C({n},{k}): {'মিলেছে' if a == b else 'ভুল'}  ({len(str(a))} অঙ্কের সংখ্যা)")


# ── Password strength ───────────────────────────────────────
import re

def charset_size(pw):
    size = 0
    if re.search(r'[a-z]', pw):            size += 26
    if re.search(r'[A-Z]', pw):            size += 26
    if re.search(r'[0-9]', pw):            size += 10
    if re.search(r'[^a-zA-Z0-9]', pw):     size += 33
    return size or 1

def naive_entropy(pw):
    """অক্ষর-ভিত্তিক — attacker uniform brute force করলে"""
    return len(pw) * log2(charset_size(pw))

COMMON = {"password", "123456", "qwerty", "letmein", "admin", "welcome"}

def realistic_entropy(pw):
    """সাধারণ pattern-এর জন্য শাস্তি"""
    low = pw.lower()
    penalty = 0
    if low in COMMON:                        return 8.0
    if re.fullmatch(r'[a-zA-Z]+\d{1,4}!?', pw):  penalty += 20   # word+digits
    if re.search(r'(.)\1{2,}', pw):              penalty += 8    # পুনরাবৃত্তি
    if re.search(r'(012|123|234|345|abc|qwe)', low): penalty += 10
    for word in ("password", "admin", "love", "dragon", "monkey"):
        if word in low:                          penalty += 15
    return max(8.0, naive_entropy(pw) - penalty)

def crack_time(bits, rate):
    secs = (2 ** bits) / 2 / rate
    for unit, n in [("সেকেন্ড",1),("মিনিট",60),("ঘণ্টা",3600),
                    ("দিন",86400),("বছর",31_536_000)]:
        if secs \< n * 1000: return f"{secs/n:.1f} {unit}"
    return f"{secs/31_536_000:.1e} বছর"

print("\n" + "─" * 66)
print(f"{'password':>26} {'সরল':>7} {'বাস্তব':>8} {'MD5':>12} {'argon2':>12}")
for pw in ["password", "P@ssw0rd1", "Tr0ub4dor&3",
           "correcthorsebatterystaple", "xK9#mQ2vL@8p", "aaaaaaaaaaaa"]:
    n_ent, r_ent = naive_entropy(pw), realistic_entropy(pw)
    print(f"{pw:>26} {n_ent:>6.0f}b {r_ent:>7.0f}b "
          f"{crack_time(r_ent, 1e11):>12} {crack_time(r_ent, 1e3):>12}")

নিজে বাড়ান:

Multinomial coefficient যোগ করুন — n!/(k₁!k₂!…kₘ!), যা একই ধরনের জিনিস থাকলে সাজানোর সংখ্যা দেয়
Derangement গুনুন — এমন permutation যেখানে কোনো element নিজের জায়গায় নেই (!n)। এটা “কেউ নিজের নাম তোলেনি” ধরনের সমস্যায় লাগে
Catalan সংখ্যা — C(2n,n)/(n+1) — যা balanced bracket, binary tree আর stack permutation-এর সংখ্যা দেয়
দুইটা thread-এর n operation-এর সব interleaving enumerate করুন এবং সংখ্যা C(2n,n)-এর সাথে মিলিয়ে দেখুন
zxcvbn library-র সাথে আপনার entropy estimator তুলনা করুন

বাস্তব সিস্টেমে

গণনা যেখানে সিদ্ধান্ত নেয়

Cryptographic key size। AES-128 নিরাপদ কারণ 2¹²⁸ ≈ 3.4 × 10³⁸ টা key — সব চেষ্টা করা physically অসম্ভব (তাপগতিবিদ্যার সীমা অনুযায়ী 2¹²⁸ বার একটা counter বাড়াতেও একটা তারার সমান শক্তি লাগত)। কিন্তু quantum computer-এ Grover’s algorithm এটা কার্যত 2⁶⁴-এ নামিয়ে আনে, তাই post-quantum প্রেক্ষাপটে AES-256 সুপারিশ করা হয়।

UUID-এর নকশা। UUIDv4-এ ১২২ bit random। Birthday bound অনুযায়ী 2⁶¹ ≈ 2.3 × 10¹⁸ টা UUID-এর পরেও collision সম্ভাবনা নগণ্য। এই কারণেই কেন্দ্রীয় coordination ছাড়াই unique id বানানো যায়।

Query planner-এর join order। n টা table join করার উপায় n!-এর ক্রমে (আসলে Catalan সংখ্যা × permutation)। ১০টা table মানে লক্ষ লক্ষ সম্ভাব্য plan। PostgreSQL তাই ১২টার বেশি table হলে exhaustive search ছেড়ে genetic algorithm ব্যবহার করে (geqo_threshold)। Level 8-এ দেখব।

Test case generation। ৫টা parameter, প্রতিটার ৪টা মান → 4⁵ = 1024 টা combination। সব চালানো ব্যয়বহুল, তাই pairwise testing ব্যবহার হয় — প্রতিটা জোড়া parameter-এর সব combination ঢাকা হয়, যা সাধারণত ২০-৩০টা test-এ সম্ভব। গবেষণা বলে বেশিরভাগ bug এক বা দুইটা parameter-এর interaction থেকে আসে।

Load balancing — power of two choices। n টা server-এ random assignment করলে সবচেয়ে ব্যস্ত server-এর load Θ(log n / log log n)। কিন্তু দুইটা random server দেখে কম ব্যস্তটা বাছলে সেটা নেমে আসে Θ(log log n)-এ। শুধু একটা বাড়তি probe, নাটকীয় উন্নতি। Level 9-এ দেখব।

Bloom filter-এর আকার। n টা element, m bit, k টা hash function দিলে false positive হার প্রায় (1 − e^(−kn/m))^k। এই সূত্র থেকে optimal k = (m/n) ln 2 — combinatorics দিয়ে সরাসরি derive করা।

Compiler-এর register allocation। k টা register-এ variable বসানো = graph k-coloring, যা NP-complete। সম্ভাব্য assignment k^n, তাই heuristic (linear scan, graph coloring) ব্যবহার হয়।

Game AI। Chess-এর game tree প্রায় 10¹²⁰ node (Shannon number), Go-তে 10⁷⁶⁰। Exhaustive search চিরকালেও অসম্ভব — তাই alpha-beta pruning, তারপর Monte Carlo tree search, তারপর neural network evaluation।

যে ভুলগুলো সবাই করে

“Password-এ চিহ্ন যোগ করলেই নিরাপদ হয়।”

Charset বাড়ানো entropy বাড়ায়, কিন্তু দৈর্ঘ্য অনেক বেশি কার্যকর।

$H = k \log_2 n$

n (charset) logarithm-এর ভেতরে, k (দৈর্ঘ্য) গুণক হিসেবে।

তুলনা করুন:

Password	দৈর্ঘ্য	charset	entropy
`P@ss1!`	6	95	39 bit
`abcdefghijkl`	12	26	56 bit
`abcdefghijklmnop`	16	26	75 bit

শুধু lowercase-এর ১৬ অক্ষর, পূর্ণ charset-এর ৬ অক্ষরের চেয়ে অনেক শক্তিশালী।

আর “একটা চিহ্ন থাকতেই হবে” নিয়মটা প্রায়ই উল্টো ফল দেয় — কারণ মানুষ তখন পূর্বানুমেয়ভাবে শেষে ! যোগ করে, যা attacker-এর rule list-এ প্রথম দিকেই আছে।

NIST SP 800-63B (২০১৭ থেকে) তাই সুপারিশ পাল্টেছে: দৈর্ঘ্যের উপর জোর দিন, জটিলতার নিয়ম বাদ দিন, আর পর্যায়ক্রমিক পরিবর্তন বাধ্যতামূলক করবেন না।

“`C(n,k)` হিসাব করতে factorial লাগে।”

সূত্রে factorial আছে, কিন্তু হিসাবে ব্যবহার করা উচিত নয়।

# খারাপ — মধ্যবর্তী মান বিশাল
def bad(n, k):
    return factorial(n) // (factorial(k) * factorial(n-k))

bad(100, 50)     # 100! গণনা করে — ১৫৮ অঙ্কের সংখ্যা

C(100,50) ≈ 10²⁹ — কিন্তু 100! ≈ 10¹⁵⁸। মধ্যবর্তী মানটা উত্তরের চেয়ে 10¹²⁹ গুণ বড়!

C বা Java-তে এটা সরাসরি overflow। Python-এ কাজ করে কিন্তু ধীর।

# ভালো — মধ্যবর্তী মান কখনো উত্তরের চেয়ে বেশি বড় হয় না
def good(n, k):
    k = min(k, n - k)
    r = 1
    for i in range(k):
        r = r * (n - i) // (i + 1)
    return r

লক্ষ্য করুন // (i+1) প্রতি ধাপেই হচ্ছে — আর এটা সবসময় নিঃশেষে বিভাজ্য, কারণ পরপর i+1 টা সংখ্যার গুণফল (i+1)! দিয়ে বিভাজ্য।

আরো ভালো — Pascal’s triangle দিয়ে, যদি একাধিক মান লাগে: প্রতিটা entry শুধু যোগ, কোনো গুণ-ভাগ নেই। DP-র ক্লাসিক উদাহরণ।

Python 3.8+ -এ math.comb(n, k) আছে, আর সেটা এই কৌশলগুলোই ব্যবহার করে।

“Combinatorial explosion মানে সমস্যাটা অসমাধেয়।”

2ⁿ সম্ভাবনা মানে brute force অসম্ভব — কিন্তু সমস্যাটা অসম্ভব নয়।

তিনটা পথ খোলা থাকে:

১. Pruning। বেশিরভাগ শাখা তাড়াতাড়ি বাতিল করা। Alpha-beta pruning chess-এর search space-কে কার্যত বর্গমূলে নামিয়ে আনে — সেই একই সময়ে দ্বিগুণ গভীরে যাওয়া যায়।

২. চতুর algorithm। SAT তাত্ত্বিকভাবে 2ⁿ, কিন্তু আধুনিক CDCL solver লক্ষ variable-এর industrial instance মিনিটে সমাধান করে। Clause learning, unit propagation, restart — এসব heuristic বাস্তব instance-এর কাঠামো কাজে লাগায়।

৩. Approximation। Optimal-এর বদলে “যথেষ্ট ভালো”। Traveling salesman NP-hard, কিন্তু Christofides algorithm 1.5× optimal-এর মধ্যে থাকে, polynomial সময়ে।

তাত্ত্বিক worst case আর ব্যবহারিক গড় case-এর ফাঁকটাই আধুনিক computer science-এর সবচেয়ে আকর্ষণীয় জায়গা।

Level 13-এ আমরা এই ফাঁকটা নিয়ে বিস্তারিত কথা বলব।

“Birthday paradox শুধু একটা মজার তথ্য।”

এটা cryptography-র একটা মৌলিক আক্রমণ পদ্ধতি, আর এর ব্যবহারিক পরিণতি বিশাল।

Collision resistance সবসময় হash আকারের অর্ধেক।

Hash	আকার	Preimage resistance	Collision resistance
MD5	128	128 bit (তাত্ত্বিক)	64 bit → ভাঙা
SHA-1	160	160 bit	80 bit → ভাঙা
SHA-256	256	256 bit	128 bit → নিরাপদ

MD5-এর collision এখন সেকেন্ডে বানানো যায়। SHA-1-এর জন্য ২০১৭-তে Google-এর 6500 CPU-বছর লেগেছিল; এখন অনেক সস্তা।

বাস্তব আক্রমণ:

২০০৮: গবেষকরা MD5 collision দিয়ে একটা জাল CA certificate বানিয়েছিলেন — যেকোনো HTTPS সাইটের ছদ্মবেশ ধরা সম্ভব ছিল
Flame malware (২০১২): MD5 collision দিয়ে Microsoft-এর code signing জাল করে Windows Update-এর মাধ্যমে ছড়িয়েছিল
SHAttered (২০১৭): একই SHA-1 hash-এর দুইটা ভিন্ন PDF

তাই নিয়ম: যেখানে collision resistance দরকার (signature, content addressing, certificate), সেখানে অন্তত ২৫৬-bit hash।

বুঝেছেন কি না দেখুন

একটা ৮ অক্ষরের password শুধু lowercase দিয়ে বনাম ৬ অক্ষরের password সব ASCII printable (৯৫টা) দিয়ে — কোনটা বেশি নিরাপদ?

প্রয়োগ

$26^8 = 2.09 \times 10^{11} \qquad H = 8 \log_2 26 = 37.6 \text{ bit}$ $95^6 = 7.35 \times 10^{11} \qquad H = 6 \log_2 95 = 39.4 \text{ bit}$

দ্বিতীয়টা সামান্য শক্তিশালী — প্রায় ৩.৫ গুণ বড় space, ১.৮ bit বেশি entropy।

কিন্তু পার্থক্যটা নগণ্য। GPU-তে MD5 ধরে নিলে:

	space	গড় crack time
8× lowercase	`2.1 × 10¹¹`	~১ সেকেন্ড
6× full ASCII	`7.4 × 10¹¹`	~৪ সেকেন্ড

দুটোই কার্যত অনিরাপদ।

এখন দৈর্ঘ্য বাড়িয়ে দেখুন:

Password	entropy	MD5-এ crack time
8 × lowercase	37.6 bit	১ সেকেন্ড
12 × lowercase	56.4 bit	~৯ ঘণ্টা
16 × lowercase	75.2 bit	~৬,৭০০ বছর
20 × lowercase	94 bit	~10⁹ বছর

শুধু lowercase রেখে দৈর্ঘ্য বাড়ালেই যথেষ্ট।

কারণ সূত্রটা H = k log₂ n — k linear, n logarithmic। Charset দ্বিগুণ করলে প্রতি অক্ষরে ১ bit বাড়ে; দৈর্ঘ্য দ্বিগুণ করলে পুরো entropy দ্বিগুণ হয়।

এই কারণেই passphrase (correct horse battery staple) কাজ করে — মনে রাখা সহজ, আর যথেষ্ট লম্বা।

৫২ তাসের একটা প্যাকেট থেকে ৫ তাসের হাত। (ক) কতগুলো সম্ভব? (খ) কতগুলোতে ঠিক একজোড়া (pair) আছে?

যুক্তি

(ক) মোট হাত:

ক্রম গুরুত্বপূর্ণ নয়, পুনরাবৃত্তি নেই:

$\binom{52}{5} = \frac{52 \times 51 \times 50 \times 49 \times 48}{120} = 2{,}598{,}960$

(খ) ঠিক একজোড়া:

“ঠিক একজোড়া” মানে: একটা rank দুইবার, বাকি তিনটা তাস তিনটা ভিন্ন rank-এর (কোনো দ্বিতীয় জোড়া নেই, three-of-a-kind নেই)।

ধাপে ধাপে product rule:

১. জোড়ার rank বাছুন: ১৩টা rank থেকে ১টা $\binom{13}{1} = 13$

২. সেই rank-এর ৪টা suit থেকে ২টা: $\binom{4}{2} = 6$

৩. বাকি ৩টা তাসের rank বাছুন: বাকি ১২টা rank থেকে ৩টা $\binom{12}{3} = 220$

(ভিন্ন rank নিতেই হবে — নাহলে আরেকটা জোড়া হয়ে যেত)

৪. প্রতিটার suit বাছুন: প্রতিটার ৪টা পছন্দ $4^3 = 64$

$13 \times 6 \times 220 \times 64 = 1{,}098{,}240$

সম্ভাবনা: $\frac{1{,}098{,}240}{2{,}598{,}960} \approx 42.3\%$

যাচাই — সব হাতের ধরন যোগ করলে মোট হওয়া উচিত:

হাত	সংখ্যা	সম্ভাবনা
Royal flush	4	0.000154%
Straight flush	36	0.00139%
Four of a kind	624	0.0240%
Full house	3,744	0.1441%
Flush	5,108	0.1965%
Straight	10,200	0.3925%
Three of a kind	54,912	2.1128%
Two pair	123,552	4.7539%
One pair	1,098,240	42.2569%
High card	1,302,540	50.1177%
মোট	2,598,960	100%

যোগফল ঠিক মিলেছে — এটাই গণনার সঠিকতা যাচাইয়ের সেরা উপায়।

এই ধরনের হিসাব কেন গুরুত্বপূর্ণ: poker AI, casino-র house edge, আর যেকোনো probabilistic system-এর মডেলিং — সবই একই কৌশল: ধাপে ধাপে বাছাই, product rule দিয়ে গুণ, তারপর যোগফল যাচাই।

আপনি একটা distributed system-এ unique id তৈরি করছেন, কেন্দ্রীয় coordination ছাড়া। কত bit random লাগবে যাতে ১ বিলিয়ন id-তে collision-এর সম্ভাবনা ১-এ ১০ লক্ষের কম থাকে?

ডিজাইন

Birthday bound-এর আনুমানিক সূত্র (k ≪ √N হলে):

$P(\text{collision}) \approx \frac{k^2}{2N}$

চাই: P \< 10⁻⁶ যখন k = 10⁹।

$\frac{(10^9)^2}{2N} \< 10^{-6} \implies N > \frac{10^{18}}{2 \times 10^{-6}} = 5 \times 10^{23}$

$\text{bits} = \log_2(5 \times 10^{23}) \approx 79$

অন্তত ৭৯ bit random লাগবে।

ব্যবহারিক সিদ্ধান্ত:

বিকল্প	random bit	১ বিলিয়ন id-তে collision
64-bit random	64	~2.7% — অগ্রহণযোগ্য
80-bit	80	~4 × 10⁻⁷
UUIDv4	122	~9 × 10⁻²⁰
128-bit random	128	~1.5 × 10⁻²¹

সুপারিশ: UUIDv4 (১২২ bit random, ১২৮ bit মোট)। বিশাল নিরাপত্তা মার্জিন, সর্বত্র সমর্থিত।

কিন্তু একটা বড় সমস্যা আছে — database index।

Random UUID primary key হিসেবে ব্যবহার করলে B-tree-তে insert এলোমেলো জায়গায় হয়, ফলে:

Page split বেশি
Cache locality খারাপ
Index fragmentation

সমাধান: time-ordered id।

Scheme	গঠন	সুবিধা
UUIDv7	48-bit timestamp + 74-bit random	সময়ক্রমে সাজানো, standard
ULID	48-bit time + 80-bit random	lexicographically sortable
Snowflake	41-bit time + 10-bit machine + 12-bit seq	৬৪ bit, কিন্তু machine id দরকার

UUIDv7-এর হিসাব: ৭৪ bit random, কিন্তু শুধু একই মিলিসেকেন্ডের মধ্যে collision হতে পারে। একটা মিলিসেকেন্ডে ১০ লক্ষ id তৈরি হলেও:

$P \approx \frac{(10^6)^2}{2 \times 2^{74}} \approx 2.6 \times 10^{-11}$

সম্পূর্ণ নিরাপদ, এবং index-friendly।

Snowflake-এর ভিন্ন কৌশল: random-এর উপর নির্ভর না করে machine id দিয়ে space ভাগ করে দেওয়া — তখন collision গাণিতিকভাবে অসম্ভব (একই machine একই ms-এ sequence বাড়ায়)। দাম: machine id বরাদ্দের জন্য coordination লাগে।

Level 9-এ আমরা distributed id generation বিস্তারিত দেখব।

একটা function-এর ৫টা boolean parameter আছে। (ক) সব combination test করতে কতগুলো test case? (খ) pairwise coverage-এ কতগুলো জোড়া ঢাকতে হবে?

প্রয়োগ

(ক) Exhaustive:

$2^5 = 32 \text{ টা test case}$

(খ) Pairwise:

parameter-এর জোড়া: C(5,2) = 10 প্রতি জোড়ায় মান-combination: 2 × 2 = 4

$10 \times 4 = 40 \text{ টা জোড়া-combination ঢাকতে হবে}$

কিন্তু একটা test case একসাথে ১০টা জোড়া ঢাকে (কারণ প্রতিটা test-এ সব ৫টা parameter-এর মান আছে, আর তাদের C(5,2) = 10 টা জোড়া)।

তাই তাত্ত্বিক সর্বনিম্ন 40/10 = 4 টা test। বাস্তবে covering array algorithm সাধারণত ৬টা test-এ সব জোড়া ঢাকে।

৩২ থেকে ৬ — ৮০% কম।

Parameter বাড়লে সাশ্রয় নাটকীয় হয়:

Parameters	মান/param	Exhaustive	Pairwise
5	2	32	~6
10	2	1,024	~10
10	3	59,049	~17
20	4	10¹²	~30

কেন pairwise যথেষ্ট (প্রায়ই):

NIST-এর একটা গবেষণায় (Kuhn et al.) বিভিন্ন domain-এর bug বিশ্লেষণ করে দেখা গেছে:

Interaction level	ধরা পড়া bug-এর অনুপাত
1-way (একটা parameter)	20–68%
2-way (pairwise)	65–97%
3-way	89–99%
4-way	96–100%
6-way	100%

Pairwise-এই ৬৫–৯৭% bug ধরা পড়ে, খরচের একটা ভগ্নাংশে।

সরঞ্জাম: Microsoft PICT, ACTS (NIST), allpairspy (Python), pairwise (Java)।

from allpairspy import AllPairs

params = [[True, False]] * 5
for i, case in enumerate(AllPairs(params), 1):
    print(i, case)

সাবধানতা: pairwise “সব bug ধরে” বলে না। Security-critical বা safety-critical কোডে উচ্চতর interaction level বা exhaustive testing দরকার হতে পারে। আর কিছু bug একটাই নির্দিষ্ট মানে ঘটে (boundary value) — সেগুলো আলাদাভাবে test করতে হয়।

কেন 2¹²⁸ কে “brute force করা অসম্ভব” বলা হয়, যেখানে 2⁶⁴ কে “সম্ভব” বলা হয়? সংখ্যা দিয়ে দেখান।

যুক্তি

$2^{64} \approx 1.8 \times 10^{19} \qquad 2^{128} \approx 3.4 \times 10^{38}$

অনুপাত: 2⁶⁴ ≈ 1.8 × 10¹⁹ গুণ।

2⁶⁴ — সম্ভব:

Bitcoin নেটওয়ার্ক (২০২৪-এর কাছাকাছি) সেকেন্ডে প্রায় 6 × 10²⁰ SHA-256 করে।

$\frac{1.8 \times 10^{19}}{6 \times 10^{20}} = 0.03 \text{ সেকেন্ড}$

Bitcoin miner-রা কার্যত প্রতি সেকেন্ডে বহুবার পুরো 2⁶⁴ space অতিক্রম করছে।

একটা GPU cluster-ও কয়েক মাসে পারবে। DES (৫৬ bit) ১৯৯৮-এ ৫৬ ঘণ্টায় ভাঙা হয়েছিল একটা $250,000-এর যন্ত্র দিয়ে।

2¹²⁸ — অসম্ভব:

সেই Bitcoin নেটওয়ার্কের গতিতে:

$\frac{3.4 \times 10^{38}}{6 \times 10^{20}} = 5.7 \times 10^{17} \text{ সেকেন্ড} = 1.8 \times 10^{10} \text{ বছর}$

১৮ বিলিয়ন বছর — মহাবিশ্বের বয়সের চেয়ে বেশি। আর এটা মানব সভ্যতার সমগ্র computing power একত্র করে।

তাপগতিবিদ্যার সীমা — আরো শক্তিশালী যুক্তি:

Landauer’s principle বলে, T তাপমাত্রায় এক bit তথ্য মুছতে অন্তত kT ln 2 শক্তি লাগে। মহাজাগতিক পটভূমি তাপমাত্রা (3.2 K) ধরলে:

$E_{\min} = 1.38 \times 10^{-23} \times 3.2 \times \ln 2 \approx 3 \times 10^{-23} \text{ J}$

2¹²⁸ বার একটা counter বাড়াতে (হিসাবের কাজ ছাড়াই, শুধু গোনা):

$3.4 \times 10^{38} \times 3 \times 10^{-23} \approx 10^{16} \text{ J}$

তুলনা: সূর্যের এক সেকেন্ডের শক্তি উৎপাদন 3.8 × 10²⁶ J।

10¹⁶ J মানে সূর্যের প্রায় 2.6 × 10⁻¹¹ সেকেন্ডের শক্তি — শুনতে কম, কিন্তু এটা পৃথিবীর সব সমুদ্রের পানি ফুটিয়ে বাষ্প করার সমান শক্তি।

আর 2²⁵⁶-এর জন্য? Bruce Schneier-এর বিখ্যাত হিসাব: একটা সুপারনোভার সমগ্র শক্তি দিয়েও শুধু counter গোনা শেষ হবে না।

তাই cryptographic নিরাপত্তা “কেউ চেষ্টা করেনি” নয় — এটা পদার্থবিজ্ঞানের সীমা।

একটা গুরুত্বপূর্ণ সতর্কতা: এই যুক্তি শুধু brute force-এর বিরুদ্ধে। Algorithm-এ দুর্বলতা থাকলে সব বদলে যায় — DES ভাঙা হয়েছিল brute force দিয়ে, কিন্তু MD5 আর SHA-1 ভাঙা হয়েছে গাণিতিক আক্রমণ দিয়ে, যা brute force-এর চেয়ে অনেক দ্রুত।

আর quantum computer: Grover’s algorithm symmetric key-এর কার্যকর নিরাপত্তা অর্ধেক করে (2¹²⁸ → 2⁶⁴), আর Shor’s algorithm RSA/ECC সম্পূর্ণ ভেঙে দেয়। Level 10-এ দেখব।

এরপর কী

Combinatorics আমাদের বলে কতগুলো সম্ভাবনা আছে। কিন্তু বেশিরভাগ বাস্তব প্রশ্ন হলো: কোনটার সম্ভাবনা কত?

Hash table-এ গড়ে কতগুলো probe লাগবে? Quicksort-এর গড় running time কত? একটা random algorithm কত সম্ভাবনায় ভুল উত্তর দেবে? একটা distributed system-এ কোনো এক ঘণ্টায় node fail হওয়ার সম্ভাবনা কত?

পরের লেসনে probability — sample space, conditional probability, Bayes’ theorem, random variable আর expectation। আর সেখানে আমরা দেখব কেন randomized algorithm প্রায়ই deterministic-এর চেয়ে সহজ ও দ্রুত, আর কেন “গড় ক্ষেত্রে ভালো” একটা সম্পূর্ণ বৈধ engineering লক্ষ্য।

Combinatorics — গোনার শিল্প

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

দুইটা মৌলিক নিয়ম

Sum rule — “অথবা”

Product rule — “এবং”

চারটা মৌলিক গণনা

১. পুনরাবৃত্তি সহ, ক্রম সহ — `n^k`

২. পুনরাবৃত্তি ছাড়া, ক্রম সহ — Permutation

৩. পুনরাবৃত্তি ছাড়া, ক্রম ছাড়া — Combination

৪. পুনরাবৃত্তি সহ, ক্রম ছাড়া — Multiset

Binomial coefficient-এর ধর্ম

Pascal’s identity

Symmetry

Binomial theorem

Combinatorial explosion

ভেতরে কী ঘটছে

Password strength — combinatorics-এর সরাসরি প্রয়োগ

Concurrency — interleaving গোনা

State space explosion

উদাহরণ

Birthday problem — আশ্চর্যজনক ফল

Hash collision-এ এটাই ফিরে আসে

Counting arguments in algorithms

কেন comparison sort `Ω(n log n)`

নিজে চালিয়ে দেখুন

Birthday paradox simulate করুন

Password entropy বনাম বাস্তব crack time

নিজে বানান

Combinatorics Toolkit

বাস্তব সিস্টেমে

গণনা যেখানে সিদ্ধান্ত নেয়

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

দুইটা মৌলিক নিয়ম

Sum rule — “অথবা”

Product rule — “এবং”

চারটা মৌলিক গণনা

১. পুনরাবৃত্তি সহ, ক্রম সহ — n^k

২. পুনরাবৃত্তি ছাড়া, ক্রম সহ — Permutation

৩. পুনরাবৃত্তি ছাড়া, ক্রম ছাড়া — Combination

৪. পুনরাবৃত্তি সহ, ক্রম ছাড়া — Multiset

Binomial coefficient-এর ধর্ম

Pascal’s identity

Symmetry

Binomial theorem

Combinatorial explosion

⚙ভেতরে কী ঘটছেUnder the hood

Password strength — combinatorics-এর সরাসরি প্রয়োগ

Concurrency — interleaving গোনা

State space explosion

▶উদাহরণExample

Birthday problem — আশ্চর্যজনক ফল

Hash collision-এ এটাই ফিরে আসে

Counting arguments in algorithms

কেন comparison sort Ω(n log n)

⌘নিজে চালিয়ে দেখুনExperiment

Birthday paradox simulate করুন

Password entropy বনাম বাস্তব crack time

⚒নিজে বানানBuild it yourself

Combinatorics Toolkit

◉বাস্তব সিস্টেমেReal-world usage

গণনা যেখানে সিদ্ধান্ত নেয়

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

১. পুনরাবৃত্তি সহ, ক্রম সহ — `n^k`

ভেতরে কী ঘটছে

উদাহরণ

কেন comparison sort `Ω(n log n)`

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী