Ring আর field — modular ring, polynomial আর GF(2ⁿ)

১ · Ring কী — যোগ আর গুণের একটি জগৎ

আগের পর্ব ৭০ “Group — symmetry, cyclic group আর Lagrange-এর উপপাদ্য”-এ একটি অপারেশনের জগৎ, অর্থাৎ group দেখেছেন। Ring-এ অপারেশন দুটি, আর তাদের মধ্যে একটি সেতু: বণ্টন বিধি।

খেয়াল করুন, গুণের inverse চাওয়া হয়নি। কিছু বইয়ে 1 থাকা বাধ্যতামূলক নয়; আমরা এই কোর্সে 1-সহ ring ধরছি, তাই অন্য বই পড়ার সময় সংজ্ঞাটি মিলিয়ে নেবেন। চারটি উদাহরণ:

• ℤ: সাধারণ পূর্ণসংখ্যা, commutative ring. ℚ, ℝ-ও ring.
• ℤ_n = {0, 1, …, n − 1}: যোগ আর গুণের পর mod n (পর্ব ২২-এর ℤ_n). Commutative ring, n উপাদানের।
• R[x]: কোনো commutative ring R-এর সহগের সব polynomial, সাধারণ নিয়মে যোগ-গুণ। একে polynomial ring বলে; §৩ থেকে এটিই মূল চরিত্র।
• M₂(ℝ): বাস্তব সংখ্যার সব 2 × 2 matrix, matrix গুণ দিয়ে (পর্ব ১৯)। এটি ring, কিন্তু commutative নয়: A = [[0, 1], [0, 0]] আর B = [[0, 0], [1, 0]] নিলে AB = [[1, 0], [0, 0]], অথচ BA = [[0, 0], [0, 1]].

Axiom থেকে স্কুলের কিছু “স্বাভাবিক” নিয়ম প্রমাণ করা যায়। এগুলো ধরে নেওয়া যায় না, কারণ অদ্ভুত ring-এও এদের সত্য হতে হবে।

1. (ক) 0 + 0 = 0, তাই a · 0 = a · (0 + 0) = a · 0 + a · 0. — বণ্টন বিধি
2. দুই দিকে −(a · 0) যোগ করলে 0 = a · 0. 0 · a-এর জন্য একই যুক্তি ডান দিকের বণ্টন দিয়ে। — যোগের inverse
3. (খ) ab + (−a)b = (a + (−a))b = 0 · b = 0, তাই (−a)b হলো ab-এর যোগের inverse, অর্থাৎ −(ab). — বণ্টন আর (ক)
4. (গ) (খ)-তে a-এর জায়গায় 1 আর b-এর জায়গায় a বসান: (−1)a = −(1 · a) = −a. ∎

২ · Unit, zero divisor, integral domain আর field

Ring-এ ভাগ সবসময় চলে না। কোন উপাদান দিয়ে “ভাগ” করা যায়, সেটি প্রথম প্রশ্ন।

ℤ-এ unit শুধু 1 আর −1, আর কোনো zero divisor নেই: ℤ integral domain কিন্তু field নয়। ℤ₁₂-এ ছবিটি অন্যরকম। Unit চারটি: 1, 5, 7, 11, আর মজার ব্যাপার, প্রতিটি নিজেরই inverse (5 · 5 = 25 ≡ 1, 7 · 7 = 49 ≡ 1, 11 · 11 = 121 ≡ 1). বাকি সাতটি অশূন্য উপাদান 2, 3, 4, 6, 8, 9, 10 সবাই zero divisor, যেমন 3 · 4 = 12 ≡ 0 আর 8 · 3 = 24 ≡ 0. মাঝামাঝি কেউ নেই। এটি কাকতালীয় নয়।

1. gcd(a, n) = 1 হলে পর্ব ২১-এর Bézout থেকে sa + tn = 1, তাই mod n-এ sa ≡ 1: s হলো a-এর inverse. — Bézout
2. d > 1 হলে b = n/d নিন। 1 ≤ b < n, তাই b ≢ 0. — d ≥ 2
3. ab = (a/d) · n, কারণ d ∣ a; তাই ab ≡ 0 (mod n), আর a zero divisor. ∎ — বিভাজ্যতা

বিশেষ করে ℤ_n-এ unit-এর সংখ্যা ঠিক φ(n) (পর্ব ২৪)। একটি unit কখনো zero divisor হতে পারে না: ab = 1 আর ac = 0 হলে c = (ba)c = b(ac) = 0. ফলে n মৌলিক হলে সব অশূন্য উপাদান unit, আর ℤ_n field; n যৌগিক হলে zero divisor আছে, field নয়। এই “ℤ_n field ⇔ n মৌলিক” উপপাদ্যের পূর্ণ প্রমাণ পর্ব ৩০-এ দেখেছেন; এখানে আমরা তার পেছনের সাধারণ কারণটি খুঁজব।

Matrix-এর ring-এও একই দুই দল দেখা যায়, তবে commutative না হওয়ায় একটু সাবধানে। M₂(ℝ)-এ A একটি unit (উল্টানো যায়) ঠিক তখন, যখন det A ≠ 0. আর det A = 0 এমন অশূন্য A-এর জন্য এমন অশূন্য B পাওয়া যায় যাতে AB = 0: §১-এর A = [[0, 1], [0, 0]] নিজেই A · A = 0 দেয়। অর্থাৎ শূন্য নয় এমন একটি উপাদানের বর্গ শূন্য, যা সংখ্যার জগতে কল্পনাও করা যায় না।

Integral domain-এর সবচেয়ে কাজের গুণ হলো কাটাকাটি (cancellation): a ≠ 0 আর ab = ac হলে a(b − c) = 0, zero divisor নেই বলে b − c = 0, অর্থাৎ b = c. স্কুলে “দুই দিক থেকে a কেটে দিন” যে নিয়ম মানতেন, তা আসলে এই উপপাদ্য। ℤ₁₂-এ এটি ভাঙে: 3 · 4 = 3 · 8 (দুটোই 0), অথচ 4 ≠ 8.

