Number Systems ও Modular Arithmetic — ঘড়ির গণিত

Positional notation — সংখ্যা লেখার চুক্তি

2026 লিখলে আমরা আসলে বলি:

$2 \times 10^3 + 0 \times 10^2 + 2 \times 10^1 + 6 \times 10^0$

গুরুত্বপূর্ণ কথাটা হলো: 10 -এ বিশেষ কিছু নেই। আমাদের দশটা আঙুল আছে, ব্যস। যেকোনো b ≥ 2 কাজ করে।

সাধারণভাবে, base b-তে অঙ্ক dₙ … d₁ d₀ মানে:

$N = \sum_{i=0}^{n} d_i \cdot b^{i}, \qquad 0 \le d_i \lt b$

শর্তটা লক্ষ্য করুন: প্রতিটা অঙ্ক 0 থেকে b−1। Base 2-এ অঙ্ক দুইটা (0,1), base 16-এ ষোলোটা (0–9, a–f)।

একই সংখ্যা, চার ভাষায়:

Base	২০২৬	Prefix
Decimal (10)	2026	—
Binary (2)	11111101010	0b
Octal (8)	3752	0o (C-তে শুধু 0)
Hex (16)	7ea	0x

যাচাই করুন হাতে: 0x7ea = 7×256 + 14×16 + 10 = 1792 + 224 + 10 = 2026 ✓

Hex কেন আছে — একটামাত্র কারণ

16 = 2⁴। তাই একটা hex অঙ্ক ঠিক চারটা bit। কোনো হিসাব নেই, কোনো carry নেই — শুধু টুকরো টুকরো করে অনুবাদ।

  1 1 1 1 1 1 0 1 0 1 0        ← 11 bit
= 0111 1110 1010                ← বাঁয়ে শূন্য দিয়ে ৪-এর গুণিতক
    7    e    a                 ← প্রতি চারটার জন্য একটা অঙ্ক

তাই 0x7ea।

এই ধর্মটাই hex-কে অপরিহার্য করেছে: byte = ৮ bit = ঠিক দুইটা hex অঙ্ক। 0x00 থেকে 0xff, কোনো ব্যতিক্রম নেই।

Decimal-এ একটা byte 0 থেকে 255 — তিন অঙ্ক, কিন্তু সব তিন-অঙ্কের সংখ্যা বৈধ নয় (299 কোনো byte নয়)। Alignment ভেঙে যায়, চোখে pattern ধরা পড়ে না।

রূপান্তর — দুইটা অ্যালগরিদম

Decimal → base b: বারবার ভাগ, ভাগশেষ উল্টো দিকে পড়ুন।

2026 ÷ 16 = 126, ভাগশেষ 10 (a)   ← সবচেয়ে কম গুরুত্বপূর্ণ অঙ্ক
 126 ÷ 16 =   7, ভাগশেষ 14 (e)
   7 ÷ 16 =   0, ভাগশেষ  7 (7)   ← সবচেয়ে বেশি গুরুত্বপূর্ণ

উল্টো দিকে পড়ুন → 7ea

Base b → decimal: Horner’s method।

0x7ea:  শুরু 0
        0 × 16 + 7  =   7
        7 × 16 + 14 = 126
      126 × 16 + 10 = 2026

Horner-এর সুবিধা: কোনো pow() লাগে না, শুধু n টা গুণ ও যোগ। এটাই প্রতিটা strtol() implementation-এর ভেতরের loop।

Divisibility আর division algorithm

b, a-কে ভাগ করে (লিখি b | a) যদি এমন একটা পূর্ণসংখ্যা k থাকে যেন a = kb।

Division algorithm (নাম বিভ্রান্তিকর — এটা একটা theorem, algorithm নয়):

যেকোনো পূর্ণসংখ্যা a আর ধনাত্মক b-এর জন্য অনন্য একজোড়া q (quotient) ও r (remainder) আছে যেন

$a = qb + r, \qquad 0 \le r \lt b$

দুইটা শব্দই গুরুত্বপূর্ণ: অস্তিত্ব আর অনন্যতা। অনন্যতাই modular arithmetic-কে সুসংজ্ঞায়িত করে।

