میدان متناهی
در ریاضیات، یک میدان متناهی یا میدان گالوا که به افتخار اواریست گالوا نامگذاری شده‌است، یک میدان است که شامل تعداد متناهی عنصر است. مثل هر میدانی، یک میدان متناهی یک مجموعه‌ای است که روی آن عملیات ضرب، جمع، تفریق و تقسیم تعریف شده و قواعد مبنایی معینی را برآورده می‌سازد. معمول‌ترین مثال‌های میدان متناهی همان میدان اعداد در پیمانه است که در آن یک عدد اول است.
"مرتبه" یک میدان متناهی همان تعداد عناصر آن است، که این مرتبه یا یک «عدد اول» است یا یک «» است. برای هر عدد اول و هر عدد صحیح مثبت میدان‌هایی از مرتبه formula_1 وجود دارد که همه آن‌ها یکریخت هستند.
مفهوم "میدان متناهی" در تعدادی از حوزه‌های ریاضیات و علوم رایانه، شامل نظریه اعداد، هندسه جبری، نظریه گالوا، هندسه متناهی، رمزنگاری و نظریه کدگذاری یک مفهوم بنیادین است.
یک میدان متناهی یک مجموعه متناهی است که یک میدان هم هست؛ یعنی ضرب، جمع، تفریق، و تقسیم (به استثنای تقسیم بر صفر) در آن تعریف شده‌است و قواعد حسابی که اصول موضوع میدان نام‌دارد را برآورده می‌سازد.
تعداد عناصر یک میدان متناهی «"مرتبه»" آن یا گاهی "اندازه (سایز)" آن نامیده می‌شود. یک میدان متناهی مرتبه وجود دارد، اگر وتنها اگر یک نمای اول باشد (که در آن یک عدد اول است و یک عدد صحیح مثبت است). در یک میدان از مرتبه جمع نسخه از هر عنصر، همیشه منجر به صفر می‌شود؛ یعنی مشخصه میدان برابر است.
اگر باشد، همه میدان‌های از مرتبه یکریخت هستند (بخش وجود و یکتایی را در زیر ببینید). بعلاوه، یک میدان نمی‌تواند شامل دو زیرمیدان متناهی متفاوت با یک مرتبه یکسان باشد. از این‌رو می‌توان همه میدان‌های متناهی با یک مرتبه یکسان را شناسایی کرد، و به صورت غیرمبهم توسط formula_2، ، یا نشان داد، که در آن حروف GF مخفف «میدان گالوا» یا "Galois field" است.
در یک میدان متناهی از مرتبه ، چندجمله‌ای دارای ریشه‌هایی شامل همه عنصر از میدان متناهی است. عناصر غیرصفر از یک میدان متناهی یک را می‌سازد. این گروه، یک گروه دوری است، از این رو همه عناصر غیرصفر را می‌توان به صورت توان‌های یک عنصر منفرد که «» میدان نام‌دارد، بیان کرد. (در کل برای یک میدان ممکن است چندین عنصر اصلی وجود داشته باشد).
ساده‌ترین مثال‌های میدان‌های متناهی همان میدان‌های مرتبه اول هستند: برای هر عدد اول میدان اول از مرتبه یعنی formula_3 را می‌توان به صورت اعداد صحیح در پیمانه یا ساخت.
عناصر میدان اول از مرتبه توسط اعداد صحیح در محدوده نمایش داده می‌شود. جمع، تفریق، و ضرب همان باقیمانده تقسیم بر از نتیجه عملیات عدد صحیح متناظر هستند. وارون ضربی یک عنصر توسط الگوریتم اقلیدسی تعمیم‌یافته محاسبه می‌شود ( را ببینید).
فرض کنید که یک میدان متناهی باشد. برای هر عنصر در و هر عدد صحیح ، جمع نسخه از توسط نمایش داده می‌شود. کمترین مثبتی که در آن است برابر مشخصه میدان است. این موضوع امکان تعریف ضرب formula_4 از یک عنصر از را در یک عنصر از می‌دهد، این کار با انتخاب یک عدد صحیح نماینده برای انجام می‌شود. این ضرب را داخل یک -فضای برداری وارد می‌کند. این منجر به آن می‌شود که تعداد عناصر برابر باشد که در آن یک عدد صحیح است.
اتحاد (که گاهی نامیده می‌شود) در یک میدان با مشخصه درست است. این از قضیه بسط دوجمله‌ای نتیجه شده‌است، به این دلیل که هر ضریب دوجمله‌ای در بسط ، بجز اولین و آخرین ضریب، یک مضرب است.
از روی قضیه کوچک فرما، اگر یک عدد اول و در میدان باشد آنوقت است. این منجر به تساوی زیر برای چندجمله‌ای‌های روی می‌شود. به صورت کلی‌تر، هر عنصر در تساوی چندجمله‌ای را برآورده می‌کند.
هر بسط میدان متناهی از یک میدان متناهی، قابل‌تفکیک و ساده است؛ یعنی اگر یک میدان متناهی باشد، و یک زیرمیدان باشد، آنوقت از قابل دستیابی است، اینکار از طریق مجاروت یک عنصر منفرد که چندجمله‌ای کمینه‌ای آن قابل تفکیک است، انجام می‌شود. در اصطلاح تخصصی، میدان‌های متناهی هستند.
یک ساختار جبری کلی‌تر که همه اصول موضوعی دیگر یک میدان، غیر از این اصل که ضرب آن لازم نیست حتماً جابجایی‌پذیری باشد، را برآورده می‌کند، یک حلقه تقسیم (یا گاهی "میدان کج") نامیده می‌شود. از روی ، هر حلقه تقسیم متناهی، جابجایی‌پذیر است، و از این‌رو یک میدان متناهی است.
فرض کنید یک نمای اول باشد، و میدان شکافنده چندجمله‌ای روی میدان اول باشد. این یعنی یک میدان متناهی از پایین‌ترین مرتبه است، که در آن دارای تا ریشه متمایز است ( برابر است که یعنی ، که در کل یعنی میدان شکافنده یک از میدان اصلی است). اتحاد بالا نشان می‌دهد که جمع و ضرب دو ریشه هم ریشه است، همچنین وارون ضربی یکی از باز هم یک ریشه آن است. به زبان دیگر، ریشه‌های یک میدان از مرتبه می‌سازند که بر اساس کمینه‌بودن میدان شکافنده برابر است.
یکتایی به دلیل یکریختی میدان‌های شکافنده رخ‌می‌دهد که این یعنی همه میدان‌های مرتبه یکریخت هستند. همچنین، اگر یک میدان یک زیرمیدان از مرتبه داشته باشد، عناصر آن ریشه از هستند، و نمی‌تواند شامل زیرمیدان دیگری از مرتبه باشد.
به صورت خلاصه، ما این قضیه طبقه‌بندی را داریم که اولین‌بار در سال ۱۸۹۳ توسط اثبات شد:
این منجر به آن می‌شود که شامل یک زیرمیدان یکریخت با باشد اگر و فقط اگر یک مقسوم‌علیه باشد؛ در این حالت، این زیرمیدان یکتا است. در حقیقت، چندجمله‌ای چندجمله‌ای را اگر و فقط اگر در صورتی تقسیم می‌کند که یک مقسوم‌علیه باشد.
اگر یک نمای اول داشته باشیم که در آن اول است و است، میدان را به این روش می‌توان به صورت صریح ساخت. اول را در از درجه انتخاب کنید (چنین چندجمله‌ای غیرقابل‌کاهشی همیشه موجود است)، آنوقت حلقه خارج‌قسمتی از حلقه چندجمله‌ای توسط ایده‌آل تولید شده توسط ، یک میدان از مرتبه است.
به صورت صریح‌تر، عناصر چندجمله‌ای‌هایی روی هستند که درجه‌شان به صورت اکید کمتر از است. جمع و تفریق آن‌ها همان جمع و تفریق چندجمله‌ای‌ها روی است. ضرب دو عنصر برابر باقیمانده در از ضرب در است. وارون ضربی از یک عنصر غیرصفر را می‌توان توسط الگوریتم اقلیدسی تعمیم‌یافته محاسبه کرد؛ الگوریتم تعمیم‌یافته اقلیدس#بسط‌های میدان جبری ساده را ببینید.
به جز در ساخت ، چندین گزینه ممکن برای وجود دارد، که همه، نتایج یکریخت تولید می‌کنند. برای ساده‌سازی تقسیم اقلیدسی، معمولاً می‌توان برای یک چندجمله‌ای از حالت زیر انتخاب کرد این موضوع تقسیم‌های اقلیدسی لازم را خیلی کارا می‌سازد. با این حال، برای بعضی از میدان‌ها، معمولاً میدان‌های با مشخصه ، ممکن است چندجمله‌ای‌های غیرقابل‌کاهش از حالت موجود نباشد. در مشخصه ، اگر چندجمله‌ای کاهش‌پذیر باشد، پیشنهاد می‌شود که را با کمترین ممکن انتخاب کرد، که این باعث می‌شود چندجمله‌ای غیرقابل‌کاهش شود. اگر همه این سه‌جمله‌ای‌ها کاهش‌پذیر باشد، می‌توان «پنج‌جمله‌ای» را انتخاب کرد، زیرا چندجمله‌ای‌های با درجه بزرگتر از ، با تعداد جمله زوج، در مشخصه هیچ‌وقت غیرقابل‌کاهش نیستند، زیرا ریشه را دارند.
یک گزینه ممکن برای چنین چندجمله‌ای توسط داده می‌شود. اینکار باعث اطمینان از یک سازگاری معین بین نمایش یک میدان و نمایش زیرمیدان‌هایش می‌شود.
در بخش‌های بعد، نشان می‌دهیم که چطور شگرد ساخت کلی ذکر شده در بالا برای میدان‌های متناهی کوچک کار می‌کند.
کوچکترین میدان غیراول، همان میدان چهار عنصره است، که معمولاً توسط یا formula_12 نشان‌داده می‌شود. این شامل چهار عنصر formula_13 است به اینصورت که formula_14 formula_15 formula_16 و formula_17 برای هر formula_18 است. دیگر نتایج عملیاتی به سادگی توسط قانون توزیع‌پذیری قابل استنتاج است. زیر را برای جداول عملیاتی کامل ببینید.
این موضوع به صورت زیر از نتایج بخش قبل قابل‌استنتاج است.
روی ، فقط یک از درجه موجود است: بنابراین، برای ، روش ساخت بخش قبل باید این چندجمله‌ای را درگیر کند و
فرض کنید به یک ریشه از این چندجمله‌ای در اشاره کند. این یعنی و اینکه و همان عناصر هستند، که در موجود نیستند. جداول عملیات از این نتیجه می‌شود، و به صورت زیر است:
جدولی برای تفریق داده نشده‌است، زیرا تفریق معادل جمع است، این موضوع برای هر میدان از مشخصه ۲ درست است. در جدول سوم، یعنی تقسیم در ، مقادیر باید از ستون چپ خوانده شود، و مقادیر باید ردیف بالا خوانده شود. (به این دلیل که برای هر در هر حلقه درست است، تقسیم بر ۰ باید تعریف‌نشده باقی بماند)
نگاشت یک خودریختی میدانی غیربدیهی است، که نام دارد که را به ریشه دوم از چندجمله‌ای غیرقابل‌کاهش ذکر شده در بالا، یعنی formula_22 می‌فرستد.