সংখ্যাতত্ত্বের প্রয়োগ — check digit, hashing আর pseudorandom সংখ্যা

১ · একটি হাতিয়ার, তিনটি কাজ — বাজারঘরের তিন সমস্যা

মডিউল ৪-এ আমরা সংখ্যাতত্ত্বের মূল যন্ত্রপাতি তৈরি করেছি: বিভাজ্যতা আর মৌলিক সংখ্যা (পর্ব ২০), gcd আর extended Euclid (পর্ব ২১), modular arithmetic (পর্ব ২২), inverse আর CRT (পর্ব ২৩), Fermat আর Euler (পর্ব ২৪), আর মৌলিকতার পরীক্ষা (পর্ব ২৫ “Primality test আর factoring — Miller–Rabin থেকে কঠিনতার ধারণা”). এই শেষ পর্বে সেই যন্ত্রপাতি দিয়ে তিনটি দৈনন্দিন কাজ করা হবে, প্রায় কোনো নতুন যন্ত্র ছাড়াই।

কাল্পনিক অনলাইন দোকান বাজারঘরের তিনটি সমস্যা দিয়ে শুরু করা যাক।

• টাইপের ভুল: গুদামের কর্মী ফোনে শুনে ইনভয়েস নম্বর টাইপ করেন। একটি অঙ্ক ভুল হলে বা পাশাপাশি দুটি অঙ্ক উল্টে গেলে ভুল পার্সেল ভুল ঠিকানায় যায়। নম্বরের শেষে একটি অতিরিক্ত অঙ্ক বসিয়ে কি এমন ভুল সঙ্গে সঙ্গে ধরা যায়?
• বোঝা ভাগ করা: কয়েক লক্ষ অর্ডার আইডিকে 64টি ডেটাবেস ভাগে (বালতিতে) রাখতে হবে, যাতে কোনো ভাগে চাপ বেশি না পড়ে। “আইডি mod 64” কি যথেষ্ট?
• এলোমেলো বাছাই: লটারিতে কুপন পাবেন কোন গ্রাহক? কম্পিউটার “এলোমেলো” সংখ্যা বানায় কীভাবে, আর কেউ কি তা আগে থেকে অনুমান করতে পারে?

তিনটির উত্তরই একটি প্রশ্নে নামে: x ↦ ax + b (mod m) ফাংশনটি কখন সব ভাগশেষ ছুঁয়ে যায়, আর কখন কিছু ভাগশেষ বাদ পড়ে? উত্তর দেয় gcd(a, m). gcd = 1 হলে ফাংশনটি একটি bijection, কারণ a-এর inverse আছে (পর্ব ২৩); gcd = g > 1 হলে সে শুধু m/g-টি ভাগশেষে পৌঁছায়। এই এক তথ্য থেকে check digit-এর ভুল ধরা, hashing-এর ছড়িয়ে পড়া আর random-এর period, তিনটিই আসবে। মাঝে মাঝে Euclid-এর lemma (পর্ব ২১) আর order ও primitive root (পর্ব ২৪) লাগবে।

২ · Check digit-এর গণিত — ISBN-10 আর mod 11

Check digit হলো একটি সংখ্যার শেষে বসানো অতিরিক্ত অঙ্ক, যা বাকি অঙ্কগুলো থেকে হিসাব করে বের করা হয়। এটি কোনো নতুন তথ্য বহন করে না; তার কাজ শুধু পাহারা দেওয়া। কেউ নম্বরটি ভুল টাইপ করলে হিসাব আর মেলে না, আর কম্পিউটার সঙ্গে সঙ্গে বলে “নম্বরটি সঠিক নয়”। পরীক্ষার খাতায় রোল নম্বরের পাশে কথায় লেখা রোল নম্বরও একই কাজ করে: দুটো না মিললে কোথাও ভুল হয়েছে।

হাতে নম্বর লেখায় সবচেয়ে সাধারণ দুই ধরনের ভুল (ডাচ গণিতবিদ J. Verhoeff-এর ১৯৬৯ সালের পরিচিত পর্যবেক্ষণ অনুযায়ী): একক ভুল (একটি অঙ্কের জায়গায় অন্য অঙ্ক, যেমন 4 → 7) আর পাশাপাশি অদলবদল বা transposition error (যেমন …58… → …85…). একটি ভালো পদ্ধতিকে অন্তত এই দুই ধরনের ভুল ধরতে হয়।

শেষ অঙ্কটি সবসময় বাছা যায় কি না, তা পর্ব ২৩-এর linear congruence-এর প্রশ্ন: w_nd_n ≡ −(বাকি যোগফল) (mod m). gcd(w_n, m) = 1 হলে ঠিক একটি সমাধান mod m আছে। সব পদ্ধতির ভুল-ধরার ক্ষমতা নিচের এক lemma থেকে আসে।

প্রমাণ:

1. (ক) পুরোনো যোগফল S ≡ 0. নতুন যোগফল S′ = S + w_i(d_i′ − d_i), কারণ শুধু একটি পদ বদলেছে। — যোগফলের পার্থক্য
2. ভুল ধরা পড়ে না মানে নতুন নম্বরও বৈধ, অর্থাৎ S′ ≡ 0 ⇔ m ∣ S′ − S = w_i(d_i′ − d_i). — congruence-এর সংজ্ঞা
3. (খ) আগে i আর j অবস্থানে w_ia + w_jb, পরে w_ib + w_ja. পার্থক্য w_i(b − a) + w_j(a − b) = −(w_i − w_j)(a − b). ধাপ ২-এর যুক্তিতে ভুল ধরা পড়ে না ⇔ m এই পার্থক্যকে ভাগ করে। ∎ — বীজগণিত

এখন যেকোনো পদ্ধতি পরীক্ষা করা সহজ: শুধু দেখতে হবে কোন গুণফল m দিয়ে বিভাজ্য হতে পারে। এর জন্য সবচেয়ে সুবিধাজনক m হলো একটি মৌলিক সংখ্যা, কারণ তখন Euclid-এর lemma খাটে: মৌলিক p যদি দুটি সংখ্যার গুণফলকে ভাগ করে, তবে অন্তত একটিকে ভাগ করে।

ISBN-10: ওজন 10 থেকে 1, mod 11