1. D সসীম integral domain, a ∈ D অশূন্য। ফাংশন m_a: D → D, m_a(x) = ax সংজ্ঞায়িত করুন। — গুণের map
2. m_a one-to-one: ax = ay হলে cancellation দিয়ে x = y. — zero divisor নেই
3. D সসীম, আর সসীম সেট থেকে নিজের ভেতরে one-to-one ফাংশন onto-ও (পর্ব ৩২-এর pigeonhole যুক্তি)। — সসীমতা
4. তাই কোনো b-এর জন্য m_a(b) = ab = 1, অর্থাৎ a একটি unit. সব অশূন্য a-এর জন্য এটি সত্য, তাই D একটি field. ∎

“সসীম” শর্তটি জরুরি: ℤ integral domain, কিন্তু অসীম, আর তার m₂(x) = 2x onto নয় (বিজোড় সংখ্যা বাদ পড়ে)। প্রমাণটি আরও একটি জিনিস দেখায়: ℤ_p (p মৌলিক) field, কারণ সেখানে ab ≡ 0 হলে p ∣ ab, আর Euclid-এর lemma দিয়ে p ∣ a বা p ∣ b. নিচের ছবিটি চারটি শ্রেণির সম্পর্ক দেখায়।

৩ · Polynomial ring F[x] — ভাগশেষসহ ভাগ

এখন থেকে F একটি field (প্রায়ই ℤ_p, যাকে GF(p)-ও লেখা হয়)। F[x]-এর একটি উপাদান f(x) = a_dx^d + ⋯ + a₁x + a₀, যেখানে a_d ≠ 0 হলে d হলো f-এর ঘাত (deg f), আর a_d leading coefficient. Leading coefficient 1 হলে f monic. শূন্য polynomial-এর ঘাত সংজ্ঞায়িত নয়।

পূর্ণসংখ্যায় সবচেয়ে কাজের হাতিয়ার ছিল division algorithm (পর্ব ২০): n = qd + r, 0 ≤ r < d. Polynomial-এ “ছোট” মানে ছোট ঘাত। প্রমাণে একটি তথ্য লাগবে: F integral domain বলে দুই অশূন্য polynomial-এর leading coefficient-এর গুণফল অশূন্য, তাই deg(uv) = deg u + deg v.

1. অস্তিত্ব, deg f-এর ওপর strong induction. f = 0 বা deg f < deg g হলে q = 0, r = f. — ভিত্তি
2. নইলে deg f = m ≥ n = deg g, আর f-এর leading coefficient a, g-এর b. b ≠ 0 আর F field, তাই b⁻¹ আছে। f₁ = f − (ab⁻¹)x^m−ng নিন; x^m-এর পদ কেটে যায়, তাই f₁ = 0 বা deg f₁ < m. — সর্বোচ্চ পদ মোছা
3. Hypothesis থেকে f₁ = q₁g + r, আর deg r < n (বা r = 0). তাহলে f = (q₁ + ab⁻¹x^m−n)g + r. — inductive step
4. অনন্যতা: q₁g + r₁ = q₂g + r₂ হলে (q₁ − q₂)g = r₂ − r₁. q₁ ≠ q₂ হলে বাঁ দিকের ঘাত ≥ deg g, কিন্তু ডান দিকের ঘাত < deg g. বিরোধ, তাই q₁ = q₂, আর তখন r₁ = r₂. ∎ — deg(uv) = deg u + deg v

ধাপ ২-এ b⁻¹ লেগেছে, তাই field জরুরি। ℤ[x]-এ x²-কে 2x দিয়ে ভাগ করে ভাগশেষ ঘাত 1-এর কম রাখা যায় না: ভাগফল x/2 হতো, যা ℤ[x]-এ নেই। তবে g monic হলে যেকোনো commutative ring-এ ভাগ চলে, যেমন ℤ[x]-এ x − c দিয়ে।

GF(2)-এ হিসাব সবচেয়ে সহজ: সহগ 0 বা 1, আর 1 + 1 = 0, তাই বিয়োগ মানে যোগ, আর bit-এর ভাষায় XOR. একটি polynomial-কে তার সহগের bit-এ লেখা যায়: x³ + x + 1 = 1011. নিচের stepper এভাবে একটি লম্বা ভাগ করে, ঠিক পর্ব ২৬-এর CRC-এর মতো, তবে এবার ভাগফলও লিখে রাখি।

1f = 1101 0011, g = 10112⊕ x⁴·g = 1011 00003⊕ x³·g = 101 10004⊕ x²·g = 10 11005⊕ x·g  = 1 01106q = 11110, r = 1

বাজারঘরের দৃষ্টিতে এই ভাগের মানে কী? ধরুন ঢাকা অফিস থেকে চট্টগ্রাম গুদামে একটি অর্ডারের bit-ক্রম যাচ্ছে। প্রেরক এমনভাবে কয়েকটি bit জুড়ে দেন যাতে পুরো ক্রমের polynomial g-এর গুণিতক হয়। গুদামের কম্পিউটার শুধু এই লম্বা ভাগটি চালায়: ভাগশেষ 0 হলে ক্রমটি গ্রহণ করে, অন্য কিছু হলে আবার পাঠাতে বলে। পুরো কাজটি XOR আর shift, যা হার্ডওয়্যারে কয়েকটি গেট দিয়েই করা যায়; এজন্যই Ethernet-এর মতো অনেক নেটওয়ার্কের frame-এ এমন একটি পরীক্ষা থাকে।

৪ · Polynomial-এর gcd — Euclid আবার

Division algorithm থাকলেই Euclid চলে, কারণ পর্ব ২১-এর প্রমাণে শুধু এটুকুই লেগেছিল। F[x]-এ f আর g-এর gcd হলো এমন monic polynomial d, যা দুটিকেই ভাগ করে আর তাদের প্রতিটি সাধারণ ভাজক d-কেও ভাগ করে।

