متناہی میدان

عام میدان میں ارکان کی تعداد لامتناہی ہو سکتی ہے۔ "متناہی میدان" ایسے میدان کو کہتے ہیں جس میں ارکان کی تعداد متناہی ہو۔ انگریزی میں اسے Finite Field یا Galois Field کہا جاتا ہے۔ اس کی مثال مفرد عدد $p$ کے متناہی میدان ${𝔽}_p$ ہے، جس کے ارکان کو

${𝔽}_p=\{0,1,2,\cdots ,p-1\}$

لکھا جاتا ہے۔ یہاں جمع، ضرب کو $p$ کے چکر پر نکالا جاتا ہے۔ انگریزی میں اسے modulo یا $modp$ کہتے ہیں۔ مثال کے طور پر ${𝔽}_7=\{0,1,2,3,4,5,6\}$ میں جمع، ضرب کے عمل کو دیکھتے ہیں۔ عام طور پر، $5+6=11$ مگر 11 کو متناہی میدان میں لانے کے لیے ہم 11 میں سے 7 منفی کر سکتے ہیں، یعنی

$5+6=4(note:11-7=4,11mod7\equiv 4)$

$5-6=6(note:-1+7=6)$

$5\times 6=2(note:30-7\times 4=2)$

گویا آپ جمع یا ضرب کے نتیجے میں پیدا ہونے والے عدد میں سے $p=7$ کو جتنی مرتبہ ضروری ہو جمع یا تفریق کر سکتے ہو حتٰی کہ جواب $\{0,1,\cdots ,p-1\}$ میں آ جائے۔

اب ${𝔽}_5=\{0,1,2,3,4\}$ میں جمع کا جدول یوں ہو گا:

${𝔽}_5$ میں جمع

$+$	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

اور ${𝔽}_5$ میں ضرب کا جدول یوں ہو گا:

${𝔽}_5$ میں ضرب

$\times$	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

اور ${𝔽}_5$ میں جمعیاتی اُلٹ کا جدول:

${𝔽}_5$ میں جمع الٹ

رکن	اُلٹ (جمع)
0	0
1	4
2	3
3	2
4	1

مثلاً ،اس کا مطلب ہے کہ ${𝔽}_5$ میں:

$-4=1$

$4+(-4)=4+1=0$

اور ${𝔽}_5$ میں ہر رکن کا ضربی اُلٹ کا جدول:

${𝔽}_5$ میں ضرب الٹ

رکن	اُلٹ (ضرب)
0
1	1
2	3
3	2
4	4

مثلاً ،اس کا مطلب ہے کہ ${𝔽}_5$ میں:

$2^{-1}=3$

$2\times 2^{-1}=2\times 3=1$

متناہی میدان کے ایسے اجزا جن کی طاقت پر متناہی میدان کے تمام اجزا نکلتے ہوں (سوائے صفر (0) کے ) کو "قدیم" (primitive) اجزاء کہتے ہیں۔ خیال کرو کہ متناہی میدان ${𝔽}_p$ کے کسی بھی جُز $\alpha \ne 0$ کے لیے ${\alpha }^{p-1}=1$۔ مثال کے طور پر متناہی میدان ${𝔽}_7$ میں 3 اور 5 قدیم جُز ہیں، جن کی طاقت کے جدول یوں ہیں:

میدان ${𝔽}_7$ میں قدیم عدد 3 کی طاقت پر

$1=3^0$

$3=3^1$

$2=3^2$

$6=3^3$

$4=3^4$

$5=3^5$

میدان ${𝔽}_7$ میں قدیم عدد 5 کی طاقت پر

$1=5^0$

$5=5^1$

$4=5^2$

$6=5^3$

$2=5^4$

$3=5^5$

اس طرح ہم متناہی میدان میں متفرد لاگرتھم کی بات کر سکتے ہیں۔ اوپر طاقت کے جدول استعمال کرتے ہوئے ہم ${𝔽}_7$ میں قدیم جز 3کے حوالے سے ${𝔽}_7$ میں لاگرتھم کا جدول یوں لکھ سکتے ہیں۔

میدان ${𝔽}_7$ میں قدیم عدد 3 کے حوالے سے لاگرتھم

$0={\log }_3(1)$

$2={\log }_3(2)$

$1={\log }_3(3)$

