محدود میدان

وکیپیڈیا سے

عام میدان میں ارکان کی تعداد لامحدود ہو سکتی ہے۔ "محدود میدان" ایسے میدان کو کہتے ہیں جس میں ارکان کی تعداد محدود ہو۔ انگریزی میں اسے Finite Field یا Galois Field کہا جاتا ہے۔ اس کی مثال پرائم عدد $\ p$ کے محدود میدان $\mathbb{F}_p$ ہے، جس کے ارکان کو

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

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

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

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

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

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

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

$\mathbb{F}_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

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

$\mathbb{F}_5$ میں ضرب
$\times$	1	2	3	4
0	0	0	0	0
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

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

$\mathbb{F}_5$ میں جمع الٹ
رکن	اُلٹ (جمع)
0	0
1	4
2	3
3	2
4	1

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

$\ -4 = 1$

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

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

$\mathbb{F}_5$ میں ضرب الٹ
رکن	اُلٹ (ضرب)
0
1	1
2	3
3	2
4	4

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

$\ 2^{-1} = 3$

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

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

میدان $\mathbb{F}_7$ میں قدیم عدد 3 کی طاقت پر
$\ 1= 3^0$
$\ 3 = 3^1$
$\ 2 = 3^2$
$\ 6= 3^3$
$\ 4= 3^4$
$\ 5= 3^5$

میدان $\mathbb{F}_7$ میں قدیم عدد 5 کی طاقت پر
$\ 1= 5^0$
$\ 5= 5^1$
$\ 4= 5^2$
$\ 6= 5^3$
$\ 2= 5^4$
$\ 3= 5^5$

اس طرح ہم محدود میدان میں ڈسکریٹ لاگرتھم (discrete logarithm) کی بات کر سکتے ہیں۔ اوپر طاقت کے جدول استعمال کرتے ہوئے ہم $\mathbb{F}_7$ میں قدیم جز 3کے حوالے سے $\mathbb{F}_7$ میں لاگرتھم کا جدول یوں لکھ سکتے ہیں۔

میدان $\mathbb{F}_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$ بڑا ہو تو $\mathbb{F}_p$ میں کسی جز کی طاقت نکالنا تو آسان ہوتا ہے، مگر کسی جز کا لاگرتھم نکالنا انتہائی دشوار مسلئہ ثابت ہوتا ہے۔ اس مسلئہ کی دشواری کی بنیاد پر عوامی کنجی کرپٹوگرافی (public key cryptography) کے طریقے بنائے گئے ہیں۔

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

$\ -1=1$

$\ 1+1=0$

[ترمیم کریں] محدود میدان $\mathbb{F}_2$ پر کثیر رقمی

ایسے کثیر رقمی جن کے عددی سر $\mathbb{F}_2$ کے ارکان ہوں، $\mathbb{F}_2$ پر کثیر رقمی کہلاتے ہیں۔ ان کثیر رقمی پر الجبرا کے اصول لاگو ہوتے ہیں، مگر عددی سر کی جمع, ضرب $\mathbb{F}_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+ 0 x^2 + x^3 = 1 + x^3$

[ترمیم کریں] عملیات

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

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

$\ msg(x) = 1 + 0 x + x^2 + 0 x^3 + 0 x^4 + 0 x^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 (سائیکلیک رئیڈنڈینسی چیک) کہا جاتا ہے، جو ایک 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\_msg = 110100011111$ وصول کندہ اس پیغام کے کسر رقمی کو $\ crc(x)$ سے تقسیم کر کے اطمینان کرے گا کہ یہ $\ crc(x)$ سے پورا تقسیم ہوتا ہے۔

              اردو ویکیپیڈیا پر مساوات کو بائیں سے دائیں (LTR) پڑھیۓ           ریاضی علامات

Retrieved from "http://ur.wikipedia.org../../../%D9%85/%D8%AD/%D8%AF/%D9%85%D8%AD%D8%AF%D9%88%D8%AF_%D9%85%DB%8C%D8%AF%D8%A7%D9%86.html"

زمرہ جات: ریاضیات | دس بڑے

We provide Linux to the World

محدود میدان

وکیپیڈیا سے

[ترمیم کریں] محدود میدان $\mathbb{F}_2$ پر کثیر رقمی

[ترمیم کریں] عملیات

Views

رہنمائی

ساتھی منصوبے

تلاش

دیگر زبانیں

We provide Linux to the World

محدود میدان

وکیپیڈیا سے

[ترمیم کریں] محدود میدان پر کثیر رقمی

[ترمیم کریں] عملیات

Views

رہنمائی

ساتھی منصوبے

تلاش

دیگر زبانیں

[ترمیم کریں] محدود میدان $\mathbb{F}_2$ پر کثیر رقمی