পুরোনো বইয়ের ১০ অঙ্কের ISBN-এ ওজন 10, 9, 8, …, 2, 1 আর modulus 11. Check digit 0 থেকে 10 পর্যন্ত যেকোনো মান নিতে পারে; 10 একটি অঙ্কে লেখা যায় না বলে তার জন্য রোমান সংখ্যা “X” ব্যবহৃত হয়। নিচের stepper একটি কাল্পনিক নম্বরের (π-এর অঙ্ক দিয়ে বানানো) check digit বের করে।

1অঙ্ক: 3 1 4 1 5 9 2 6 52ওজন: 10 9 8 7 6 5 4 3 2330 + 9 + 32 = 7147 + 30 + 45 = 82 → 15358 + 18 + 10 = 36 → 1896189 ≡ 2, তাই d₁₀ ≡ −2 ≡ 9

প্রমাণ: ওজন w_i = 11 − i, তাই প্রতিটি ওজন 1 থেকে 10-এর মধ্যে।

1. একক ভুলে Lemma ২.২(ক) অনুযায়ী দেখতে হবে 11 ∣ w_i(d_i′ − d_i) সম্ভব কি না। 11 মৌলিক, তাই Euclid-এর lemma-য় তাহলে 11 ∣ w_i বা 11 ∣ (d_i′ − d_i). — Euclid-এর lemma
2. কিন্তু 1 ≤ w_i ≤ 10, আর d_i′ ≠ d_i হওয়ায় 1 ≤ |d_i′ − d_i| ≤ 10 (X = 10 ধরেও)। 1 থেকে 10-এর কোনো সংখ্যা 11 দিয়ে বিভাজ্য নয়, তাই ভুলটি ধরা পড়ে। — আকারের সীমা
3. অদলবদলে Lemma ২.২(খ): w_i − w_j = j − i, আর i ≠ j বলে 1 ≤ |j − i| ≤ 9. a ≠ b বলে 1 ≤ |a − b| ≤ 10. ধাপ ১–২-এর একই যুক্তিতে 11 ∤ (j − i)(a − b). ∎ — Euclid-এর lemma আবার

প্রমাণের প্রতিটি ধাপ m = 11 মৌলিক হওয়ার ওপর দাঁড়িয়ে; এর দাম হলো check digit-এ অদ্ভুত “X” অক্ষর। বইয়ে প্রায়ই সমতুল্য রূপ দেখা যায়, ওজন 1, 2, …, 10, কারণ ∑ (11 − i)d_i = 11∑d_i − ∑ i·d_i. এই রূপে check digit সরাসরি ∑_i=1⁹ i·d_i mod 11 (উপরের নম্বরে 207 mod 11 = 9, একই উত্তর)।

৩ · EAN-13 আর Luhn — mod 10-এর আপস

অনেক সিস্টেম শুধু 0–9 অঙ্ক চায়, তাই বারকোড আর ব্যাংক কার্ড mod 10 ব্যবহার করে। কিন্তু 10 = 2 · 5 মৌলিক নয়, আর Euclid-এর lemma খাটে না: 10 ∣ 2 · 5, অথচ 10 ∤ 2 আর 10 ∤ 5. কোন ভুল ফাঁক গলে যায়, তা Lemma ২.২ নির্ভুলভাবে বলে।

EAN-13 আর ISBN-13: ওজন 1, 3, 1, 3, …

দোকানের পণ্যের ১৩ অঙ্কের EAN-13 নম্বরে (আর ISBN-13-এ) বাঁ থেকে ওজন পালাক্রমে 1, 3, 1, 3, …, 1, আর modulus 10. বারকোডের গঠন Computer Fundamentals কোর্সের পর্ব ১৮-এ আছে।

প্রমাণ:

1. (ক) ওজন 1 হলে পার্থক্য Δ = d′ − d, আর 1 ≤ |Δ| ≤ 9, তাই 10 ∤ Δ. ওজন 3 হলে পার্থক্য 3Δ; gcd(3, 10) = 1, তাই 10 ∣ 3Δ হলে 3-এর inverse (3 · 7 = 21 ≡ 1) দিয়ে গুণ করে 10 ∣ Δ, যা অসম্ভব। — Lemma ২.২(ক), inverse mod 10
2. (খ) পাশাপাশি দুটি অবস্থানের ওজন একটি 1, অন্যটি 3, তাই w_i − w_j = ±2, আর পার্থক্য ±2(a − b). — Lemma ২.২(খ)
3. 10 ∣ 2(a − b) ⇔ 5 ∣ (a − b). a, b অঙ্ক আর a ≠ b, তাই এটি ঘটে ঠিক তখন, যখন |a − b| = 5: জোড়াগুলো {0, 5}, {1, 6}, {2, 7}, {3, 8}, {4, 9}. ∎ — 2(a − b)-কে 10 ভাগ করে ⇔ 5 ভাগ করে a − b-কে

অর্থাৎ …38… থেকে …83… হলে বারকোড পদ্ধতি ভুলটি দেখবে না, অথচ ISBN-10 দেখত। ২০০৭ সালের বদলের দাম এই ছোট দুর্বলতা।

Luhn-এর পদ্ধতি: পালাক্রমে দ্বিগুণ

ব্যাংক কার্ড আর অনেক পরিচয় নম্বরে Luhn algorithm ব্যবহৃত হয়। নিয়ম: ডান দিক থেকে check digit-কে ১ নম্বর ধরে প্রতিটি দ্বিতীয় অঙ্ক (২, ৪, ৬, …তম) দ্বিগুণ করুন; দ্বিগুণ করে 9-এর বেশি হলে তার দুই অঙ্ক যোগ করুন (বা 9 বিয়োগ করুন, একই ফল); তারপর সব যোগ করুন। মোট ≡ 0 (mod 10) হলে নম্বরটি বৈধ। এটি পুরোপুরি “ওজনযুক্ত যোগফল” নয়, কারণ দ্বিগুণ অঙ্কে একটি ফাংশন বসে: f(d) = 2d (d ≤ 4) আর f(d) = 2d − 9 (d ≥ 5).