$4={\log }_3(4)$

$5={\log }_3(5)$

$3={\log }_3(6)$

جب مفرد عدد $p$ بڑا ہو تو ${𝔽}_p$ میں کسی جز کی طاقت نکالنا تو آسان ہوتا ہے، مگر کسی جز کا لاگرتھم نکالنا انتہائی دشوار مسلئہ ثابت ہوتا ہے۔ اس مسلئہ کی دشواری کی بنیاد پر عوامی کنجی کرپٹوگرافی (public key cryptography) کے طریقے بنائے گئے ہیں۔

کمپوٹر کی دنیا میں خاصا زیادہ استعمال ہونے والا متناہی میدان ${𝔽}_2=\{0,1\}$ ہے۔ ${𝔽}_2$ میں

$-1=1$

$1+1=0$

متناہی میدان ${𝔽}_2$ پر کثیر رقمی

ایسے کثیر رقمی جن کے عددی سر ${𝔽}_2$ کے ارکان ہوں، ${𝔽}_2$ پر کثیر رقمی کہلاتے ہیں۔ ان کثیر رقمی پر الجبرا کے اصول لاگو ہوتے ہیں، مگر عددی سر کی جمع، ضرب ${𝔽}_2$ میں ہوتی ہے۔ مثلاً جمع

$p_1(x)=1+x,p_2(x)=1+x+x^2$

$p_1(x)+p_2(x)=1+x+1+x+x^2=1+1+x+x+x^2=0+0x+x^2=x^2$ اور ضرب $p_1(x)p_2(x)=(1+x)(1+x+x^2)=1+x+x^2+x+x^2+x^3$ $=1+x+x+x^2+x^2+x^3=1+0x+0x^2+x^3=1+x^3$

عملیات

برقی پیغامات کو ${𝔽}_2$ کے سلسلہ کے طور پر لکھا جاتا ہے۔ مثلاً، ایک لمبائی 11 کا پیغام: $msg=10100011111$

اس پیغام کے سلسلہ کو ہم ${𝔽}_2$ پر ایک کثیر رقمی کے بطور یوں لکھ سکتے ہیں:

$msg(x)=1+0x+x^2+0x^3+0x^4+0x^5+x^6+x^7+x^8+x^9+x^{10}$ $=1+x^2+x^6+x^7+x^8+x^9+x^{10}$

برقی پیغامات کی ترسیل سے پہلے پیغام کے ساتھ کچھ اضافی عدد لگا دیے جاتے ہیں، جن کی مدد سے وصول کندہ پیغام کی صحت کے بارے اندازہ لگا سکتا ہے۔ ترسیل میں پیغام کے کچھ اعداد کے غلط وصول ہونے کا امکان ہمیشہ موجود ہوتا ہے۔ ان اضافی اعداد کو CRC چکری وفر جائزہ (cyclic redundancy check) کہا جاتا ہے، جو ایک CRC کثیر رقمی کی مدد سے نکالے جاتے ہیں۔ مثلاً اگر ہم پیغام کے آخر میں صرف ایک اضافی عدد نتھی کرنا چاہیں، تو درجہ ا کا یہ کثیر رقمی استعمال کر سکتے ہیں: $crc(x)=1+x$

اب $x\times msg(x)$ کو $crc(x)$ سے لمبی تقسیم کرنے کے بعد جو $R(x)$ بچے

$x^{deg(crc(x))}msg(x)=q(x)crc(x)+R(x)$

$x^{1}msg(x)=q(x)crc(x)+R(x)$

$x(1+x^2+x^6+x^7+x^8+x^9+x^{10})=q(x)(1+x)+R(x),$ $q(x)=x^9+x^7+x^5+x^4+x^3+x^2,R(x)=1$

اس $R(x)$ کو اضافی عدد (اعداد) کے طور پر پیغام کے آخر میں نتھی کر دیتے ہیں۔ اس طرح "1" کے اضافے سے بھیجے جانے والا برقی پیغام بن جائے گا، لمبائی 12 کے ساتھ: $c\mathrm{\_}msg=110100011111$ وصول کندہ اس پیغام کے کسر رقمی کو $crc(x)$ سے تقسیم کر کے اطمینان کرے گا کہ یہ $crc(x)$ سے پورا تقسیم ہوتا ہے۔