GCD আর Euclid-এর অ্যালগরিদম

gcd(a, b) = সবচেয়ে বড় পূর্ণসংখ্যা যা দুটোকেই ভাগ করে।

Euclid-এর মূল অন্তর্দৃষ্টি (খ্রিস্টপূর্ব ৩০০ অব্দ, আজও সেরা):

$\gcd(a, b) = \gcd(b, a \bmod b)$

কেন সত্য: a = qb + r হলে, a আর b-র যেকোনো সাধারণ ভাজক d, r = a − qb-কেও ভাগ করে। উল্টোদিকে b আর r-এর যেকোনো সাধারণ ভাজক a = qb + r-কেও ভাগ করে। দুই জোড়ার সাধারণ ভাজকের set অভিন্ন — তাই সবচেয়ে বড়টাও এক।

gcd(1071, 462)
  1071 = 2 × 462 + 147
   462 = 3 × 147 +  21
   147 = 7 ×  21 +   0    ← ভাগশেষ ০, থামুন
gcd = 21

তিন ধাপ। Trial division-এ ৪৬২ পর্যন্ত সংখ্যা যাচাই করতে হতো।

কত দ্রুত? Lamé-র theorem: ধাপ সংখ্যা সবচেয়ে ছোট সংখ্যাটার অঙ্ক সংখ্যার ৫ গুণের বেশি নয়। অর্থাৎ O(log min(a,b))।

সবচেয়ে খারাপ ক্ষেত্র পরপর দুইটা Fibonacci সংখ্যা — gcd(F₍ₙ₊₁₎, Fₙ)-এ প্রতিটা ধাপে quotient ঠিক 1, তাই সবচেয়ে ধীর সংকোচন। ২০৪৮-bit সংখ্যাতেও কয়েক হাজার ধাপের বেশি লাগে না।

Extended Euclid আর Bézout-এর অভেদ

Euclid শুধু gcd দেয়। কিন্তু প্রায়ই আমাদের আরো দরকার।

Bézout-এর অভেদ: যেকোনো a, b-এর জন্য এমন পূর্ণসংখ্যা x, y আছে যেন

$ax + by = \gcd(a, b)$

Extended Euclid এই x, y বের করে — একই O(log n) সময়ে।

হাতে করে দেখুন — gcd(240, 46):

সামনের দিকে Euclid:

ধাপ	সমীকরণ
1	240 = 5 × 46 + 10
2	46 = 4 × 10 + 6
3	10 = 1 × 6 + 4
4	6 = 1 × 4 + 2
5	4 = 2 × 2 + 0 → gcd = 2

এখন উল্টো দিকে প্রতিস্থাপন — প্রতিবার ভাগশেষটাকে আগের লাইন দিয়ে বদলান:

উৎস	প্রতিস্থাপন
ধাপ 4	2 = 6 − 1×4
ধাপ 3	= 6 − 1×(10 − 1×6) = 2×6 − 1×10
ধাপ 2	= 2×(46 − 4×10) − 1×10 = 2×46 − 9×10
ধাপ 1	= 2×46 − 9×(240 − 5×46) = 47×46 − 9×240

$240 \times (-9) + 46 \times 47 = -2160 + 2162 = 2 \quad\blacksquare$

পুনরাবৃত্তিমূলক রূপ (যেটা আমরা কোড করব) এই উল্টো যাত্রাটা সামনের দিকেই করে ফেলে, দুইটা সহগ জোড়া টেনে নিয়ে:

