Conway polynomial (finite fields)
ریاضی میں، کونوے کثیر الجہتی سی پی، این محدود فیلڈ ایف پی این کے لیے ایف پی این پر ڈگری این کا ایک خاص ناقابل تلافی کثیر الجہتی ہے جو ایف پی این کی معیاری نمائندگی کو سی پی، این کے تقسیم فیلڈ کے طور پر بیان کرنے کے لیے استعمال کیا جا سکتا ہے۔ کونوے کثیرالجہتی کا نام جان ایچ کونوے کے نام پر رچرڈ اے پارکر نے رکھا تھا، جو ان کی وضاحت کرنے اور مثالوں کا حساب لگانے والے پہلے شخص تھے۔ کونوے کثیر الجہتی ایک مخصوص مطابقت کی شرط کو پورا کرتے ہیں جو کونوے نے کسی فیلڈ کی نمائندگی اور اس کے ذیلی فیلڈز کی نمائندگی کے درمیان تجویز کی تھی۔ وہ کمپیوٹر الجبرا میں اہم ہیں جہاں وہ مختلف ریاضیاتی ڈیٹا بیس اور کمپیوٹر الجبرا سسٹمز کے درمیان پورٹیبلٹی فراہم کرتے ہیں۔ چونکہ کونوے کثیر الجہتی شمار کرنے کے لیے مہنگے ہوتے ہیں، اس لیے انہیں عملی طور پر استعمال کرنے کے لیے ذخیرہ کیا جانا چاہیے۔ کونوے کثیر الجہتی کے ڈیٹا بیس کمپیوٹر الجبرا سسٹمز جی اے پی، میکالے 2، میگما، سیج میتھ، اور فرینک لیوبیک کی ویب سائٹ پر دستیاب ہیں۔ ایف پی این کے پس منظر کے عناصر کو −1βn −1 +. + a1β + a0 کی شکل کے مجموعے کے طور پر پیش کیا جا سکتا ہے جہاں β Fp پر ڈگری n کے ناقابل تلافی کثیر الجہتی کا جڑ ہے اور aj Fp کے عناصر ہیں۔ اس نمائندگی میں فیلڈ عناصر کا اضافہ محض ویکٹر کا اضافہ ہے۔ اگرچہ آئسومورفزم تک آرڈر pn کا ایک منفرد محدود فیلڈ ہے، لیکن فیلڈ عناصر کی نمائندگی کا انحصار ناقابل تلافی کثیر الجہتی کے انتخاب پر ہوتا ہے۔ کونوے کثیر الجہتی اس انتخاب کو معیاری بنانے کا ایک طریقہ ہے۔ ایک محدود میدان کے غیر صفر عناصر ضرب کے تحت ایک چکور گروہ بناتے ہیں۔ ایف پی این کا ایک ابتدائی عنصر، α، ایک ایسا عنصر ہے جو اس گروپ کو پیدا کرتا ہے۔ غیر صفر فیلڈ عناصر کو α کی طاقتوں کے طور پر پیش کرنے سے فیلڈ میں ضرب کو مؤثر طریقے سے انجام دیا جا سکتا ہے۔ α کے لیے ابتدائی کثیر الجہتی Fp میں کوفیشنٹس کے ساتھ سب سے چھوٹی ممکنہ ڈگری کا مونیک کثیر الجہتی ہے جس میں α Fpn میں جڑ کے طور پر ہے (α کے لیے کم از کم کثیر الجہتی)۔ یہ لازمی طور پر ناقابل تلافی ہے۔ کونوے کثیر الجہتی کو ابتدائی ہونے کے لیے منتخب کیا جاتا ہے، تاکہ اس کی ہر جڑ متعلقہ محدود فیلڈ کا ضرب گروپ پیدا کرے۔ ایف پی این کے ذیلی فیلڈز ایف پی ایم فیلڈز ہیں جن میں ایم تقسیم کرتا ہے۔ ایف پی ایم کے غیر صفر عناصر سے تشکیل پانے والا چکور گروپ ایف پی این کے چکور گروپ کا ایک ذیلی گروپ ہے۔ اگر α مؤخر الذکر پیدا کرتا ہے، تو α کی سب سے چھوٹی طاقت جو سابقہ پیدا کرتی ہے وہ αr ہے جہاں r = (pn−1)/(pm−1) ہے۔ اگر fn جڑ α کے ساتھ Fpn کے لیے ایک ابتدائی کثیر الجہتی ہے، اور اگر fm ایف پی ایم کے لیے ایک ابتدائی کثیر الجہتی ہے، تو کونوے کی تعریف کے مطابق، fm اور fn مطابقت رکھتے ہیں اگر αr fm کا جڑ ہے۔ اس کے لیے ضروری ہے کہ fm (x) fn (xr) کو تقسیم کرے۔ مطابقت کے اس تصور کو کچھ مصنفین معمول کی مطابقت کہتے ہیں۔ ایک محدود فیلڈ کے لیے کونوے کثیر الجہتی کا انتخاب کیا جاتا ہے تاکہ اس کے ہر ذیلی فیلڈ کے کونوے کثیر الجہتی کے ساتھ مطابقت ہو۔ یہ کہ اس طریقے سے انتخاب کرنا ممکن ہے، ورنر نکل نے ثابت کیا۔ تعریف کونوے کثیر الجہتی سی پی، این کی تعریف لغت کے لحاظ سے کم سے کم مونیک ابتدائی کثیر الجہتی ڈگری این اوور ایف پی کے طور پر کی گئی ہے جو سی پی کے ساتھ مطابقت رکھتی ہے، تمام ایم تقسیم کرنے والے این کے لیے ایم۔ یہ این پر ایک تعمیری تعریف ہے: بیس کیس سی پی، 1 (x) = x−α ہے جہاں α لغت کے لحاظ سے ایف پی کا کم سے کم قدیم عنصر ہے۔ استعمال شدہ لغت کی ترتیب کا تصور درج ذیل ہے: Fp کے عناصر کو 0 <1 <2 <. <p−1 ترتیب دیا گیا ہے۔ Fp [x] میں ڈگری d کا کثیر الجہتی adxd − ad − 1xd − 1 +. + (−1) ga0 لکھا جاتا ہے اور پھر لفظ adad − 1. a0 کے طور پر ظاہر کیا جاتا ہے۔ ڈگری d کے دو کثیر الجہتی کو ان کے متعلقہ الفاظ کی لغت کی ترتیب کے مطابق ترتیب دیا جاتا ہے۔ چونکہ ایسا کوئی قدرتی ریاضیاتی معیار نظر نہیں آتا جو ایک مونیک ابتدائی کثیر الجہتی کو دوسرے تمام پر مطابقت کے حالات کو مطمئن کرے، اس لیے کونوے کثیر الجہتی کی تعریف میں لغت کی ترتیب کے نفاذ کو ایک روایت سمجھا جانا چاہیے۔ کونوے کثیر الجہتی کی کمپیوٹنگ کے لیے کمپیوٹیشن الگورتھم جو بروٹ فورس سرچ سے زیادہ موثر ہیں ہیتھ اور لوہر نے تیار کیے ہیں۔ لیوبیک اشارہ کرتا ہے کہ ان کا الگورتھم پارکر کے طریقہ کار کی دوبارہ دریافت ہے۔ نوٹس حوالہ جات فائنائٹ فیلڈز کمپیوٹر الجبرا جان ہارٹن کونوے