Visualization Ideas — Advanced Number Theory¶

Number theory-র algorithm গুলো abstract শোনায়, কিন্তু প্রত্যেকটার একটা যান্ত্রিক ছবি আছে — সিঁড়ি, ঘড়ি, দৌড় প্রতিযোগিতা। সেই ছবিগুলো একবার আঁকলে formula গুলো আর মুখস্থের বোঝা থাকে না। নিচে আঁকার idea, শেষে 3টা worked ASCII example।

প্রতি concept-এর visualization idea¶

1. Extended Euclid = সিঁড়ির ওঠা-নামা¶

Euclid-এর প্রতিটা ভাগকে সিঁড়ির এক-একটা ধাপ আঁকো — নামার সময় শুধু remainder লেখো, নামা শেষে gcd। তারপর লাল কালিতে নিচ থেকে উপরে তীর টেনে back-substitution — প্রতি ধাপে gcd-কে আগের লাইনের a, b-এর ভাষায় নতুন করে লেখো। ওঠা শেষ হলে x, y হাতে।

2. Diophantine solution family = দাঁড়িপাল্লা¶

ax + by = c-কে দাঁড়িপাল্লা ভাবো — বাঁ পাল্লায় a-ওজনের x-টা বাটখারা আর b-ওজনের y-টা। x-কে b/g বাড়িয়ে y-কে a/g কমালে মোট ওজন একই — পাল্লা স্থির। সংখ্যারেখায় solution গুলো dot করে দেখাও — সমান দূরত্বে সাজানো একটা পরিবার।

3. CRT = দুই ঘড়ির কাঁটা¶

পাশাপাশি দুটো ঘড়ি আঁকো — একটা 3 ঘরের, একটা 5 ঘরের। x = 0, 1, 2, ... বাড়াতে থাকো, দুই ঘড়ির কাঁটাই ঘোরে। যে মুহূর্তে দুই কাঁটা নির্দিষ্ট ঘরে (2 আর 3) একসাথে — সেটাই উত্তর। 15 ধাপ পরে পুরো দৃশ্য repeat — তাই উত্তর mod 15-এ unique।

4. φ আর μ = prime-দের আলাদা আলাদা ভোট¶

n-এর প্রতিটা prime factor-কে একটা রঙ দাও। φ-এর ছবিতে: 1 থেকে n পর্যন্ত সংখ্যারেখায় প্রতিটা রঙের গুণিতকগুলো কেটে দাও — যা বেঁচে থাকে তা-ই φ(n)। μ-এর ছবিতে: রঙ জোড় সংখ্যক হলে +1, বিজোড় হলে −1, কোনো রঙ দুবার (p²) থাকলেই 0 — sign-এর তিনটা ঘর।

5. Matrix exponentiation = gear box¶

Recurrence-এর এক ধাপ = একটা gear-এর এক ঘূর্ণন। Matrix squaring মানে দুটো gear জুড়ে "দুই-ধাপের gear" বানানো, তারপর "চার-ধাপের"... n-এর binary representation-এর জ্বলা bit গুলোর gear জুড়লেই n ধাপ এক ঘূর্ণনে। n = 13 = 1101₂ দিয়ে আঁকো: 8-gear + 4-gear + 1-gear।

6. Miller-Rabin = আদালতের জেরা¶

n আসামি, দাবি "আমি prime"। প্রতিটা base a একজন সাক্ষী — ধারা a^d, a^(2d), ... হলো জেরার প্রশ্নমালা। ধারাটা নিয়ম মেনে (n−1 হয়ে তারপর 1) গেলে সাক্ষী চুপ; নিয়ম ভাঙলে সাক্ষী চিৎকার করে — "composite!" — মামলা শেষ, রায় নিশ্চিত। সব সাক্ষী চুপ থাকলে "সম্ভবত নির্দোষ" (নির্দিষ্ট 12 সাক্ষীতে 64-bit-এ নিশ্চিত নির্দোষ)।

7. Pollard rho = ρ-আকৃতির দৌড়ের track¶

f(x) = x² + c mod n ধারাটা আঁকলে গ্রিক অক্ষর ρ-এর আকার — একটা লেজ, তারপর একটা loop। কচ্ছপ আর খরগোশ একই track-এ — খরগোশ দ্বিগুণ গতিতে; loop-এ ঢুকলে দেখা হবেই। দেখা হওয়ার বিন্দুতে gcd(|x−y|, n) লিখে factor বের হওয়া দেখাও।

8. Segmented sieve = টর্চ দিয়ে জানালা ছাঁকা¶