13 8 5 2 0 0 7 1 ?2ডান থেকে দ্বিগুণ: 1, 0, 2, 831→2, 0→0, 2→4, 8→16416 → 1 + 6 = 75(2+0+4+7) + (7+0+5+3) = 28628 + ? ≡ 0 ⇒ ? = 2

প্রমাণ: f(0), …, f(9)-এর মান যথাক্রমে 0, 2, 4, 6, 8, 1, 3, 5, 7, 9.

1. (ক) দ্বিগুণ না হওয়া অবস্থানে পার্থক্য d′ − d, যা 10-এর গুণিতক নয়। দ্বিগুণ অবস্থানে পার্থক্য f(d′) − f(d); তালিকায় f-এর দশটি মান সব আলাদা অঙ্ক, অর্থাৎ f হলো {0, …, 9}-এর একটি permutation, তাই f(d′) ≠ f(d) আর পার্থক্য 1 থেকে 9-এর মধ্যে, 10 দিয়ে বিভাজ্য নয়। — f একটি bijection
2. (খ) পাশাপাশি a, b-এর একটি দ্বিগুণ হয়, অন্যটি হয় না। আগে f(a) + b, পরে a + f(b). ভুল ধরা পড়ে না ⇔ f(a) − a ≡ f(b) − b (mod 10). — যোগফলের পার্থক্য
3. g(d) = f(d) − d mod 10 হিসাব করুন: d = 0, …, 9-এ g = 0, 1, 2, 3, 4, 6, 7, 8, 9, 0. দুটি ভিন্ন অঙ্কে g সমান শুধু d = 0 আর d = 9-এ। ∎ — দশটি ক্ষেত্র সরাসরি গোনা

Luhn-এর কৌশলটি চতুর: ওজন 2 সরাসরি নিলে (gcd(2, 10) = 2) একক ভুলও ফসকাত, যেমন 0 → 5 (2 · 5 = 10 ≡ 0). “দুই অঙ্ক যোগ” ধাপটি 2d ≥ 10 হলে 1 যোগ করে হারানো তথ্য ফেরত আনে, আর f-কে permutation বানায়। পদ্ধতিটি IBM-এর বিজ্ঞানী Hans Peter Luhn ১৯৫০-এর দশকে প্রস্তাব করেন; তাঁর patent ১৯৬০ সালে মঞ্জুর হয় বলে উল্লেখ করা হয়। C কোর্সের পর্ব ৪৩-এ এর কোড আছে; এখানে আমরা প্রমাণ আর পরীক্ষা নিয়ে কাজ করছি।

এবার পরীক্ষা। নিচের ব্লক প্রতিটি পদ্ধতিতে ৩০০টি এলোমেলো বৈধ নম্বর বানায়, আর প্রতিটিতে সব একক ভুল আর payload-এর পাশাপাশি সব অদলবদল চালিয়ে দেখে কোনটি ফসকায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random
random.seed(26)                       # fixed seed: same numbers every run
def isbn10_ok(d):                     # weights 10, 9, ..., 1  (mod 11)
    return sum(w * x for w, x in zip(range(10, 0, -1), d)) % 11 == 0

def ean13_ok(d):                      # weights 1, 3, 1, 3, ...  (mod 10)
    return sum(x * (3 if i % 2 else 1) for i, x in enumerate(d)) % 10 == 0

def luhn_ok(d):                       # double every 2nd digit from the right
    s = 0
    for i, x in enumerate(reversed(d)):
        s += (2 * x - 9 if x > 4 else 2 * x) if i % 2 else x
    return s % 10 == 0

def experiment(ok, n, top, trials=300):
    single = s_miss = swaps = 0; missed = set()
    for _ in range(trials):
        d = [random.randrange(10) for _ in range(n - 1)]
        d += [next(c for c in range(top) if ok(d + [c]))]   # add check digit
        for i in range(n):
            for v in range(top if i == n - 1 else 10):
                if v != d[i]:
                    single += 1; s_miss += ok(d[:i] + [v] + d[i + 1:])
        for i in range(n - 2):        # swap two neighbouring payload digits
            if d[i] != d[i + 1]:
                e = d[:]; e[i], e[i + 1] = e[i + 1], e[i]; swaps += 1
                if ok(e): missed.add(tuple(sorted(d[i:i + 2])))
    print(f"  single errors missed {s_miss}/{single}; {swaps} swaps,",
          "missed pairs:", sorted(missed) or "none")

for name, ok, n, top in [("ISBN-10", isbn10_ok, 10, 11),
                         ("EAN-13 ", ean13_ok, 13, 10), ("Luhn-16", luhn_ok, 16, 10)]:
    print(name); experiment(ok, n, top)
print("stepper numbers valid:", isbn10_ok([3,1,4,1,5,9,2,6,5,9]),
      luhn_ok([3,8,5,2,0,0,7,1,2]), ean13_ok([2,0,2,6,1,1,1,0,0,4,2,7,8]))

ISBN-10
  single errors missed 0/27300; 2167 swaps, missed pairs: none
EAN-13 
  single errors missed 0/35100; 2999 swaps, missed pairs: [(0, 5), (1, 6), (2, 7), (3, 8), (4, 9)]
Luhn-16
  single errors missed 0/43200; 3803 swaps, missed pairs: [(0, 9)]
stepper numbers valid: True True True

৪ · Hashing — k mod m, আর কেন m মৌলিক

বাজারঘরের দ্বিতীয় সমস্যা: অনেক key-কে m-টি বালতিতে (bucket) সমানভাবে ভাগ করা। সবচেয়ে সরল hash function হলো h(k) = k mod m: key k যায় k mod m নম্বর বালতিতে। একই বালতিতে দুটি key পড়লে তাকে collision বলে, আর key-এর সংখ্যা বালতির চেয়ে বেশি হলে pigeonhole নীতিতে collision অবশ্যম্ভাবী। লক্ষ্য তাই সমানভাবে ছড়ানো, যাতে প্রতিটি বালতিতে মোটামুটি n/m-টি key থাকে (এই অনুপাত load factor). Hash table-এর গঠন আর কোড DSA কোর্সের পর্ব ৩২-এ; এখানে প্রশ্ন শুধু গাণিতিক: কোন m-এ k mod m ভালো ছড়ায়?

