"میدان" کے نسخوں کے درمیان فرق

حذف شدہ مندرجات اضافہ شدہ مندرجات
کوئی خلاصۂ ترمیم نہیں
"محدود میدان" کا مضمون علیحدہ کر دیا
سطر 17:
 
[[مختلط عدد]] بھی ایک میدان تشکیل دیتے ہیں، جسے <math>\mathbb{C}</math> لکھا جاتا ہے۔
 
===محدود میدان===
عام اشاریہ اعداد کے میدان کے ارکان کی تعداد لامحدود ہے۔ "محدود میدان" ایسے میدان کو کہتے ہیں جس میں ارکان کی تعداد محدود ہو۔ انگریزی میں اسے Finite Field یا Galois Field کہا جاتا ہے۔ اس کی مثال پرائم عدد <math>\ p</math> کے محدود میدان <math>\mathbb{F}_p</math> ہے، جس کے ارکان کو
 
 
<math>\mathbb{F}_p=\{ 0,1,2,\cdots,p-1\}</math>
 
لکھا جاتا ہے۔ یہاں جمع، ضرب کو <math>\ p</math> کے چکر پر نکالا جاتا ہے۔ انگریزی میں اسے modulo یا <math>\ \mod p</math> کہتے ہیں۔ مثال کے طور پر
<math> \mathbb{F}_7 = \{0,1,2,3,4,5,6\} </math>
میں جمع، ضرب کے عمل کو دیکھتے ہیں۔
عام طور پر،
<math>\ 5 + 6 = 11 </math>
مگر 11 کو محدود میدان میں لانے کیلئے ہم 11 میں سے 7 منفی کر سکتے ہیں، یعنی
 
<math>\ 5 + 6 = 4 \,\,\,\,\, (note:\,\,\, 11-7=4 \,,\, 11 \mod 7 \equiv 4) </math>
 
<math>\ 5 - 6 = 6 \,\,\,\,\, (note:\,\,\, -1+7=6) </math>
 
<math>\ 5 \times 6 = 2 \,\,\,\,\, (note:\,\,\, 30-7\times4=2) </math>
 
گویا آپ جمع یا ضرب کے نتیجے میں پیدا ہونے والے عدد میں سے <math>\ p=7</math> کو جتنی مرتبہ ضروری ہو جمع یا تفریق کر سکتے ہو حتٰی کہ جواب <math>\ \{0,1,\cdots,p-1\}</math> میں آ جائے۔
 
 
 
اب <math>\mathbb{F}_5=\{0,1,2,3,4\} \,</math> میں جمع کا جدول یوں ہو گا:
<table border="1">
<caption><math>\mathbb{F}_5</math> میں جمع</caption>
<TR bgcolor="green">
<td><math>\ +</math></td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
</TR>
<tr>
<TD bgcolor="green"> 0</TD>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
</tr>
<tr>
<td bgcolor="green">1</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>0</td>
</tr>
<tr>
<td bgcolor="green">2</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td bgcolor="green">3</td>
<td>3</td>
<td>4</td>
<td>0</td>
<td>1</td>
<td>2</td>
</tr>
<tr>
<td bgcolor="green">4</td>
<td>4</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
</tr>
</table>
 
اور <math>\mathbb{F}_5</math> میں ضرب کا جدول یوں ہو گا:
<table border="1">
<caption><math>\mathbb{F}_5</math> میں ضرب </caption>
<tr bgcolor="green">
<td><math>\times</math></td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
</tr>
<tr>
<td bgcolor="green">0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td bgcolor="green">1</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
</tr>
<tr>
<td bgcolor="green">2</td>
<td>0</td>
<td>2</td>
<td>4</td>
<td>1</td>
<td>3</td>
</tr>
<tr>
<td bgcolor="green">3</td>
<td>0</td>
<td>3</td>
<td>1</td>
<td>4</td>
<td>2</td>
</tr>
<tr>
<td bgcolor="green">4</td>
<td>0</td>
<td>4</td>
<td>3</td>
<td>2</td>
<td>1</td>
</tr>
</table>
 
اور <math>\mathbb{F}_5</math> میں جمعیاتی اُلٹ کا جدول:
<table border="1">
<caption><math>\mathbb{F}_5</math> میں جمع الٹ</caption>
<tr>
<th>رکن</th>
<th>اُلٹ (جمع)</th>
</tr>
<tr>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>4</td>
</tr>
<tr>
<td>2</td>
<td>3</td>
</tr>
<tr>
<td>3</td>
<td>2</td>
</tr>
<tr>
<td>4</td>
<td>1</td>
</tr>
</table>
 