$(x, y) \leftarrow (y',\; x' - q \cdot y')$

Congruence — সমতার একটা শিথিল সংস্করণ

$a \equiv b \pmod{m} \iff m \mid (a - b)$

পড়ুন: “a আর b congruent modulo m”।

সমতুল্য তিনটা সংজ্ঞা (একটা বাছুন, যেটা হাতের কাজে সুবিধা):

1. m | (a − b)
2. a mod m == b mod m
3. a = b + km কোনো পূর্ণসংখ্যা k-এর জন্য

17 ≡ 5 (mod 12) — কারণ 12 | 12। ঘড়িতে ১৭টা মানে বিকেল ৫টা।

এটা একটা equivalence relation

Relations-এর লেসনে আমরা তিনটা শর্ত শিখেছিলাম। যাচাই করুন:

ধর্ম	যাচাই
Reflexive	m ভাগ করে (a − a) = 0 ✓
Symmetric	m যদি (a−b) ভাগ করে, (b−a) ও করে ✓
Transitive	(a−b) আর (b−c) ভাগ করলে (a−c) = (a−b)+(b−c) ও ভাগ করে ✓

তাই congruence পূর্ণসংখ্যাদের partition করে ঠিক m টা equivalence class-এ:

$\mathbb{Z}_m = \{[0], [1], \ldots, [m-1]\}$

[r] = যাদের ভাগশেষ r, অর্থাৎ {…, r−m, r, r+m, r+2m, …}।

Congruence যোগ ও গুণে টিকে থাকে

এটাই পুরো বিষয়টার প্রাণভোমরা। যদি a ≡ b আর c ≡ d (mod m):

$a + c \equiv b + d, \qquad a - c \equiv b - d, \qquad ac \equiv bd \pmod{m}$

প্রমাণ (গুণের জন্য). a = b + km, c = d + lm ধরুন।

$ac = (b+km)(d+lm) = bd + m(bl + kd + klm)$

দ্বিতীয় পদটা m-এর গুণিতক, তাই ac ≡ bd \pmod m $\quad\blacksquare$

ব্যবহারিক ফল: আপনি যেকোনো সময় mod নিতে পারেন।

# এই দুইটা একই উত্তর দেয় —
(123456789 * 987654321) % 1000
(123456789 % 1000) * (987654321 % 1000) % 1000
# কিন্তু দ্বিতীয়টায় সংখ্যাগুলো কখনো ৬ অঙ্কের বেশি হয় না

বড় সংখ্যার প্রতিটা algorithm এই ধর্মের উপর দাঁড়িয়ে — মাঝপথে mod নিয়ে সংখ্যা ছোট রাখা যায়, উত্তর বদলায় না। Overflow এড়ানোর আসল কৌশল এটাই।

Modular inverse — কখন ভাগ করা যায়

Modular arithmetic-এ “ভাগ” বলে কিছু নেই। যা আছে তা হলো inverse দিয়ে গুণ।

a-র modular inverse mod m হলো সেই x যেন:

$a \cdot x \equiv 1 \pmod m$

লিখি a⁻¹ mod m।

অস্তিত্বের শর্ত: a⁻¹ mod m আছে যদি এবং কেবল যদি gcd(a, m) = 1।

কেন — দুই দিকেই:

(⇐) gcd(a,m) = 1 হলে Bézout দেয় ax + my = 1। দুই পাশে mod m নিন: my ≡ 0, তাই ax ≡ 1 (mod m)। x-ই inverse।

(⇒) ax ≡ 1 (mod m) হলে ax − 1 = km, অর্থাৎ ax − km = 1। d = gcd(a,m) বাঁ পাশের দুটো পদকেই ভাগ করে, তাই d | 1, তাই d = 1 $\quad\blacksquare$

তাই extended Euclid = modular inverse খোঁজার যন্ত্র।

একটা করে দেখি — 17⁻¹ mod 43:

ধাপ	Euclid
1	43 = 2 × 17 + 9
2	17 = 1 × 9 + 8
3	9 = 1 × 8 + 1
4	8 = 8 × 1 + 0 → gcd = 1, তাই inverse আছে

উল্টো:

1 = 9 − 1×8
  = 9 − 1×(17 − 1×9)  = 2×9 − 1×17
  = 2×(43 − 2×17) − 17 = 2×43 − 5×17

তাই −5 × 17 ≡ 1 (mod 43), অর্থাৎ

$17^{-1} \equiv -5 \equiv 38 \pmod{43}$

যাচাই: 17 × 38 = 646 = 15 × 43 + 1 ✓

Fermat আর Euler — শর্টকাট দুইটা

Fermat’s little theorem: p prime আর p ∤ a হলে $a^{p-1} \equiv 1 \pmod p$

কেন বিশ্বাসযোগ্য (স্বজ্ঞা, পূর্ণ প্রমাণ নয়): a, 2a, 3a, …, (p−1)a সংখ্যাগুলো mod p নিলে 1, 2, …, p−1-এরই একটা পুনর্বিন্যাস হয় (কারণ a invertible, তাই গুণটা একটা bijection — functions-এর লেসনের ভাষায়)। দুই দিকের গুণফল সমান করলে:

$a^{p-1} (p-1)! \equiv (p-1)! \pmod p$

(p−1)! prime p-এর সাথে coprime, তাই কাটা যায় $\quad\blacksquare$

তাৎক্ষণিক প্রয়োগ: a⁻¹ ≡ a^(p−2) (mod p)। Extended Euclid ছাড়াই inverse — শুধু একটা modular exponentiation।

Euler’s theorem (সাধারণীকরণ): gcd(a, n) = 1 হলে $a^{\varphi(n)} \equiv 1 \pmod n$

φ(n) = Euler’s totient = 1..n-এর মধ্যে কতগুলো সংখ্যা n-এর সাথে coprime।

n	φ(n)	কেন
p (prime)	p − 1	সব ছোট সংখ্যাই coprime
p^k	p^k − p^(k−1)	p-এর গুণিতকগুলো বাদ
pq (p ≠ q prime)	(p−1)(q−1)	multiplicative
12 = 2²·3	4	{1, 5, 7, 11}

n prime হলে φ(n) = n−1, তাই Euler → Fermat। একটাই theorem।

কেন এটা RSA-র হৃদয়: exponent-গুলো mod φ(n)-এ চলে। আপনি যদি φ(n) জানেন, তবেই decryption exponent বানাতে পারেন। আর φ(n) = (p−1)(q−1) জানতে হলে p, q জানতে হবে — অর্থাৎ n factor করতে হবে।

Chinese Remainder Theorem

খ্রিস্টীয় তৃতীয় শতকে সুন জু-র ধাঁধা:

এমন একটা সংখ্যা যার ৩ দিয়ে ভাগশেষ ২, ৫ দিয়ে ৩, ৭ দিয়ে ২ — সংখ্যাটা কী?

CRT: m₁, m₂, …, mₖ জোড়ায় জোড়ায় coprime হলে, সমীকরণগুলো $x \equiv a_i \pmod{m_i}$ -এর একটা অনন্য সমাধান আছে mod M = m₁m₂⋯mₖ।

স্বজ্ঞাটা গোনার: mod m₁-এ m₁ টা সম্ভাবনা, mod m₂-এ m₂ টা — coprime হওয়ায় জোড়াগুলো স্বাধীন, তাই মোট m₁m₂ টা সম্ভাব্য জোড়া। আর mod m₁m₂-এ ঠিক m₁m₂ টা অবশিষ্ট। সংখ্যায় সংখ্যায় মিলছে — তাই mapping টা একটা bijection।

CRT আসলে বলছে: ℤ₁₀₅ ≅ ℤ₃ × ℤ₅ × ℤ₇। একটা বড় সংখ্যাকে কয়েকটা ছোট ভাগশেষে ভেঙে ফেলা যায়, আর দুইদিকেই যাওয়া যায়।

সুন জু-র ধাঁধা সমাধান করি:

M = 3 × 5 × 7 = 105

i	mᵢ	aᵢ	Mᵢ = M/mᵢ	Mᵢ⁻¹ mod mᵢ	পদ aᵢ Mᵢ Mᵢ⁻¹
1	3	2	35	35 ≡ 2, 2⁻¹ = 2	2 × 35 × 2 = 140
2	5	3	21	21 ≡ 1, 1⁻¹ = 1	3 × 21 × 1 = 63
3	7	2	15	15 ≡ 1, 1⁻¹ = 1	2 × 15 × 1 = 30

$x \equiv 140 + 63 + 30 = 233 \equiv 233 - 2(105) = \mathbf{23} \pmod{105}$

যাচাই: 23 = 7×3 + 2 ✓, 23 = 4×5 + 3 ✓, 23 = 3×7 + 2 ✓

নির্মাণটা কেন কাজ করে: প্রতিটা পদ aᵢ Mᵢ Mᵢ⁻¹ নিজের modulus-এ aᵢ দেয় (কারণ Mᵢ Mᵢ⁻¹ ≡ 1), আর বাকি সব modulus-এ শূন্য (কারণ Mᵢ-তে সেই factor আছে)। তাই পদগুলো একে অপরের ক্ষতি করে না — ঠিক basis vector-এর মতো।

Prime আর primality testing

Prime = ১-এর চেয়ে বড় এমন সংখ্যা যার ভাজক শুধু ১ আর নিজে।

Prime গুলোই পূর্ণসংখ্যার পরমাণু — arithmetic-এর মৌলিক উপপাদ্য বলে প্রতিটা n > 1 অনন্যভাবে prime-এর গুণফলে ভাঙে।

Trial division

def is_prime_trial(n):
    if n \< 2: return False
    if n % 2 == 0: return n == 2
    f = 3
    while f * f <= n:
        if n % f == 0: return False
        f += 2
    return True

√n পর্যন্ত দেখাই যথেষ্ট — কারণ n = ab হলে দুটোর অন্তত একটা ≤ √n।

খরচ: O(√n) ভাগ। শুনতে ভালো, কিন্তু n-এর অঙ্ক সংখ্যার হিসাবে এটা exponential। ২০৪৮-bit RSA modulus-এ √n ≈ 2¹⁰²⁴ ভাগ লাগবে — মহাবিশ্বের বয়সের চেয়ে বেশি সময়।

Miller–Rabin — সম্ভাব্যতা দিয়ে কাটিয়ে দেওয়া

Probability-র লেসনে আমরা দেখেছি একটা randomized algorithm “প্রায় নিশ্চিত” উত্তর অনেক সস্তায় দিতে পারে। Miller–Rabin তার সবচেয়ে বিখ্যাত উদাহরণ।

ভিত্তি: Fermat বলে prime p-এ a^(p−1) ≡ 1। তাই এটা না মিললে n নিশ্চিতভাবে composite।

কিন্তু শুধু Fermat যথেষ্ট নয় — Carmichael সংখ্যা (561, 1105, 1729, …) সব a-এর জন্য Fermat পাশ করে যায় যদিও composite। 561 = 3 × 11 × 17।

Miller–Rabin আরেকটা শর্ত যোগ করে। n − 1 = 2^s · d লিখুন (d বিজোড়)। n prime হলে, প্রতিটা a-এর জন্য হয়:

$a^d \equiv 1 \pmod n \qquad \text{অথবা} \qquad a^{2^r d} \equiv -1 \pmod n \;\; \text{কোনো } 0 \le r \lt s$

কেন: prime modulus-এ x² ≡ 1 -এর সমাধান কেবল x ≡ ±1 (কারণ p | (x−1)(x+1), আর prime এক factor-কে ভাগ করতেই হবে)। তাই a^(n−1) থেকে বারবার বর্গমূলের দিকে নামলে 1-এ পৌঁছানোর ঠিক আগের ধাপটা −1 হতে বাধ্য। না হলে আমরা 1-এর একটা nontrivial square root পেলাম — যার মানে n composite।

ত্রুটির সম্ভাবনা: একটা random a-তে সর্বোচ্চ 1/4। k টা স্বাধীন witness-এ:

$P(\text{composite-কে prime বলা}) \le 4^{-k}$

k = 40 হলে এটা 2⁻⁸⁰ ≈ 10⁻²⁴ — আপনার RAM-এ cosmic ray দিয়ে bit flip হওয়ার সম্ভাবনার চেয়েও কম। বাস্তবে এটাই যথেষ্ট, আর OpenSSL, GnuPG, Java-র BigInteger.isProbablePrime() সবাই এটাই ব্যবহার করে।