Key সত্যিই এলোমেলো হলে প্রায় যেকোনো m চলে। সমস্যা হয় যখন key-গুলোতে একটি নিয়মিত গঠন থাকে, আর বাস্তবে প্রায় সবসময়ই থাকে। ধরুন বাজারঘরের প্রতিটি গুদাম 8টি করে আইডি আগে থেকে সংরক্ষণ করে, তাই একটি গুদামের অর্ডার আইডি 100000, 100008, 100016, …, অর্থাৎ ধাপ 8. এমন সমান্তর ধারায় (arithmetic progression) k mod m কতটি বালতিতে পড়ে, তা নিচের উপপাদ্য বলে।

প্রমাণ:

1. s + id ≡ s + jd (mod m) ⇔ m ∣ (i − j)d. দুই পাশকে g দিয়ে ভাগ করলে ⇔ (m/g) ∣ (i − j)(d/g). — congruence-এর সংজ্ঞা
2. gcd(m/g, d/g) = 1 (gcd-কে gcd দিয়ে ভাগ করলে সহমৌলিক থাকে, পর্ব ২১). তাই Euclid-এর lemma-র সাধারণ রূপে ⇔ (m/g) ∣ (i − j). — সহমৌলিক উৎপাদক বাদ দেওয়া
3. অর্থাৎ i আর j একই ভাগশেষ দেয় ঠিক তখন, যখন i ≡ j (mod m/g). তাই i = 0, 1, …, m/g − 1 দেয় m/g-টি ভিন্ন মান, আর তারপর ধারা পুনরাবৃত্ত হয়। — ধাপ ১–২
4. g ∣ d আর g ∣ m, তাই প্রতিটি মান ≡ s (mod g). 0 থেকে m − 1-এর মধ্যে এমন ভাগশেষ ঠিক m/g-টি, আর ধাপ ৩-এ আমরা m/g-টি ভিন্ন পেয়েছি, তাই সবগুলোই আসে। ∎ — গণনা

ধাপ 8-এর আইডি mod 64-এ: g = gcd(8, 64) = 8, তাই মাত্র 64/8 = 8টি বালতি ব্যবহৃত হয়, বাকি 56টি খালি, আর প্রতিটি ব্যবহৃত বালতিতে গড়ের আট গুণ চাপ। m = 61 (মৌলিক) নিলে gcd(8, 61) = 1, সব 61টি বালতি সমান ব্যবহৃত। নিচের ছবিতে ছোট সংখ্যায় একই ঘটনা।

উপপাদ্য থেকে m বাছাইয়ের দুটি নিয়ম আসে। প্রথমত, m মৌলিক হলে যেকোনো ধাপ d (যেখানে m ∤ d) সব m-টি বালতি ব্যবহার করে, কারণ gcd(d, m) = 1. দ্বিতীয়ত, m = 2^r হলে k mod m মানে শুধু k-এর বাইনারির শেষ r-টি bit; key-গুলো যদি শুধু উঁচু bit-এ আলাদা হয় (যেমন সবগুলো 1024-এর গুণিতক থেকে 7 বেশি), তবে সবগুলো একই বালতিতে পড়ে। এ কারণেই পাঠ্যবইয়ে division-method hashing-এ “2-এর ঘাতের কাছাকাছি নয় এমন মৌলিক m” বাছার পরামর্শ দেওয়া হয়।

তবে মৌলিক m-ও কোনো জাদু নয়। ধাপ d যদি নিজেই m-এর গুণিতক হয়, বা কেউ ইচ্ছা করে একই বালতির key পাঠায়, তবে যেকোনো স্থির h ভেঙে পড়ে। এর গাণিতিক উত্তর universal hashing: একটি বড় মৌলিক p (p > সব key) নিয়ে প্রোগ্রাম শুরুর সময় এলোমেলোভাবে a ∈ {1, …, p − 1} আর b ∈ {0, …, p − 1} বাছা হয়, আর h_a,b(k) = ((ak + b) mod p) mod m. J. Lawrence Carter আর Mark Wegman ১৯৭০-এর দশকের শেষে (১৯৭৭–৭৯) এই ধারণা দেন; যেকোনো দুটি ভিন্ন key-এর collision-এর সম্ভাবনা বড়জোর 1/m, key যেমনই হোক। প্রমাণের মূলে সেই পুরোনো তথ্য: p মৌলিক বলে k ↦ ak + b mod p একটি bijection.

নিচের ব্লক ধাপ-8 আইডি আর ধাপ-1024 key কয়েকটি m-এ ভাগ করে ব্যবহৃত বালতি আর সবচেয়ে ভরা বালতি দেখায়, একটি universal hash চেষ্টা করে, আর উপপাদ্য ৪.১ ছোট সব m, d-তে মেলায়।

import random
from collections import Counter
from math import gcd

def report(label, keys, m, h=None):
    load = Counter(h(k) if h else k % m for k in keys)
    print(f"{label:<16} m={m:<5} buckets used {len(load):>4}/{m:<5}"
          f" max load {max(load.values()):>3}  (ideal {len(keys) / m:.1f})")

ids = [100000 + 8 * i for i in range(2000)]      # order ids step by 8
for m in (64, 61, 100, 97):
    report("ids step 8", ids, m)

keys = [1024 * i + 7 for i in range(2000)]       # only the high bits differ
for m in (1024, 1031):
    report("keys step 1024", keys, m)

random.seed(26)                                  # one random (a, b): universal family
p = 1_000_003
a, b = random.randrange(1, p), random.randrange(p)
report("universal hash", keys, 1024, lambda k: (a * k + b) % p % 1024)

ok = all(len({(s + i * d) % m for i in range(m)}) == m // gcd(d, m)
         for m in range(1, 60) for d in range(1, 60) for s in range(3))
print("stride theorem holds for all m, d < 60:", ok)
print("p = 1000003 is prime:", all(p % q for q in range(2, int(p ** 0.5) + 1)))