مثلاً ،اس کا مطلب ہے کہ <math>\mathbb{F}_5</math> میں:
 
<math>\ -4 = 1</math>
 
<math>\ 4 + (-4) = 4 + 1 = 0</math>
 
 
 
اور <math>\mathbb{F}_5</math> میں ہر رکن کا ضربی اُلٹ کا جدول:
<table border="1">
<caption><math>\mathbb{F}_5</math> میں ضرب الٹ</caption>
<tr>
<th>رکن</th>
<th>اُلٹ (ضرب)</th>
</tr>
<tr>
<td>0</td>
<td></td>
</tr>
<tr>
<td>1</td>
<td>1</td>
</tr>
<tr>
<td>2</td>
<td>3</td>
</tr>
<tr>
<td>3</td>
<td>2</td>
</tr>
<tr>
<td>4</td>
<td>4</td>
</tr>
</table>
 
مثلاً ،اس کا مطلب ہے کہ <math>\mathbb{F}_5</math> میں:
 
<math>\ 2^{-1} = 3</math>
 
<math>\ 2 \times 2^{-1} = 2 \times 3 = 1</math>
 
 
محدود میدان کے ایسے اجزا جن کی طاقت پر محدود میدان کے تمام اجزا نکلتے ہوں (سوائے صفر (0) کے) کو "قدیم" (primitive) اجزاء کہتے ہیں۔ خیال کرو کہ محدود میدان <math>\mathbb{F}_p</math> کے کسی بھی جُز <math>\ \alpha \ne 0</math> کے لیے <math>\ \alpha^{p-1} = 1</math> ۔ مثال کے طور پر محدود میدان <math>\mathbb{F}_7</math> میں 3 اور 5 قدیم جُز ہیں، جن کی طاقت کے جدول یوں ہیں:
 
<table align="left" >
<caption>
 
میدان <math>\mathbb{F}_7</math> میں قدیم عدد 3 کی طاقت پر
 
</caption>
<tr>
<td><math>\ 1= 3^0 </math></td>
</tr>
<tr>
<td><math>\ 3 = 3^1</math></td>
</tr>
<tr>
<td><math>\ 2 = 3^2</math></td>
</tr>
<tr>
<td><math>\ 6= 3^3 </math></td>
</tr>
<tr>
<td><math>\ 4= 3^4 </math></td>
</tr>
<tr>
<td><math>\ 5= 3^5 </math></td>
</tr>
</table>
 
<table align="center" >
<caption>
میدان <math>\mathbb{F}_7</math> میں قدیم عدد 5 کی طاقت پر
</caption>
<tr>
<td><math>\ 1= 5^0</math></td>
</tr>
<tr>
<td><math>\ 5= 5^1 </math></td>
</tr>
<tr>
<td><math>\ 4= 5^2 </math></td>
</tr>
<tr>
<td><math>\ 6= 5^3 </math></td>
</tr>
<tr>
<td><math>\ 2= 5^4 </math></td>
</tr>
<tr>
<td><math>\ 3= 5^5</math></td>
</tr>
</table>
 
اس طرح ہم محدود میدان میں ڈسکریٹ لاگرتھم (discrete logarithm) کی بات کر سکتے ہیں۔ اوپر طاقت کے جدول استعمال کرتے ہوئے ہم <math>\mathbb{F}_7</math> میں قدیم جز 3کے حوالے سے <math>\mathbb{F}_7</math> میں لاگرتھم کا جدول یوں لکھ سکتے ہیں۔
<table>
<caption>
میدان <math>\mathbb{F}_7</math> میں قدیم عدد 3 کے حوالے سے لاگرتھم
</caption>
<tr>
<td><math>\ 0=\log_3(1)</math></td>
</tr>
<tr>
<td><math>\ 2=\log_3(2) </math></td>
</tr>
<tr>
<td><math>\ 1=\log_3(3) </math></td>
</tr>
<tr>
<td><math>\ 4=\log_3(4) </math></td>
</tr>
<tr>
<td><math>\ 5=\log_3(5) </math></td>
</tr>
<tr>
<td><math>\ 3=\log_3(6)</math></td>
</tr>
</table>
جب پرائم عدد <math>\ p</math> بڑا ہو تو <math>\mathbb{F}_p</math> میں کسی جز کی طاقت نکالنا تو آسان ہوتا ہے، مگر کسی جز کا لاگرتھم نکالنا انتہائی دشوار مسلئہ ثابت ہوتا ہے۔ اس مسلئہ کی دشواری کی بنیاد پر [[عوامی کنجی کرپٹوگرافی]] (public key cryptography) کے طریقے بنائے گئے ہیں۔
 
 
کمپوٹر کی دنیا میں خاصا زیادہ استعمال ہونے والا محدود میدان <math>\mathbb{F}_2=\{0,1\} \,</math> ہے۔ <math>\mathbb{F}_2</math> میں
 