পুরো সংখ্যারেখা অন্ধকার; শুধু [L, R] জানালাটা আলোকিত। √R পর্যন্ত prime-রা এক-একটা stamp — প্রতিটা stamp জানালার ভেতরে তার গুণিতকগুলোতে ছাপ মারে। ছাপহীন ঘরগুলোই prime। জানালার বাঁ ধার থেকে প্রথম ছাপ কোথায় পড়বে — সেই offset হিসাবটাই আসল কসরত।

Worked ASCII example 1: extended Euclid-এর সিঁড়ি (gcd(99, 78))¶

নামা ▼                                ওঠা ▲ (back-substitution)
─────────────────────                 ──────────────────────────────────
99 = 1·78 + 21                        3 = 78 − 3·21                 ◀ শুরু এখান থেকে
78 = 3·21 + 15                          = 78 − 3·(99 − 1·78)
21 = 1·15 + 6                           = 4·78 − 3·99
15 = 2·6  + 3   ◀ gcd = 3            আর বিস্তারিত মাঝের ধাপগুলো:
 6 = 2·3  + 0                         3 = 15 − 2·6
                                      6 = 21 − 1·15  ⇒ 3 = 3·15 − 2·21
                                      15 = 78 − 3·21 ⇒ 3 = 3·78 − 11·21
                                      21 = 99 − 78   ⇒ 3 = 14·78 − 11·99

ফল: 99·(−11) + 78·(14) = −1089 + 1092 = 3 ✓     x = −11, y = 14

ছবির শিক্ষা: নামার প্রতিটা লাইন উঠার সময় একবার করে ব্যবহার হয় — কিছুই নষ্ট হয় না, পথটাই উত্তর।

Worked ASCII example 2: CRT-র দুই ঘড়ি (x ≡ 2 mod 3, x ≡ 3 mod 5)¶

x      : 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
ঘড়ি-3  : 0  1  2  0  1  2  0  1  2  0  1  2  0  1  2
ঘড়ি-5  : 0  1  2  3  4  0  1  2  3  4  0  1  2  3  4
চাই    :       ▲ঘড়ি-3 = 2 এখানে...
ঘড়ি-3=2:        ✓        ✓        ✓        ✓
ঘড়ি-5=3:           ✓              ✓              (x=3, 8, 13)
দুটোই  :                          ★ x = 8

8-এর পরে আবার কবে? দুই ঘড়িই reset হয় lcm(3,5) = 15 পরপর → x = 8, 23, 38, ...
উত্তর: x ≡ 8 (mod 15)

ছবির শিক্ষা: CRT = দুই চক্রের ছন্দ মেলানো; coprime হলে এক পূর্ণ চক্রে (15) ঠিক একবারই মেলে।

Worked ASCII example 3: matrix exponentiation-এর gear box (F(13))¶

n = 13 = 1101₂ — জ্বলা bit: 8, 4, 1

squaring-এ gear বানানো:           M¹ ──sq──▶ M² ──sq──▶ M⁴ ──sq──▶ M⁸
n-এর bit (ডান থেকে):               1          0          1          1
result-এ জোড়া:                     ✓ M¹       ✗          ✓ M⁴       ✓ M⁸

R = M¹ · M⁴ · M⁸ = M¹³            মোট গুণ: 3 squaring + 3 জোড়া = 6 (13 নয়!)

Fibonacci check (mod ছাড়া):
M = [1 1]    M¹³-এর [0][1] ঘর = F(13) = 233
    [1 0]    হাতে মেলাও: 1 1 2 3 5 8 13 21 34 55 89 144 233 ✓

ছবির শিক্ষা: binary exponentiation-এর কঙ্কালটা অপরিবর্তিত — level 2-তে সংখ্যায় করেছিলে, এখানে শুধু "গুণ"-এর সংজ্ঞা বদলে matrix multiplication হয়ে গেছে। Operation associative হলেই এই কৌশল চলে।

নিজে আঁকার চ্যালেঞ্জ¶

μ-এর সংখ্যারেখা 1 থেকে 30 পর্যন্ত আঁকো — +1 উপরে, −1 নিচে, 0 মাঝে dot; square-গুণিতকের ঘরে কেন সব 0 — রঙ দিয়ে দেখাও
Pollard rho-র ধারা f(x) = (x² + 1) mod 33, শুরু x = 2 — মানগুলো বের করে ρ-আকৃতিটা আঁকো, কচ্ছপ-খরগোশ কোথায় মেলে চিহ্নিত করো
Segmented sieve-এ L = 50, R = 70, prime stamp {2, 3, 5, 7} — প্রতিটা stamp-এর প্রথম ছাপের ঘর হিসাব করে জানালাটা এঁকে ফেলো