প্রমাণ পূর্ণসংখ্যার মতো হুবহু: d ∣ f আর d ∣ g হলে d ∣ f − qg = r; উল্টোভাবে d ∣ g আর d ∣ r হলে d ∣ qg + r = f. ঘাত একটি অঋণাত্মক পূর্ণসংখ্যা, আর প্রতি ধাপে কঠোরভাবে কমে, তাই প্রক্রিয়া থামে (পর্ব ১১-এর well-ordering). Bézout-এর s, t পেছনে হেঁটে আসে, extended Euclid-এর মতোই। ∎ এবার GF(3)-এ একটি উদাহরণ, যেখানে সহগ 0, 1, 2 আর হিসাব mod 3; একমাত্র নতুন জিনিস হলো leading coefficient 2 হলে তার inverse লাগে, আর 2 · 2 = 4 ≡ 1, তাই 2⁻¹ = 2.

1a = x⁴+2x³+x²+2x+22b = x³+2x²+2x+13a = x·b + (2x²+x+2)4b = 2x·r₁ + (x+1)5r₁ = (2x+2)(x+1) + 06gcd = x + 1

নিচের ব্লক GF(p)[x]-এর জন্য ভাগ আর gcd লেখে, দুই stepper-এর উত্তর মেলায়, আর পরের অংশের একটি চমক আগে দেখিয়ে রাখে। Polynomial রাখা হয়েছে সহগের list-এ, ছোট ঘাত আগে: [1, 1, 0, 1] মানে 1 + x + x³. Python-এর pow(b, -1, p) সরাসরি mod p-এর inverse দেয়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

def trim(a):                              # coefficients, lowest degree first
    while a and a[-1] == 0: a = a[:-1]
    return a
def pdivmod(a, b, p):                     # division algorithm in GF(p)[x]
    a, q = trim([c % p for c in a]), [0] * len(a)
    inv = pow(b[-1], -1, p)               # leading coefficient must be a unit
    while len(a) >= len(b):
        s, c = len(a) - len(b), a[-1] * inv % p
        q[s] = c
        a = trim([(x - c * b[i - s]) % p if 0 <= i - s < len(b) else x
                  for i, x in enumerate(a)])
    return trim(q), a
def pgcd(a, b, p):                        # Euclid, then make it monic
    while trim(b):
        a, b = b, pdivmod(a, b, p)[1]
    return [c * pow(a[-1], -1, p) % p for c in a]
def mul(a, b, p):
    r = [0] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        for j, y in enumerate(b): r[i + j] = (r[i + j] + x * y) % p
    return trim(r)
def add(a, b, p):
    n = max(len(a), len(b)); a, b = a + [0]*(n - len(a)), b + [0]*(n - len(b))
    return trim([(x + y) % p for x, y in zip(a, b)])
def show(a):                              # [1, 0, 2] -> "2x^2 + 1"
    t = [(str(c) if c > 1 or i == 0 else "") + ("x^%d" % i if i > 1 else "x" * i)
         for i, c in reversed(list(enumerate(a))) if c]
    return " + ".join(t) or "0"
f, g = [1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 0, 1]   # x^7+x^6+x^4+x+1, x^3+x+1
q, r = pdivmod(f, g, 2); ok = add(mul(q, g, 2), r, 2) == f
print("GF(2): q =", show(q), "| r =", show(r), "| q*g + r == f:", ok)
a, b = [2, 2, 1, 2, 1], [1, 2, 2, 1]             # over GF(3)
print("GF(3): gcd(", show(a), ",", show(b), ") =", show(pgcd(a, b, 3)))
for n in (7, 8, 15):                             # roots of x^2 - 1 in Z_n
    print(f"x^2 - 1 in Z_{n}: roots", [x for x in range(n) if (x * x - 1) % n == 0])

GF(2): q = x^4 + x^3 + x^2 + x | r = 1 | q*g + r == f: True
GF(3): gcd( x^4 + 2x^3 + x^2 + 2x + 2 , x^3 + 2x^2 + 2x + 1 ) = x + 1
x^2 - 1 in Z_7: roots [1, 6]
x^2 - 1 in Z_8: roots [1, 3, 5, 7]
x^2 - 1 in Z_15: roots [1, 4, 11, 14]

৫ · Root, factor আর irreducible polynomial

c ∈ F হলো f-এর root, যদি f(c) = 0. ভাগের উপপাদ্যের প্রথম ফল:

প্রমাণ: f-কে x − c দিয়ে ভাগ করুন: f = q · (x − c) + r, যেখানে r = 0 বা deg r < 1, অর্থাৎ r একটি ধ্রুবক। x = c বসালে f(c) = r. তাই f(c) = 0 ⇔ r = 0 ⇔ (x − c) ∣ f. ∎

1. d-এর ওপর induction. d = 0: f একটি অশূন্য ধ্রুবক, কোনো root নেই। — ভিত্তি
2. d ≥ 1 আর f-এর কোনো root না থাকলে কিছু প্রমাণের নেই। নইলে একটি root c নিন; factor theorem থেকে f = (x − c)g, আর deg g = d − 1. — উপপাদ্য ৫.১
3. c′ ≠ c আরেকটি root হলে 0 = f(c′) = (c′ − c) · g(c′). c′ − c ≠ 0, আর zero divisor নেই, তাই g(c′) = 0. — integral domain
4. তাই f-এর root-এর সেট ⊆ {c} ∪ (g-এর root), আর hypothesis থেকে g-এর root বড়জোর d − 1টি। মোট বড়জোর 1 + (d − 1) = d. ∎

ধাপ ৩-ই সব। ℤ₈-এ x² − 1 = (x − 1)(x + 1), আর x = 3 বসালে (3 − 1)(3 + 1) = 2 · 4 = 8 ≡ 0, অথচ কোনো উৎপাদকই 0 নয়। ℤ₈-এর zero divisor 2 আর 4 ধাপ ৩-কে ভেঙে দেয়, ফলে চারটি root: 1, 3, 5, 7. আরেকটি অদ্ভুত ফল: ℤ₈[x]-এ x² − 1 = (x − 1)(x + 1) = (x − 3)(x + 3), অর্থাৎ উৎপাদকে ভাঙা আর অনন্য নয়। একটি সতর্কতা: উপপাদ্যটি ভিন্ন root গোনে; GF(2)-এ x² + 1 = (x + 1)²-এর root একটিই (1), তবু ঘাত 2.