<math>\ -1=1</math>
 
<math>\ 1+1=0</math>
 
==== محدود میدان <math>\mathbb{F}_2</math> پر کثیر رقمی====
ایسے کثیر رقمی جن کے عددی سر <math>\mathbb{F}_2</math> کے ارکان ہوں، <math>\mathbb{F}_2</math> پر کثیر رقمی کہلاتے ہیں۔ ان کثیر رقمی پر الجبرا کے اصول لاگو ہوتے ہیں، مگر عددی سر کی جمع, ضرب <math>\mathbb{F}_2</math> میں ہوتی ہے۔ مثلاً جمع
 
<math>\ p_1(x) = 1 + x \,\,,\,\, p_2(x) = 1 + x + x^2 </math>
 
<math>\ p_1(x)+p_2(x) = 1+x +1 +x+ x^2 = 1+1 +x+ x + x^2 = 0 + 0x + x^2 = x^2</math>
اور ضرب
<math>\ p_1(x) p_2(x) = (1+x )(1 + x+ x^2) = 1 + x+ x^2 + x + x^2 + x^3 </math>
<math>\ = 1 + x+x + x^2 + x^2 + x^3 = 1 + 0x+ 0 x^2 + x^3 = 1 + x^3
</math>
 
 
====عملیات ====
برقی پعغامات کو <math>\mathbb{F}_2</math> کے سلسلہ کے طور پر لکھا جاتا ہے۔ مثلاً، ایک لمبائی 11 کا پیغام:
<math>\ msg = 10100011111 </math>
 
اس پیغام کے سلسلہ کو ہم <math>\mathbb{F}_2</math> پر ایک کثیر رقمی کے بطور یوں لکھ سکتے ہیں:
 
<math>\ 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}
</math>
<math>\ = 1 + x^2 + x^6 + x^7 + x^8 + x^9 + x^{10}</math>
 
برقی پیغامات کی ترسیل سے پہلے پیغام کے ساتھ کچھ اضافی عدد لگا دیے جاتے ہیں، جن کی مدد سے وصول کندہ پیغام کی صحت کے بارے اندازہ لگا سکتا ہے۔ ترسیل میں پیغام کے کچھ اعداد کے غلط وصول ہونے کا امکان ہمیشہ موجود ہوتا ہے۔ ان اضافی اعداد کو CRC (سائیکلیک رئیڈنڈینسی چیک) کہا جاتا ہے، جو ایک CRC کثیر رقمی کی مدد سے نکالے جاتے ہیں۔ مثلاً اگر ہم پیغام کے آخر میں صرف ایک اضافی عدد نتھی کرنا چاہیں، تو درجہ ا کا یہ کثیر رقمی استعمال کر سکتے ہیں:
<math>\ crc(x) = 1+ x </math>
 
اب <math>\ x \times msg(x)</math> کو <math>\ crc(x)</math> سے لمبی تقسیم کرنے کے بعد جو <math>\ R(x)</math> بچے
 
<math> x^{deg(crc(x))} msg(x) = q(x) crc(x) + R(x) \,</math>
 
<math> x^{1} msg(x) = q(x) crc(x) + R(x) \,</math>
 
<math> x (1 + x^2 + x^6 + x^7 + x^8 + x^9 + x^{10}) = q(x) (1+x) + R(x) \,,\, </math>
<math> q(x)=x^9+x^7+x^5+x^4+x^3+x^2 \,,\, R(x)=1 \,
</math>
 
اس <math>\ R(x)</math> کو اضافی عدد (اعداد) کے طور پر پیغام کے آخر میں نتھی کر دیتے ہیں۔ اس طرح "1" کے اضافے سے بھیجے جانے والا برقی پیغام بن جائے گا، لمبائی 12 کے ساتھ:
<math>\ c\_msg = 110100011111 </math>
وصول کندہ اس پیغام کے کسر رقمی کو <math>\ crc(x)</math> سے تقسیم کر کے اطمینان کرے گا کہ یہ <math>\ crc(x)</math> سے پورا تقسیم ہوتا ہے۔
 
 
سطر 349 ⟵ 23:
[[Category:دس بڑے]]
 
[[en:FiniteField field(mathematics)]]