ids step 8       m=64    buckets used    8/64    max load 250  (ideal 31.2)
ids step 8       m=61    buckets used   61/61    max load  33  (ideal 32.8)
ids step 8       m=100   buckets used   25/100   max load  80  (ideal 20.0)
ids step 8       m=97    buckets used   97/97    max load  21  (ideal 20.6)
keys step 1024   m=1024  buckets used    1/1024  max load 2000  (ideal 2.0)
keys step 1024   m=1031  buckets used 1031/1031  max load   2  (ideal 1.9)
universal hash   m=1024  buckets used 1020/1024  max load   3  (ideal 2.0)
stride theorem holds for all m, d < 60: True
p = 1000003 is prime: True

একই উপপাদ্য “বোঝা ছড়ানো”-র অন্য জায়গাতেও খাটে। Double hashing-এ সংঘর্ষ হলে ঘর খোঁজা হয় h, h + d, h + 2d, … mod m ধরে; gcd(d, m) > 1 হলে কিছু খালি ঘর কখনো দেখাই হয় না। আর অর্ডার k-কে ডেলিভারি ভ্যান (k · s) mod v-তে পাঠালে gcd(s, v) = 1 হলেই পরপর v-টি অর্ডার v-টি ভ্যানে একটি করে যায়।

৫ · Pseudorandom সংখ্যা — linear congruential generator

কম্পিউটার একটি নির্দিষ্ট নিয়মে চলে, তাই সে সত্যিকারের এলোমেলো সংখ্যা বানাতে পারে না। সে যা বানায়, তা pseudorandom: একটি সূত্র থেকে আসা সংখ্যার ধারা, যা দেখতে এলোমেলো, কিন্তু শুরুর মান (seed) এক হলে হুবহু একই। সবচেয়ে পুরোনো আর সরল সূত্রটি এই মডিউলের ভাষাতেই লেখা।

এর প্রথম প্রস্তাব D. H. Lehmer-এর, ১৯৪৯ সালের একটি সম্মেলনে (প্রকাশ ১৯৫১), বলে সাধারণত উল্লেখ করা হয়। প্রথম প্রশ্ন: ধারা কতক্ষণ নতুন সংখ্যা দেয়?

প্রমাণ:

1. প্রতিটি x_n ∈ {0, …, m − 1}, মাত্র m-টি মান। x₀, …, x_m এই m + 1টি পদের মধ্যে তাই দুটি সমান: x_i = x_j, i < j ≤ m. — pigeonhole নীতি
2. পরের পদ শুধু আগের পদের ওপর নির্ভর করে, তাই x_i+1 = x_j+1, x_i+2 = x_j+2, …: i-তম পদ থেকে ধারা j − i ≤ m দৈর্ঘ্যের চক্রে ঘোরে। — induction
3. gcd(a, m) = 1 হলে x ↦ ax + c একটি bijection (inverse: x ↦ a⁻¹(x − c)), তাই প্রতিটি পদের আগের পদ অনন্য। x_i = x_j থেকে পিছিয়ে x_i−1 = x_j−1, …, x₀ = x_j−i. ∎ — inverse mod m, পর্ব ২৩

সবচেয়ে ভালো হয় period ঠিক m হলে (“full period”): তখন এক চক্রে 0 থেকে m − 1-এর প্রতিটি মান ঠিক একবার আসে, seed যা-ই হোক। কখন তা হয়, তার পূর্ণ উত্তর আছে।

T. E. Hull আর A. R. Dobell ১৯৬২ সালে এটি প্রকাশ করেন। প্রমাণ এখানে বাদ; এটি Knuth-এর The Art of Computer Programming, খণ্ড ২-এর LCG অধ্যায়ে আছে। তবে একটি দিক সহজেই দেখা যায়: যদি gcd(c, m) = g > 1 আর seed 0 হয়, তবে প্রতিটি পদ g-এর গুণিতক থাকে (a · 0 + c = c, তারপর a · (g-এর গুণিতক) + c), তাই বড়জোর m/g-টি মান আসে, full period অসম্ভব। নিচের stepper শর্তগুলো মেলানো একটি ছোট LCG চালায়।

1m = 16 = 2⁴, a = 5, c = 32gcd(3, 16) = 1; 2 ∣ 4; 4 ∣ 43x₁..x₄  = 6, 1, 8, 114x₅..x₈  = 10, 5, 12, 155x₉..x₁₂ = 14, 9, 0, 36x₁₃..x₁₆ = 2, 13, 4, 7

c = 0 হলে (multiplicative LCG) 0 একটি আটকে থাকা মান (0 → 0), তাই period বড়জোর m − 1. m = p মৌলিক আর seed x₀ ≠ 0 হলে x_n = aⁿx₀ mod p, আর x_n = x₀ ⇔ aⁿ ≡ 1, অর্থাৎ period ঠিক ord_p(a), পর্ব ২৪-এর order (প্রমাণ অনুশীলন ১-এ)। period সবচেয়ে বড়, p − 1, ঠিক তখন যখন a একটি primitive root. Stephen Park আর Keith Miller ১৯৮৮ সালে “minimal standard” হিসেবে m = 2³¹ − 1 (একটি মৌলিক) আর a = 16807 = 7⁵ প্রস্তাব করেন, যেটি mod 2³¹ − 1-এ একটি primitive root; পরে তাঁরা a = 48271 পছন্দ করেন বলে উল্লেখিত।

নিচের ব্লক stepper-এর ধারা ছাপে, কয়েকটি m-এ সব (a, c) জোড়ার period গুনে Hull–Dobell-এর শর্তের সঙ্গে মেলায়, mod 13-এ multiplicative LCG-এর period দেখায়, আর 16807 সত্যিই primitive root কি না পরীক্ষা করে (2³¹ − 2 = 2 · 3² · 7 · 11 · 31 · 151 · 331, আর পর্ব ২৪-এর নিয়মে প্রতিটি মৌলিক উৎপাদক q-তে g^(p−1)/q ≢ 1 দেখতে হয়)।

from math import gcd

def period(a, c, m, seed):            # length of the cycle the sequence falls into
    seen, x, n = {}, seed, 0
    while x not in seen:
        seen[x] = n; x = (a * x + c) % m; n += 1
    return n - seen[x]

x, seq = 7, []
for _ in range(17):
    x = (5 * x + 3) % 16; seq.append(x)
print("x -> (5x + 3) mod 16, seed 7:", seq)

def primes_of(m):
    return [p for p in range(2, m + 1) if m % p == 0 and all(p % q for q in range(2, p))]