প্রমাণ: f = uv, দুটিরই ঘাত ≥ 1 হলে ঘাতের যোগ 2 বা 3, তাই একটির ঘাত ঠিক 1, ধরুন u = ax + b, a ≠ 0. তখন c = −b · a⁻¹ হলো u-এর, তাই f-এর root. উল্টোভাবে root c থাকলে (x − c) ∣ f, আর f ভেঙে যায়। ∎ ঘাত 4-এ এই সহজ পরীক্ষা ভুল: GF(2)-এ x⁴ + x² + 1-এর কোনো root নেই (x = 0 আর x = 1-এ মান 1), অথচ এটি (x² + x + 1)². Irreducible polynomial ℤ-এর মৌলিক সংখ্যার ভূমিকা নেয়: F[x]-এ প্রতিটি monic polynomial monic irreducible-দের গুণফলে অনন্যভাবে ভাঙে, ঠিক পূর্ণসংখ্যার মতো।

৬ · Ideal আর quotient ring — ℤ/nℤ থেকে F[x]/(f)

ℤ_n আসলে কোথা থেকে আসে? পর্ব ৫৫-এ দেখেছেন, “a ≡ b (mod n)” একটি equivalence relation, আর ℤ_n-এর প্রতিটি উপাদান একটি equivalence class, যেমন [3] = {…, −9, 3, 15, …}. এই class-গুলোর মধ্যে যোগ-গুণ চলে, কারণ যে সেট দিয়ে আমরা “ভাগ” করছি, সেই nℤ = {…, −n, 0, n, 2n, …}-এর একটি বিশেষ গুণ আছে।

গুণ কেন well-defined, অর্থাৎ class-এর প্রতিনিধি বদলালে ফল বদলায় না? a ~ a′ আর b ~ b′ হলে a′b′ − ab = a′(b′ − b) + (a′ − a)b, আর (খ) অনুযায়ী দুটি পদই I-এ, তাই যোগফলও I-এ। এই এক লাইনের জন্যই ideal-এর সংজ্ঞায় (খ) রাখা হয়েছে। ℤ-এ nℤ একটি ideal, আর ℤ/nℤ ঠিক ℤ_n. আসলে ℤ-এর প্রতিটি ideal এমনই: I ≠ {0} হলে I-এর সবচেয়ে ছোট ধনাত্মক উপাদান n নিন; যেকোনো a ∈ I-কে a = qn + r লিখলে r = a − qn ∈ I আর 0 ≤ r < n, তাই r = 0, অর্থাৎ I = nℤ. হুবহু একই যুক্তিতে F[x]-এর প্রতিটি ideal হলো একটি polynomial-এর সব গুণিতক, (f) = {gf : g ∈ F[x]}, যেখানে f হলো I-এর সবচেয়ে ছোট ঘাতের উপাদান।

F[x]/(f)-এর প্রতিটি class-এ ঠিক একটি প্রতিনিধি আছে যার ঘাত deg f-এর কম (division algorithm-এর ভাগশেষ)। তাই f-এর ঘাত n আর F = GF(p) হলে F[x]/(f)-এর উপাদান সংখ্যা pⁿ: n-টি সহগ, প্রতিটির p রকম মান। এখন মূল উপপাদ্য, যা ℤ_n-এর গল্পের হুবহু অনুবাদ।

1. (⇐) [g] ≠ 0, অর্থাৎ f ∤ g. gcd(f, g) হলো f-এর একটি monic ভাজক; f irreducible বলে তা 1 অথবা f-এর monic রূপ, আর দ্বিতীয়টি হলে f ∣ g হতো। তাই gcd = 1. — irreducible-এর সংজ্ঞা
2. উপপাদ্য ৪.১-এর Bézout: sg + tf = 1. Class নিলে [s][g] = [1], কারণ tf ∈ (f). তাই [g]-এর inverse [s]. — Bézout
3. (⇒) f irreducible না হলে f = uv, যেখানে 1 ≤ deg u, deg v < deg f. তখন [u] ≠ 0, [v] ≠ 0, কিন্তু [u][v] = [f] = 0: zero divisor, তাই field নয়। ∎ — উপপাদ্য ২.২-এর প্রমাণের মতো

তাই GF(pⁿ) বানাতে একটি n ঘাতের irreducible polynomial দরকার। এমন কি সবসময় আছে, আর কয়টি? GF(2)-এ ছোট ঘাতে brute force করা যায়: n ঘাতের প্রতিটি polynomial-কে 1 থেকে ⌊n/2⌋ ঘাতের সব polynomial দিয়ে ভাগ করে দেখা (কোনো উৎপাদক থাকলে অন্তত একটির ঘাত ≤ n/2). ফলাফল একটি সুন্দর সূত্রের সঙ্গে মেলে, যা Möbius function μ ব্যবহার করে (μ(1) = 1; d যদি k-টি আলাদা মৌলিকের গুণফল হয় তবে μ(d) = (−1)^k; কোনো মৌলিকের বর্গ d-কে ভাগ করলে μ(d) = 0).

সূত্রটি Gauss-এর নামে পরিচিত; তাঁর জীবদ্দশায় অপ্রকাশিত লেখায় এটি ছিল বলে উল্লেখ করা হয়। যেমন N₂(4) = (2⁴ − 2²)/4 = 3 আর N₃(2) = (9 − 3)/2 = 3. সূত্রের উৎস একটি অভেদ: x^qn − x হলো সেই সব monic irreducible-এর গুণফল, যাদের ঘাত n-কে ভাগ করে; ঘাত তুলনা করলে ∑_{d ∣ n} d · N_q(d) = qⁿ, আর Möbius inversion বাকিটা দেয়। এর পূর্ণ প্রমাণ এখানে বাদ। একটি সহজ ফল: মোটামুটি N_q(n) ≈ qⁿ/n, তাই এলোমেলো একটি monic polynomial প্রায় 1/n সম্ভাবনায় irreducible, যেমন এলোমেলো একটি সংখ্যা N মোটামুটি 1/ln N সম্ভাবনায় মৌলিক। সূত্রটি ধনাত্মক, তাই প্রতিটি n-এ irreducible আছে, আর GF(pⁿ) সবসময় বানানো যায়।

def pmod(f, g):                  # GF(2)[x] as int bits: 0b1011 = x^3 + x + 1
    while f.bit_length() >= g.bit_length():
        f ^= g << (f.bit_length() - g.bit_length())
    return f
def irreducible(f):              # no factor of degree 1 .. deg(f)//2
    d = f.bit_length() - 1
    return all(pmod(f, g) for g in range(2, 1 << (d // 2 + 1)))
def mobius(n):
    r, k = 1, 2
    while k * k <= n:
        if n % k == 0:
            n //= k
            if n % k == 0: return 0
            r = -r
        k += 1
    return -r if n > 1 else r
def gauss(n, q=2):               # number of monic irreducibles of degree n
    return sum(mobius(d) * q ** (n // d) for d in range(1, n + 1) if n % d == 0) // n
for n in range(1, 7):
    found = [f for f in range(1 << n, 1 << (n + 1)) if irreducible(f)]
    show = [bin(f)[2:] for f in found] if n <= 4 else "..."
    print(f"degree {n}: brute force {len(found)}, Gauss {gauss(n)}  {show}")
sq = 0b111 ^ (0b111 << 1) ^ (0b111 << 2)   # (x^2+x+1)*(x^2+x+1), XOR shifts
f = 0b10101                      # x^4 + x^2 + 1
print("x^4+x^2+1: roots in GF(2):", [x for x in (0, 1) if pmod(f, 0b10 | x) == 0],
      "| irreducible:", irreducible(f), "| equals (x^2+x+1)^2:", f == sq)
print("degree 8 by Gauss:", gauss(8), "  over GF(3), degree 2:", gauss(2, 3))

degree 1: brute force 2, Gauss 2  ['10', '11']
degree 2: brute force 1, Gauss 1  ['111']
degree 3: brute force 2, Gauss 2  ['1011', '1101']
degree 4: brute force 3, Gauss 3  ['10011', '11001', '11111']
degree 5: brute force 6, Gauss 6  ...
degree 6: brute force 9, Gauss 9  ...
x^4+x^2+1: roots in GF(2): [] | irreducible: False | equals (x^2+x+1)^2: True
degree 8 by Gauss: 30   over GF(3), degree 2: 3

৭ · GF(16) নির্মাণ — আর গুণের group কেন cyclic

F = GF(2), f = x⁴ + x + 1 (irreducible, উপরের তালিকা)। উপপাদ্য ৬.২ অনুযায়ী GF(2)[x]/(f) একটি field, যার উপাদান ঘাত 3 পর্যন্ত সব polynomial, অর্থাৎ 4 bit-এর ১৬টি string: এটিই GF(16) = GF(2⁴). যোগ মানে XOR. গুণের নিয়ম: সাধারণভাবে গুণ করুন, তারপর f দিয়ে ভাগশেষ নিন। হাতে করার কৌশল হলো f(x) = 0 থেকে পাওয়া সম্পর্ক x⁴ = x + 1 (mod 2-এ −1 = 1). পর্ব ৩০-এ AES-এর GF(2⁸)-এ ঠিক এভাবেই {57} · {83} গুণ করেছেন; এখানে ছোট field-এ পুরো গঠনটি দেখব।

1a = 1101, b = 101121101 ⊕ 1 1010 ⊕ 110 10003= 111 1111 (ঘাত 6)4⊕ x²·f = 100 11005⊕ x·f  = 10 01106⊕ f    = 1 0011 → 0110

শেষ ধাপের “ঘাতের তালিকা” কৌশলটি কাজ করে, কারণ GF(16)-এর প্রতিটি অশূন্য উপাদান x-এর কোনো ঘাত। এটি একটি সাধারণ উপপাদ্যের বিশেষ রূপ। F* দিয়ে F-এর অশূন্য উপাদানের সেট বোঝাই; গুণের সাপেক্ষে এটি একটি group, যাকে multiplicative group বলে।

প্রমাণের রূপরেখা (পর্ব ৭০-এর Lagrange আর উপপাদ্য ৫.২ মিলিয়ে):

1. প্রতিটি a ∈ F*-এর order q − 1-কে ভাগ করে (Lagrange). d ∣ q − 1-এর জন্য ψ(d) = order ঠিক d এমন উপাদানের সংখ্যা। তাহলে ∑_{d ∣ q−1} ψ(d) = q − 1. — প্রতিটি উপাদান একবার গোনা
2. order d-এর একটি a থাকলে 1, a, …, a^d−1 হলো x^d − 1-এর d-টি আলাদা root; উপপাদ্য ৫.২ অনুযায়ী আর কোনো root নেই। তাই order d-এর প্রতিটি উপাদান a-এর কোনো ঘাত a^k, আর a^k-এর order d ⇔ gcd(k, d) = 1. ফলে ψ(d) = 0 অথবা φ(d). — field-এ root-এর সীমা
3. পরিচিত অভেদ ∑_{d ∣ m} φ(d) = m (m = q − 1). ধাপ ১ আর ২ মিলিয়ে q − 1 = ∑ ψ(d) ≤ ∑ φ(d) = q − 1, তাই প্রতিটি d-তে ψ(d) = φ(d). বিশেষ করে ψ(q − 1) = φ(q − 1) ≥ 1. ∎ — সমতা জোর করে আসে

ধাপ ২-এ field ছাড়া প্রমাণ চলত না, তাই ℤ₈-এর unit-group {1, 3, 5, 7} cyclic নয় (প্রতিটির বর্গ 1, ঠিক §৫-এর চার root). q = p মৌলিক হলে এটিই পর্ব ২৪-এর primitive root-এর অস্তিত্ব। নিচের কোড GF(16)-এ সব দাবি পরীক্ষা করে।

M = 0b10011                       # x^4 + x + 1, irreducible over GF(2)
def mul(a, b, m=M):               # multiply two polynomials mod m
    r, top = 0, 1 << (m.bit_length() - 1)
    while b:
        if b & 1: r ^= a
        b >>= 1; a <<= 1
        if a & top: a ^= m        # degree of m appeared: subtract (XOR) m
    return r
def order(a, m=M):                # smallest k >= 1 with a^k = 1
    x, k = a, 1
    while x != 1: x, k = mul(x, a, m), k + 1
    return k
print("1101 * 1011 =", format(mul(0b1101, 0b1011), "04b"))
powers, x = [], 1
for k in range(15):               # powers of x = 0b0010
    powers.append(format(x, "04b")); x = mul(x, 0b10)
print("x^0..x^14:", " ".join(powers))
print("all 15 nonzero elements appear:", len(set(powers)) == 15)
orders = {a: order(a) for a in range(1, 16)}
print("element orders:", sorted(orders.values()))
gens = [format(a, "04b") for a in orders if orders[a] == 15]
print("generators:", len(gens), gens)
inv = {a: b for a in range(1, 16) for b in range(1, 16) if mul(a, b) == 1}
print("every nonzero element has an inverse:", len(inv) == 15,
      "| inverse of 0100:", format(inv[0b100], "04b"))
M2 = 0b11111                      # x^4+x^3+x^2+x+1: also irreducible
print("mod x^4+x^3+x^2+x+1: order of x =", order(0b10, M2))
print("AES field (mod 0x11B): order of 02 =", order(2, 0x11B),
      "| order of 03 =", order(3, 0x11B))

1101 * 1011 = 0110
x^0..x^14: 0001 0010 0100 1000 0011 0110 1100 1011 0101 1010 0111 1110 1111 1101 1001
all 15 nonzero elements appear: True
element orders: [1, 3, 3, 5, 5, 5, 5, 15, 15, 15, 15, 15, 15, 15, 15]
generators: 8 ['0010', '0011', '0100', '0101', '1001', '1011', '1101', '1110']
every nonzero element has an inverse: True | inverse of 0100: 1101
mod x^4+x^3+x^2+x+1: order of x = 5
AES field (mod 0x11B): order of 02 = 51 | order of 03 = 255

এই ঘাতের তালিকা বাস্তবেও কাজে লাগে। একবার “log table” (উপাদান থেকে তার ঘাত) আর “antilog table” (ঘাত থেকে উপাদান) বানিয়ে রাখলে দুটি অশূন্য উপাদানের গুণ মানে দুটি log যোগ করে mod 15 নেওয়া, আর inverse মানে 15 থেকে log বিয়োগ। বাজারের হিসাবে logarithm table দিয়ে গুণকে যোগে বদলানোর পুরোনো কৌশলের এটি সসীম রূপ, তবে এখানে কোনো আসন্ন মান নেই, সব নির্ভুল। অনেক error-correcting code-এর সফটওয়্যার GF(2⁸)-এ এমন ২৫৬ ঘরের টেবিল ব্যবহার করে বলে বর্ণিত। Cryptography-তে অবশ্য টেবিল-দেখা গোপন ডেটার ওপর নির্ভর করলে cache-এর সময় থেকে তথ্য ফাঁস হতে পারে, তাই সেখানে সতর্ক বাস্তবায়ন লাগে।

৮ · প্রয়োগ — CRC, AES, Reed–Solomon আর Shamir

CRC. পর্ব ২৬-এ দেখেছেন, CRC বার্তা M(x)-কে x^r দিয়ে গুণ করে r ঘাতের generator G(x) দিয়ে ভাগ করে, আর ভাগশেষ জুড়ে দেয়, যাতে পাঠানো polynomial T(x) হয় G-এর গুণিতক। এখন ভাষাটি পরিষ্কার: T হলো GF(2)[x]-এর ideal (G)-এর সদস্য, আর ভুল E(x) ধরা পড়ে না ঠিক তখন, যখন E ∈ (G). একটি bit উল্টালে E = xⁱ. xⁱ-এর ভাজক শুধু x^j ধরনের একক পদ (অনন্য উৎপাদকে ভাঙা থেকে), তাই G-তে অন্তত দুটি পদ থাকলে G ∤ xⁱ, আর সব একক ভুল ধরা পড়ে। বাস্তব CRC-32 আর Ethernet-এর হিসাব Computer Networks কোর্সের পর্ব ০৯-এ।

AES. AES-এর প্রতিটি byte GF(2⁸) = GF(2)[x]/(x⁸ + x⁴ + x³ + x + 1)-এর একটি উপাদান, আর S-box-এর মূল ধাপ এই field-এর inverse (তার পরে একটি affine রূপান্তর). গুণের হিসাব পর্ব ৩০-এ, আর AES নিরাপদে কীভাবে ব্যবহার করতে হয় তা Cybersecurity কোর্সের পর্ব ০৮-এ।

Reed–Solomon. Irving Reed আর Gustave Solomon ১৯৬০ সালে প্রকাশিত একটি প্রবন্ধে k-টি তথ্য-প্রতীককে GF(q)-এর ওপর একটি k − 1 ঘাতের polynomial-এর সহগ ধরে, তাকে n > k-টি বিন্দুতে মূল্যায়ন করে পাঠানোর প্রস্তাব দেন বলে পরিচিত। দুটি আলাদা এমন polynomial-এর পার্থক্যের ঘাত ≤ k − 1, তাই উপপাদ্য ৫.২ অনুযায়ী তারা বড়জোর k − 1 বিন্দুতে মেলে, অর্থাৎ অন্তত n − k + 1 বিন্দুতে আলাদা। এই “দূরত্ব” থেকেই ভুল সারানোর ক্ষমতা আসে; CD, QR code আর অনেক সংরক্ষণ-ব্যবস্থায় Reed–Solomon-এর রূপ ব্যবহৃত হয় বলে বর্ণিত। Code-এর দূরত্বের সাধারণ তত্ত্ব পর্ব ৭২ “Error-correcting code — parity, Hamming code আর Hamming distance”-এ।

Shamir secret sharing. বাজারঘরের মূল ভল্টের একটি গোপন সংখ্যা s আছে। পাঁচজন ম্যানেজারের যেকোনো তিনজন মিলে তা খুলতে পারবেন, কিন্তু দুজন পারবেন না, এমনকি s সম্পর্কে কিছু জানতেও পারবেন না। Adi Shamir ১৯৭৯ সালে “How to Share a Secret” প্রবন্ধে (Communications of the ACM) এর একটি polynomial-ভিত্তিক সমাধান দেন: একটি মৌলিক p নিয়ে GF(p)-এ এলোমেলো f(x) = s + c₁x + c₂x² বানান, আর ম্যানেজার i-কে দিন (i, f(i)). একই বছরে George Blakley জ্যামিতিক ভাবনা থেকে স্বাধীনভাবে একটি পদ্ধতি দেন।

1. অস্তিত্ব: j-তম গুণফল x = x_j-এ 1 আর অন্য x_m-এ 0; ভাগ চলে কারণ x_j − x_m ≠ 0 আর F field. — সূত্র যাচাই
2. অনন্যতা: দুটি এমন f আর h থাকলে f − h-এর ঘাত ≤ k − 1 কিন্তু root k-টি। উপপাদ্য ৫.২ অনুযায়ী f − h = 0. ∎ — root-এর সীমা

এখন threshold-এর যুক্তি: তিনজনের তিনটি বিন্দু ঘাত ≤ 2-এর f-কে অনন্যভাবে ঠিক করে, তাই s = f(0) বেরিয়ে আসে। দুজনের দুটি বিন্দুর সঙ্গে যেকোনো সম্ভাব্য গোপন সংখ্যা t-এর বিন্দু (0, t) যোগ করলে আবার তিনটি বিন্দু, তাই প্রতিটি t-এর জন্য ঠিক একটি সামঞ্জস্যপূর্ণ polynomial আছে। c₁, c₂ সমসম্ভাব্যভাবে বাছা হলে দুটি share দেখে প্রতিটি t সমান সম্ভাব্য থাকে: দুজন কিছুই শেখেন না। এই নিরাপত্তা আক্রমণকারীর কম্পিউটারের শক্তির ওপর নির্ভর করে না।

একটি সুন্দর সংযোগ এখানে লুকিয়ে আছে। পর্ব ২৩-এর Chinese Remainder Theorem ring-এর ভাষায় বলে: gcd(m, n) = 1 হলে ℤ_mn আর ℤ_m × ℤ_n একই ring, শুধু নাম আলাদা। ℤ₆-এর 0, 1, 2, 3, 4, 5 হয়ে যায় (0, 0), (1, 1), (0, 2), (1, 0), (0, 1), (1, 2), আর যোগ-গুণ দুই অংশে আলাদা আলাদা চলে। Polynomial-এ একই উপপাদ্য আছে: f-কে x − x_i দিয়ে ভাগ করলে ভাগশেষ f(x_i) (factor theorem-এর প্রমাণ), তাই “x₁, …, x_k-এ f-এর মান জানা” মানে আলাদা আলাদা x − x_i-এর সাপেক্ষে f-এর ভাগশেষ জানা। Lagrange interpolation আসলে polynomial-এর CRT, আর তার সূত্রের প্রতিটি গুণফল CRT-এর সেই সংখ্যাগুলোর মতো, যা একটি modulus-এ 1 আর বাকিগুলোতে 0. একই কাঠামো দুই জগতে, ঠিক যেমন §৪-এ Euclid দেখেছেন।

from itertools import combinations
import random
p = 2027                                  # a small prime: toy only, never real use
secret, k, n = 1234, 3, 5                 # any 3 of 5 managers can open
random.seed(71)
coef = [secret] + [random.randrange(p) for _ in range(k - 1)]
f = lambda x: sum(c * pow(x, i, p) for i, c in enumerate(coef)) % p
shares = [(x, f(x)) for x in range(1, n + 1)]
print("polynomial coefficients:", coef)
print("shares:", shares)
def interp(pts, x0=0):                    # Lagrange interpolation, value at x0
    total = 0
    for j, (xj, yj) in enumerate(pts):
        num = den = 1
        for m, (xm, _) in enumerate(pts):
            if m != j:
                num = num * (x0 - xm) % p
                den = den * (xj - xm) % p
        total += yj * num * pow(den, -1, p)   # division = multiply by inverse
    return total % p
ok = all(interp(list(c)) == secret for c in combinations(shares, 3))
print("every 3 of 5 shares give", secret, ":", ok)
two = shares[:2]                          # only 2 shares: try every secret s
guess3 = {interp([(0, s)] + two, 3) for s in range(p)}
print("2 shares fit a different polynomial for each of", len(guess3), "secrets")

polynomial coefficients: [1234, 663, 1041]
shares: [(1, 911), (2, 643), (3, 430), (4, 272), (5, 169)]
every 3 of 5 shares give 1234 : True
2 shares fit a different polynomial for each of 2027 secrets

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

অঙ্ক ১: ℤ₁₂-এর unit আর zero divisor

ℤ₁₂-এর সব unit আর তাদের inverse, আর সব zero divisor বের করুন।

1. Unit = gcd(a, 12) = 1: 1, 5, 7, 11; সংখ্যা φ(12) = 4. প্রতিটি নিজের inverse: 5 · 5 = 25, 7 · 7 = 49, 11 · 11 = 121, সবই ≡ 1.
2. Zero divisor: বাকি অশূন্য 2, 3, 4, 6, 8, 9, 10; প্রতিটির জন্য b = 12/gcd(a, 12): 2 · 6, 3 · 4, 4 · 3, 6 · 2, 8 · 3, 9 · 4, 10 · 6, সবই ≡ 0 (scratch-এ মেলানো)।

অঙ্ক ২: GF(3)-এ উৎপাদকে ভাঙা

x³ + x + 1 GF(2)-এ irreducible, কিন্তু GF(3)-এ? উৎপাদকে ভাঙুন।

1. GF(2)-এ x = 0 আর 1-এ মান 1, root নেই, ঘাত 3, তাই irreducible (উপপাদ্য ৫.৪)।
2. GF(3)-এ x = 1-এ 1 + 1 + 1 = 3 ≡ 0, তাই x − 1 = x + 2 একটি উৎপাদক। ভাগ করলে x³ + x + 1 = (x + 2)(x² + x + 2); যাচাই: x³ + 3x² + 4x + 4 ≡ x³ + x + 1.
3. x² + x + 2-এর x = 0, 1, 2-এ মান 2, 1, 2: root নেই, তাই আর ভাঙে না। Irreducibility তাই field-এর ওপর নির্ভর করে।

অঙ্ক ৩: GF(16)-এ inverse

x⁴ + x + 1 দিয়ে বানানো GF(16)-এ x³ + 1-এর inverse বের করুন।

1. ঘাতের তালিকায় 1001 = x¹⁴. তাই inverse x¹⁵⁻¹⁴ = x = 0010.
2. সরাসরি যাচাই: x(x³ + 1) = x⁴ + x = (x + 1) + x = 1. ✓ (Extended Euclid দিয়েও একই উত্তর আসে, কারণ x⁴ + x + 1 = x · (x³ + 1) + 1.)

অঙ্ক ৪: গণনা

GF(2)-এর ওপর 5 ঘাতের কয়টি monic irreducible polynomial? N₂(5) = (2⁵ − 2)/5 = 6, কারণ 5-এর ভাজক 1 আর 5, μ(5) = −1. (উপরের brute force-এও 6.) তাহলে 2⁵ = 32টি monic 5 ঘাতের polynomial-এর মাত্র 6টি irreducible, প্রায় 1/5 অংশ।

অঙ্ক ৫: Extended Euclid দিয়ে GF(8)-এ inverse

GF(8) = GF(2)[x]/(x³ + x + 1)-এ x² + x + 1-এর inverse extended Euclid দিয়ে বের করুন।

1. f = x³ + x + 1-কে g = x² + x + 1 দিয়ে ভাগ: (x + 1)g = x³ + 1, তাই f = (x + 1)g + x. ভাগশেষ x.
2. g-কে x দিয়ে ভাগ: g = (x + 1) · x + 1. ভাগশেষ 1, তাই gcd = 1 আর inverse আছে (f irreducible হওয়ায় এটি প্রত্যাশিত)।
3. পেছনে হাঁটা (GF(2)-এ বিয়োগ = যোগ): 1 = g + (x + 1)x = g + (x + 1)(f + (x + 1)g) = (x + 1)f + (1 + (x + 1)²)g. আর 1 + (x + 1)² = 1 + x² + 1 = x².
4. mod f নিলে x² · g ≡ 1, তাই (x² + x + 1)⁻¹ = x². যাচাই: x²(x² + x + 1) = x⁴ + x³ + x², আর x³ = x + 1, x⁴ = x² + x বসালে (x² + x) + (x + 1) + x² = 1 (scratch-এ সব সাতটি inverse brute force-এ মেলানো)।

প্রমাণের ভুল ধরুন: “irreducible, তাই x generator”

একজন লিখলেন: “f = x⁴ + x³ + x² + x + 1 GF(2)-এ irreducible, তাই GF(2)[x]/(f) একটি field, যার গুণের group cyclic এবং 15 উপাদানের। x একটি অশূন্য উপাদান, তাই x-এর ঘাতগুলো সব ১৫টি উপাদান দেয়।”

ভুল কোথায়: প্রথম দুটি দাবি ঠিক: field হয় (উপপাদ্য ৬.২), আর F* cyclic (উপপাদ্য ৭.১)। কিন্তু “cyclic” মানে কোনো একটি generator আছে, প্রতিটি অশূন্য উপাদান generator নয়। এখানে (x − 1)f = x⁵ − 1, তাই x⁵ = 1: x-এর order 5, আর তার ঘাত মাত্র পাঁচটি উপাদান দেয় (উপরের কোডেও order 5). Generator φ(15) = 8টি, বাকি ৭টি অশূন্য উপাদান generator নয়। অস্তিত্বের উপপাদ্য থেকে নির্দিষ্ট একটি উপাদান সম্পর্কে সিদ্ধান্ত টানাই ভুল।

১০ · AI-এর যুগে — ring আর field-এর হিসাব যাচাই

AI সহকারী সংজ্ঞা ভালো বলে, কিন্তু mod p-এর হিসাবে, শর্ত বাদ দেওয়ায় আর “অস্তিত্ব” ও “এটিই সেটি” গুলিয়ে ফেলায় ভুল করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

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

• Modulus সত্যিই irreducible, ছোট ঘাতের সব উৎপাদক দিয়ে ভাগ করে নিশ্চিত হয়েছি
• প্রতিটি ভাগে q · g + r = f, আর ভাগশেষের ঘাত ভাজকের চেয়ে কম
• Inverse দাবি করলে গুণ করে 1 পেয়েছি
• উপপাদ্যের শর্ত (field, integral domain, আলাদা বিন্দু) প্রমাণে স্পষ্ট
• ছোট ক্ষেত্রে brute force দিয়ে root, order বা গণনা নিজে চালিয়ে মিলিয়েছি
• নাম, সাল আর মানদণ্ডের দাবি বিশ্বস্ত পাঠ্যবই বা মূল নথিতে মিলিয়েছি

Finite field-এর উত্তর যাচাই সহজ, কারণ সব কিছু সসীম: কয়েকশো উপাদানের field-এ প্রতিটি দাবি কম্পিউটারে এক মুহূর্তে পরীক্ষা করা যায়। AI-এর প্রমাণ বিশ্বাস করার আগে ছোট উদাহরণে তার প্রতিটি দাবি চালিয়ে দেখুন।