def hull_dobell(a, c, m):
    return (gcd(c, m) == 1 and all((a - 1) % p == 0 for p in primes_of(m))
            and (m % 4 != 0 or (a - 1) % 4 == 0))

fulls = {}
for m in (16, 10, 12, 30, 81):
    full = [(a, c) for a in range(m) for c in range(m) if period(a, c, m, 0) == m]
    same = all((period(a, c, m, 0) == m) == hull_dobell(a, c, m)
               for a in range(m) for c in range(m))
    fulls[m] = full
    print(f"m={m:<3} full-period (a, c) pairs: {len(full):>4}   Hull-Dobell agrees: {same}")
print("m = 10, all full-period (a, c):", fulls[10])

print("c = 0, m = 13, seed 1, period for a = 1..12:",
      [period(a, 0, 13, 1) for a in range(1, 13)])
M = 2**31 - 1                         # Park-Miller: a = 16807 = 7^5
print("16807 primitive root mod 2^31-1:",
      all(pow(16807, (M - 1) // q, M) != 1 for q in (2, 3, 7, 11, 31, 151, 331)))

x -> (5x + 3) mod 16, seed 7: [6, 1, 8, 11, 10, 5, 12, 15, 14, 9, 0, 3, 2, 13, 4, 7, 6]
m=16  full-period (a, c) pairs:   32   Hull-Dobell agrees: True
m=10  full-period (a, c) pairs:    4   Hull-Dobell agrees: True
m=12  full-period (a, c) pairs:    4   Hull-Dobell agrees: True
m=30  full-period (a, c) pairs:    8   Hull-Dobell agrees: True
m=81  full-period (a, c) pairs: 1458   Hull-Dobell agrees: True
m = 10, all full-period (a, c): [(1, 1), (1, 3), (1, 7), (1, 9)]
c = 0, m = 13, seed 1, period for a = 1..12: [1, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2]
16807 primitive root mod 2^31-1: True

৬ · খারাপ generator আর নিরাপত্তা — RANDU আর অনুমানযোগ্যতা

Full period যথেষ্ট নয়: পরপর মানগুলোর মধ্যে সহজ সম্পর্ক থাকলে generator খারাপ। সবচেয়ে বিখ্যাত উদাহরণ RANDU: m = 2³¹, a = 65539 = 2¹⁶ + 3, c = 0 (seed বিজোড়)। এটি ১৯৬০-এর দশকে IBM-এর বৈজ্ঞানিক লাইব্রেরিতে বহুল ব্যবহৃত হয়েছিল বলে উল্লেখ করা হয়।

প্রমাণ: M = 2³¹ আর a = 2¹⁶ + 3.

1. a² = 2³² + 6 · 2¹⁶ + 9. 2³² = 2 · M ≡ 0, তাই a² ≡ 6 · 2¹⁶ + 9 (mod M). — বর্গের সূত্র
2. 6 · 2¹⁶ = 6(a − 3) = 6a − 18, তাই a² ≡ 6a − 18 + 9 = 6a − 9 (mod M). — বদলে বসানো
3. x_k+2 ≡ a²x_k ≡ (6a − 9)x_k = 6(a x_k) − 9x_k ≡ 6x_k+1 − 9x_k (mod M). ∎ — গুণ congruence মানে

এর জ্যামিতিক অর্থ ভয়ংকর। u = x_k/M, v = x_k+1/M, w = x_k+2/M নিলে তিনটিই 0 থেকে 1-এর মধ্যে, আর উপপাদ্য বলে 9u − 6v + w একটি পূর্ণসংখ্যা। এর মান −6 < 9u − 6v + w < 10, তাই সম্ভাব্য পূর্ণসংখ্যা মাত্র 15টি (−5 থেকে 9). অর্থাৎ (u, v, w) বিন্দুগুলো একটি ঘনকের ভেতরে ছড়িয়ে না থেকে মাত্র 15টি সমান্তরাল সমতলে পড়ে থাকে। ত্রিমাত্রিক সিমুলেশনে (যেমন একটি বাক্সে কণার অবস্থান) ঘনকের বেশিরভাগ জায়গায় কখনো বিন্দু পড়ে না। George Marsaglia ১৯৬৮ সালে “Random numbers fall mainly in the planes” প্রবন্ধে দেখান, প্রতিটি multiplicative LCG-এর পরপর বিন্দু কিছু সমতলে পড়ে; RANDU-তে সংখ্যাটি অস্বাভাবিক কম। এই সমতলগুলোর দূরত্ব মাপার পরীক্ষাকে spectral test বলে।

অনুমানযোগ্যতা: তিনটি সংখ্যাই যথেষ্ট

দ্বিতীয় সমস্যাটি নিরাপত্তার। ধরুন বাজারঘর লটারির বিজয়ী বাছে একটি LCG দিয়ে, যার m প্রকাশ্য (ধরুন একটি মৌলিক p), কিন্তু a আর c গোপন। কেউ পরপর তিনটি আউটপুট x₀, x₁, x₂ দেখলেন। তাহলে

x₂ − x₁ ≡ a(x₁ − x₀) (mod p)

কারণ c বিয়োগে বাদ যায়। x₁ ≠ x₀ হলে x₁ − x₀-এর inverse mod p আছে, তাই a = (x₂ − x₁)(x₁ − x₀)⁻¹ mod p, আর তারপর c = x₁ − a x₀ mod p. এরপর পরের সব “এলোমেলো” সংখ্যা জানা। m অজানা হলেও কয়েকটি বেশি আউটপুট আর gcd দিয়ে তা বের করার পরিচিত কৌশল আছে।

নিচের ব্লক RANDU-তে উপপাদ্য ৬.১ আর সমতলগুলো পরীক্ষা করে, তারপর তিনটি আউটপুট থেকে একটি LCG-এর গোপন a, c বের করে।

from collections import Counter

M = 2**31                              # RANDU: x -> 65539 x mod 2^31
xs, x = [], 1
for _ in range(30000):
    x = 65539 * x % M; xs.append(x)
print("RANDU from seed 1:", xs[:5])
bad = sum((xs[k + 2] - 6 * xs[k + 1] + 9 * xs[k]) % M != 0 for k in range(len(xs) - 2))
print("triples with x[k+2] != 6x[k+1] - 9x[k] (mod 2^31):", bad)

# scaled to u, v, w in [0, 1): 9u - 6v + w is always a whole number k
planes = Counter((9 * xs[k] - 6 * xs[k + 1] + xs[k + 2]) // M
                 for k in range(0, len(xs) - 2, 3))
print("planes 9u - 6v + w = k used by 10000 triples:", sorted(planes))
print("smallest / largest plane count:", min(planes.values()), max(planes.values()))

# predicting an LCG: m is public, a and c are secret
m = 2**31 - 1                          # a prime modulus
a, c = 48271, 12345                    # the secret parameters
out = [2026]
for _ in range(8):
    out.append((a * out[-1] + c) % m)
x0, x1, x2 = out[:3]                   # an attacker sees only these three
a_hat = (x2 - x1) * pow(x1 - x0, -1, m) % m
c_hat = (x1 - a_hat * x0) % m
pred, y = [], x2
for _ in range(6):
    y = (a_hat * y + c_hat) % m; pred.append(y)
print("recovered a, c:", a_hat, c_hat)
print("next six outputs predicted correctly:", pred == out[3:])

RANDU from seed 1: [65539, 393225, 1769499, 7077969, 26542323]
triples with x[k+2] != 6x[k+1] - 9x[k] (mod 2^31): 0
planes 9u - 6v + w = k used by 10000 triples: [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
smallest / largest plane count: 96 1152
recovered a, c: 48271 12345
next six outputs predicted correctly: True

৭ · আরও দুটি প্রয়োগ — CRC আর round-robin সময়সূচি

CRC: mod 2-এ polynomial-এর ভাগশেষ

নেটওয়ার্কে বা ডিস্কে ভুল প্রায়ই আসে bit-এর গুচ্ছে (burst), যেমন বৈদ্যুতিক গোলযোগে টানা কয়েকটি bit উল্টে যাওয়া। সেখানে ব্যবহৃত হয় CRC (cyclic redundancy check), যার গণিত হলো ভাগশেষ, তবে সংখ্যার নয়, polynomial-এর। bit-এর ক্রম 1101-কে পড়া হয় x³ + x² + 1 হিসেবে, আর সহগগুলো mod 2-এ চলে: 1 + 1 = 0, অর্থাৎ যোগ আর বিয়োগ দুটোই XOR.

প্রেরক ও প্রাপক একটি generator polynomial আগে থেকে ঠিক করেন, ধরুন G(x) = x³ + x + 1 (bit-এ 1011). বার্তা M = 1101-এর পেছনে deg G = 3টি শূন্য বসিয়ে 1101000 বানানো হয়, আর একে 1011 দিয়ে mod 2-এ লম্বা ভাগ করা হয়: প্রতি ধাপে প্রথম 1-এর নিচে 1011 বসিয়ে XOR. ধাপগুলো হলো 1101000 → 0110000 → 0011100 → 0001010 → 0000001, অর্থাৎ ভাগশেষ 001. পাঠানো হয় 1101 001. প্রাপক পুরো 1101001-কে 1011 দিয়ে ভাগ করেন; ভাগশেষ 000 হলে ধরে নেওয়া হয় ভুল নেই (আমাদের scratch হিসাবেও ঠিক 000). যুক্তিটি পূর্ণসংখ্যার check digit-এর মতোই: পাঠানো polynomial-টি G-এর গুণিতক, আর ভুল E যোগ হলে ধরা পড়ে না ঠিক তখন, যখন G ∣ E. ভালো G বাছলে সব একক bit-এর ভুল আর deg G-এর সমান বা ছোট দৈর্ঘ্যের সব burst ধরা পড়ে।

CRC-এর ধারণা W. Wesley Peterson ১৯৬১ সালে প্রকাশ করেন বলে উল্লেখ করা হয়। Ethernet frame-এর CRC-32-সহ বাস্তব প্রয়োগ Computer Networks কোর্সের পর্ব ০৯-এ আছে, আর ভুল শুধু ধরা নয়, সারিয়ে তোলার গণিত পর্ব ৭২ “Error-correcting code — parity, Hamming code আর Hamming distance”-এ আসবে।

Round-robin: সবার সঙ্গে সবার একবার দেখা

বাজারঘরের কর্মীদের ৮টি দল নিয়ে একটি ক্রিকেট টুর্নামেন্ট হবে। প্রতিটি দল অন্য প্রতিটির সঙ্গে ঠিক একবার খেলবে, আর প্রতি রাউন্ডে প্রতিটি দল ঠিক একটি ম্যাচ খেলবে। মোট ম্যাচ C(8, 2) = 28, প্রতি রাউন্ডে 4টি, তাই 7টি রাউন্ড লাগবে। সাজানো যায় mod 7-এর যোগ দিয়ে, এক ধরনের round-robin নিয়মে।

প্রমাণ:

1. রাউন্ড r-এ দল i-এর প্রতিপক্ষ j ≡ r − i (mod 7), যা অনন্য। j = i হয় ঠিক তখন, যখন 2i ≡ r. 2-এর inverse mod 7 হলো 4 (2 · 4 = 8 ≡ 1), তাই এমন i ঠিক একটি: i ≡ 4r. সে দল ∞-এর সঙ্গে খেলে, বাকি ছয়টি দল তিন জোড়ায় ভাগ হয়। — inverse mod 7
2. দুটি দল i ≠ j (দুটিই ∞ নয়) খেলে শুধু সেই রাউন্ডে, যেখানে r ≡ i + j (mod 7): ঠিক একটি রাউন্ড। — r অনন্যভাবে নির্ধারিত
3. দল i আর ∞ খেলে সেই রাউন্ডে, যেখানে r ≡ 2i (mod 7): আবার ঠিক একটি। মোট 7 · 4 = 28 = C(8, 2) ম্যাচ, সব জোড়া একবার করে। ∎ — গণনা

যেকোনো জোড় n দলে একই নিয়ম mod n − 1-এ চলে (n − 1 বিজোড় বলে 2-এর inverse থাকে); বিজোড় n হলে একটি কাল্পনিক দল যোগ করে তার প্রতিপক্ষকে বিশ্রাম দেওয়া হয়। CPU scheduling-এর round robin (Operating Systems কোর্সের পর্ব ১৮) একই পালাক্রম: সময়-খণ্ড t-তে চলে প্রক্রিয়া t mod n. আর প্রতি 7 দিনে ও প্রতি 11 দিনে আসা দুটি ডেলিভারি একই দিনে পড়ে প্রতি lcm(7, 11) = 77 দিনে, কোন দিনে তা CRT বলে দেয় (পর্ব ২২ ও ২৩)।

৮ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই বিষয়ের যে ধাঁচের অঙ্ক আসে, তার তিনটি পূর্ণ সমাধান। প্রতিটি সংখ্যা scratch-এ Python দিয়ে মেলানো।

অঙ্ক ১: ISBN-10 নম্বর 2-71?-28182-0-এর মুছে যাওয়া অঙ্কটি কী?

1. ওজন 10, 9, …, 1. অজানা অঙ্ক x চতুর্থ অবস্থানে, তার ওজন 7. বাকি নয়টি অবস্থানের গুণফল 10·2, 9·7, 8·1, 6·2, 5·8, 4·1, 3·8, 2·2, 1·0 = 20, 63, 8, 12, 40, 4, 24, 4, 0; যোগ 175 = 11 · 15 + 10, অর্থাৎ 175 ≡ 10 (mod 11).
2. শর্ত: 175 + 7x ≡ 0, অর্থাৎ 7x ≡ −10 ≡ 1 (mod 11). তাই x হলো 7-এর inverse mod 11.
3. 7 · 8 = 56 = 5 · 11 + 1, তাই x = 8. পূর্ণ নম্বর 2-718-28182-0, আর যাচাইয়ে মোট 175 + 56 = 231 = 11 · 21 ✓.

অঙ্ক ২: x → (13x + 7) mod 36-এর period কত?

1. c = 7 ≠ 0, তাই Hull–Dobell. 36 = 2² · 3², মৌলিক উৎপাদক 2 আর 3.
2. gcd(7, 36) = 1 ✓. a − 1 = 12, আর 2 ∣ 12, 3 ∣ 12 ✓. 4 ∣ 36, আর 4 ∣ 12 ✓.
3. তিন শর্তই মেলে, তাই period 36 (প্রতিটি seed-এ)। তুলনায় x → (11x + 5) mod 100-এ a − 1 = 10, আর 4 ∣ 100 কিন্তু 4 ∤ 10, তাই full period নয় (seed অনুযায়ী period 10 বা 2).

অঙ্ক ৩: key 5, 17, 29, 41, … (ধাপ 12) mod 18-এ কয়টি বালতিতে পড়ে, কোনগুলোতে?

1. g = gcd(12, 18) = 6. উপপাদ্য ৪.১-এ বালতির সংখ্যা 18/6 = 3.
2. বালতিগুলো সেই r, যেখানে r ≡ 5 (mod 6): 5, 11, 17. (5, 17, 29 ≡ 11, 41 ≡ 5, …)
3. m = 19 (মৌলিক) নিলে gcd(12, 19) = 1, সব 19টি বালতি ব্যবহৃত হতো।

প্রমাণের ভুল ধরুন: “gcd(c, m) = 1 হলেই full period”

একজন লিখলেন: “দাবি: gcd(a, m) = 1 আর gcd(c, m) = 1 হলে x → (ax + c) mod m-এর period m. প্রমাণ: gcd(a, m) = 1, তাই ফাংশনটি {0, …, m − 1}-এর একটি bijection. Bijection কোনো মান বাদ দেয় না, তাই ধারা সব m-টি মান ছুঁয়ে যায়, আর period m. ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: “bijection কোনো মান বাদ দেয় না” কথাটি ফাংশনের প্রতিচ্ছবি সম্পর্কে সত্য, কিন্তু একটি নির্দিষ্ট seed থেকে বারবার লাগালে যে ধারা আসে, তা সম্পর্কে নয়। একটি সসীম সেটের bijection সেটটিকে কয়েকটি আলাদা চক্রে ভাগ করে (উপপাদ্য ৫.২), আর ধারা শুধু seed-এর নিজের চক্রে ঘোরে। একটি counterexample: m = 8, a = 3, c = 1. gcd(3, 8) = gcd(1, 8) = 1, তবু seed 0 থেকে ধারা 0, 1, 4, 5, 0, …, period 4. Hull–Dobell-এর শর্ত ৩ ভেঙেছে: 4 ∣ 8 কিন্তু 4 ∤ a − 1 = 2. সঠিক বক্তব্য Hull–Dobell-এর তিন শর্ত।

৯ · AI-এর যুগে — check digit, hash আর random-এর দাবি যাচাই

AI সহকারী এই বিষয়ে চটপটে উত্তর দেয়, কিন্তু কয়েকটি নির্দিষ্ট জায়গায় নিয়মিত ভুল করে। এগুলো চেনা থাকলে ধরতে এক মিনিট লাগে।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Check digit-সহ পূর্ণ নম্বরটি নিজের লেখা পরীক্ষকে বৈধ এসেছে
• “সব ভুল ধরে” দাবিটি সব একক ভুল আর সব অদলবদল brute force করে পরীক্ষা করেছি
• ব্যবহৃত উপপাদ্যের প্রতিটি শর্ত (মৌলিক, gcd = 1, 4 ∣ m) এই সংখ্যায় নিজে মিলিয়েছি
• প্রমাণে “শূন্য নয়” থেকে “m দিয়ে বিভাজ্য নয়”-এ লাফ নেই, আর converse নিঃশব্দে ঢোকেনি
• নিরাপত্তার কাজে প্রস্তাবিত random উৎসটি CSPRNG কি না দেখেছি
• ইতিহাসের সাল, নাম আর উল্লেখ করা প্রবন্ধ বিশ্বস্ত উৎসে মিলিয়েছি

এই পর্বের প্রায় প্রতিটি দাবি দশটি অঙ্ক বা ছোট m-এ এক সেকেন্ডে brute force করা যায়; AI-এর “সবসময়” বা “কখনো না” দাবি পেলে আগে ছোট ক্ষেত্রে counterexample খুঁজুন।