میدان متناهی

الگو:Sidebar with collapsible lists در ریاضیات، یک میدان متناهی الگو:به انگلیسی یا میدان گالوا الگو:به انگلیسی که به افتخار اواریست گالوا نامگذاری شده‌است، یک میدان است که شامل تعداد متناهی عنصر است. مثل هر میدانی، یک میدان متناهی یک مجموعه‌ای است که روی آن عملیات ضرب، جمع، تفریق و تقسیم تعریف شده و قواعد مبنایی معینی را برآورده می‌سازد. معمول‌ترین مثال‌های میدان متناهی همان میدان [[هم‌نهشتی (نظریه اعداد)|اعداد در پیمانه الگو:Math]] است که در آن الگو:Math یک عدد اول است.

مرتبه الگو:به انگلیسی یک میدان متناهی همان تعداد عناصر آن است، که این مرتبه یا یک «عدد اول» است یا یک «نمای اول» است. برای هر عدد اول الگو:Mvar و هر عدد صحیح مثبت الگو:Mvar میدان‌هایی از مرتبه $p^k$ وجود دارد که همه آن‌ها یکریخت هستند.

مفهوم میدان متناهی در تعدادی از حوزه‌های ریاضیات و علوم رایانه، شامل نظریه اعداد، هندسه جبری، نظریه گالوا، هندسه متناهی، رمزنگاری و نظریه کدگذاری یک مفهوم بنیادین است.

ویژگی‌ها

یک میدان متناهی یک مجموعه متناهی است که یک میدان هم هست؛ یعنی ضرب، جمع، تفریق، و تقسیم (به استثنای تقسیم بر صفر) در آن تعریف شده‌است و قواعد حسابی که اصول موضوع میدان نام‌دارد را برآورده می‌سازد.

تعداد عناصر یک میدان متناهی «مرتبه» آن یا گاهی اندازه (سایز) آن نامیده می‌شود. یک میدان متناهی مرتبه الگو:Math وجود دارد، اگر وتنها اگر الگو:Math یک نمای اول الگو:Math باشد (که در آن الگو:Math یک عدد اول است و الگو:Math یک عدد صحیح مثبت است). در یک میدان از مرتبه الگو:Math جمع الگو:Math نسخه از هر عنصر، همیشه منجر به صفر می‌شود؛ یعنی مشخصه میدان برابر الگو:Math است.

اگر الگو:Math باشد، همه میدان‌های از مرتبه الگو:Mvar یکریخت هستند (بخش وجود و یکتایی را در زیر ببینید). بعلاوه، یک میدان نمی‌تواند شامل دو زیرمیدان متناهی متفاوت با یک مرتبه یکسان باشد. از این‌رو می‌توان همه میدان‌های متناهی با یک مرتبه یکسان را شناسایی کرد، و به صورت غیرمبهم توسط ${𝔽}_q$، الگو:Math، یا الگو:Math نشان داد، که در آن حروف GF مخفف «میدان گالوا» یا "Galois field" است.

در یک میدان متناهی از مرتبه الگو:Math، چندجمله‌ای الگو:Math دارای ریشه‌هایی شامل همه الگو:Math عنصر از میدان متناهی است. عناصر غیرصفر از یک میدان متناهی یک گروه ضربی را می‌سازد. این گروه، یک گروه دوری است، از این رو همه عناصر غیرصفر را می‌توان به صورت توان‌های یک عنصر منفرد که «عنصر اصلی» میدان نام‌دارد، بیان کرد. (در کل برای یک میدان ممکن است چندین عنصر اصلی وجود داشته باشد).

ساده‌ترین مثال‌های میدان‌های متناهی همان میدان‌های مرتبه اول هستند: برای هر عدد اول الگو:Math میدان اول از مرتبه الگو:Math یعنی ${𝔽}_p$ را می‌توان به صورت [[هم‌نهشتی (نظریه اعداد)|اعداد صحیح در پیمانه الگو:Mvar]] یا الگو:Math ساخت.

عناصر میدان اول از مرتبه الگو:Mvar توسط اعداد صحیح در محدوده الگو:Math نمایش داده می‌شود. جمع، تفریق، و ضرب همان باقیمانده تقسیم بر الگو:Math از نتیجه عملیات عدد صحیح متناظر هستند. وارون ضربی یک عنصر توسط الگوریتم اقلیدسی تعمیم‌یافته محاسبه می‌شود (الگو:Slink را ببینید).

فرض کنید که الگو:Math یک میدان متناهی باشد. برای هر عنصر الگو:Math در الگو:Math و هر عدد صحیح الگو:Math، جمع الگو:Math نسخه از الگو:Math توسط الگو:Math نمایش داده می‌شود. کمترین الگو:Math مثبتی که در آن الگو:Math است برابر مشخصه الگو:Mvar میدان است. این موضوع امکان تعریف ضرب $(k,x)\mapsto k\cdot x$ از یک عنصر الگو:Mvar از الگو:Math را در یک عنصر الگو:Mvar از الگو:Math می‌دهد، این کار با انتخاب یک عدد صحیح نماینده برای الگو:Mvar انجام می‌شود. این ضرب الگو:Math را داخل یک الگو:Math-فضای برداری وارد می‌کند. این منجر به آن می‌شود که تعداد عناصر الگو:Math برابر الگو:Math باشد که در آن الگو:Mvar یک عدد صحیح است.

اتحاد

$(x+y{)}^p=x^p+y^p$

(که گاهی رویای دانشجوی سال اول نامیده می‌شود) در یک میدان با مشخصه الگو:Math درست است. این از قضیه بسط دوجمله‌ای نتیجه شده‌است، به این دلیل که هر ضریب دوجمله‌ای در بسط الگو:Math، بجز اولین و آخرین ضریب، یک مضرب الگو:Math است.

از روی قضیه کوچک فرما، اگر الگو:Mvar یک عدد اول و الگو:Mvar در میدان الگو:Math باشد آنوقت الگو:Math است. این منجر به تساوی زیر

$X^p-X=\prod _{a\in \mathrm{G}\mathrm{F}(p)}(X-a)$

برای چندجمله‌ای‌های روی الگو:Math می‌شود. به صورت کلی‌تر، هر عنصر در الگو:Math تساوی چندجمله‌ای الگو:Math را برآورده می‌کند.

هر بسط میدان متناهی از یک میدان متناهی، قابل‌تفکیک و ساده است؛ یعنی اگر الگو:Math یک میدان متناهی باشد، و الگو:Math یک زیرمیدان الگو:Math باشد، آنوقت الگو:Math از الگو:Math قابل دستیابی است، اینکار از طریق مجاروت یک عنصر منفرد که چندجمله‌ای کمینه‌ای آن قابل تفکیک است، انجام می‌شود. در اصطلاح تخصصی، میدان‌های متناهی کامل هستند.

یک ساختار جبری کلی‌تر که همه اصول موضوعی دیگر یک میدان، غیر از این اصل که ضرب آن لازم نیست حتماً جابجایی‌پذیری باشد، را برآورده می‌کند، یک حلقه تقسیم (یا گاهی میدان کج) نامیده می‌شود. از روی قضیه کوچک ودربرن، هر حلقه تقسیم متناهی، جابجایی‌پذیر است، و از این‌رو یک میدان متناهی است.

وجود و یکتایی

فرض کنید الگو:Math یک نمای اول باشد، و الگو:Math میدان شکافنده چندجمله‌ای

$P=X^q-X$

روی میدان اول الگو:Math باشد. این یعنی الگو:Math یک میدان متناهی از پایین‌ترین مرتبه است، که در آن الگو:Math دارای الگو:Math تا ریشه متمایز است (مشتق صوری الگو:Math برابر الگو:Math است که یعنی الگو:Math، که در کل یعنی میدان شکافنده یک بسط قابل‌تفکیک از میدان اصلی است). اتحاد بالا نشان می‌دهد که جمع و ضرب دو ریشه الگو:Math هم ریشه الگو:Math است، همچنین وارون ضربی یکی از الگو:Math باز هم یک ریشه آن است. به زبان دیگر، ریشه‌های الگو:Math یک میدان از مرتبه الگو:Math می‌سازند که بر اساس کمینه‌بودن میدان شکافنده برابر الگو:Math است.

یکتایی به دلیل یکریختی میدان‌های شکافنده رخ‌می‌دهد که این یعنی همه میدان‌های مرتبه الگو:Math یکریخت هستند. همچنین، اگر یک میدان الگو:Mvar یک زیرمیدان از مرتبه الگو:Math داشته باشد، عناصر آن الگو:Mvar ریشه از الگو:Math هستند، و الگو:Mvar نمی‌تواند شامل زیرمیدان دیگری از مرتبه الگو:Mvar باشد.

به صورت خلاصه، ما این قضیه طبقه‌بندی را داریم که اولین‌بار در سال ۱۸۹۳ توسط ای.اچ. مور اثبات شد:

مرتبه یک میدان متناهی یک نمای اول است. برای هر نمای اول الگو:Math میدان‌هایی از مرتبه الگو:Math وجود دارد، و همه آن‌ها یکریخت هستند. در این میدان‌ها هر عنصر این را برآورده می‌کند

$x^q=x,$

و هر چندجمله‌ای الگو:Math به این‌صورت عامل‌بندی می‌شود

$X^q-X=\prod _{a\in F}(X-a).$

این منجر به آن می‌شود که الگو:Math شامل یک زیرمیدان یکریخت با الگو:Math باشد اگر و فقط اگر الگو:Math یک مقسوم‌علیه الگو:Math باشد؛ در این حالت، این زیرمیدان یکتا است. در حقیقت، چندجمله‌ای الگو:Math چندجمله‌ای الگو:Math را اگر و فقط اگر در صورتی تقسیم می‌کند که الگو:Math یک مقسوم‌علیه الگو:Math باشد.

ساخت صریح

میدان‌های غیراول

اگر یک نمای اول الگو:Math داشته باشیم که در آن الگو:Math اول است و الگو:Math است، میدان الگو:Math را به این روش می‌توان به صورت صریح ساخت. اول چندجمله‌ای غیرقابل‌کاهش الگو:Math را در الگو:Math از درجه الگو:Math انتخاب کنید (چنین چندجمله‌ای غیرقابل‌کاهشی همیشه موجود است)، آنوقت حلقه خارج‌قسمتی

$\mathrm{G}\mathrm{F}(q)=\mathrm{G}\mathrm{F}(p)[X]/(P)$

از حلقه چندجمله‌ای الگو:Math توسط ایده‌آل تولید شده توسط الگو:Math، یک میدان از مرتبه الگو:Math است.

به صورت صریح‌تر، عناصر الگو:Math چندجمله‌ای‌هایی روی الگو:Math هستند که درجه‌شان به صورت اکید کمتر از الگو:Math است. جمع و تفریق آن‌ها همان جمع و تفریق چندجمله‌ای‌ها روی الگو:Math است. ضرب دو عنصر برابر باقیمانده تقسیم اقلیدسی در الگو:Math از ضرب در الگو:Math است. وارون ضربی از یک عنصر غیرصفر را می‌توان توسط الگوریتم اقلیدسی تعمیم‌یافته محاسبه کرد؛ الگوریتم تعمیم‌یافته اقلیدس#بسط‌های میدان جبری ساده را ببینید.

به جز در ساخت الگو:Math، چندین گزینه ممکن برای الگو:Math وجود دارد، که همه، نتایج یکریخت تولید می‌کنند. برای ساده‌سازی تقسیم اقلیدسی، معمولاً می‌توان برای الگو:Math یک چندجمله‌ای از حالت زیر انتخاب کرد

$X^n+aX+b,$

این موضوع تقسیم‌های اقلیدسی لازم را خیلی کارا می‌سازد. با این حال، برای بعضی از میدان‌ها، معمولاً میدان‌های با مشخصه الگو:Math، ممکن است چندجمله‌ای‌های غیرقابل‌کاهش از حالت الگو:Math موجود نباشد. در مشخصه الگو:Math، اگر چندجمله‌ای الگو:Math کاهش‌پذیر باشد، پیشنهاد می‌شود که الگو:Math را با کمترین الگو:Math ممکن انتخاب کرد، که این باعث می‌شود چندجمله‌ای غیرقابل‌کاهش شود. اگر همه این سه‌جمله‌ای‌ها کاهش‌پذیر باشد، می‌توان «پنج‌جمله‌ای» الگو:Math را انتخاب کرد، زیرا چندجمله‌ای‌های با درجه بزرگتر از الگو:Math، با تعداد جمله زوج، در مشخصه الگو:Math هیچ‌وقت غیرقابل‌کاهش نیستند، زیرا ریشه الگو:Math را دارند.

یک گزینه ممکن برای چنین چندجمله‌ای توسط چندجمله‌ای‌های کانوی داده می‌شود. اینکار باعث اطمینان از یک سازگاری معین بین نمایش یک میدان و نمایش زیرمیدان‌هایش می‌شود.

در بخش‌های بعد، نشان می‌دهیم که چطور شگرد ساخت کلی ذکر شده در بالا برای میدان‌های متناهی کوچک کار می‌کند.

میدان‌های چهار عنصره

کوچکترین میدان غیراول، همان میدان چهار عنصره است، که معمولاً توسط الگو:Math یا ${𝔽}_4.$ نشان‌داده می‌شود. این شامل چهار عنصر $0,1,\alpha ,1+\alpha$ است به اینصورت که ${\alpha }^2=1+\alpha ,$ $1\cdot \alpha =\alpha \cdot 1=\alpha ,$ $x+x=0,$ و $x\cdot 0=0\cdot x=0,$ برای هر $x\in \mathrm{GF}(4)$ است. دیگر نتایج عملیاتی به سادگی توسط قانون توزیع‌پذیری قابل استنتاج است. زیر را برای جداول عملیاتی کامل ببینید.

این موضوع به صورت زیر از نتایج بخش قبل قابل‌استنتاج است.

روی الگو:Math، فقط یک چندجمله‌ای غیرقابل‌کاهش از درجه الگو:Val موجود است:

$X^2+X+1$

بنابراین، برای الگو:Math، روش ساخت بخش قبل باید این چندجمله‌ای را درگیر کند و

$\mathrm{G}\mathrm{F}(4)=\mathrm{G}\mathrm{F}(2)[X]/(X^2+X+1).$

فرض کنید الگو:Math به یک ریشه از این چندجمله‌ای در الگو:Math اشاره کند. این یعنی

الگو:Math

و اینکه الگو:Math و الگو:Math همان عناصر الگو:Math هستند، که در الگو:Math موجود نیستند. جداول عملیات الگو:Math از این نتیجه می‌شود، و به صورت زیر است:

جمع الگو:Math	ضرب الگو:Math	تقسیم الگو:Math
الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math	الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math	الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math الگو:Math

جدولی برای تفریق داده نشده‌است، زیرا تفریق معادل جمع است، این موضوع برای هر میدان از مشخصه ۲ درست است. در جدول سوم، یعنی تقسیم الگو:Math در الگو:Math، مقادیر الگو:Math باید از ستون چپ خوانده شود، و مقادیر الگو:Math باید ردیف بالا خوانده شود. (به این دلیل که الگو:Math برای هر الگو:Mvar در هر حلقه درست است، تقسیم بر ۰ باید تعریف‌نشده باقی بماند)

نگاشت

$\phi :x\mapsto x^2$

یک خودریختی میدانی غیربدیهی است، که خودریختی فروبینیوس نام دارد که الگو:Math را به ریشه دوم الگو:Math از چندجمله‌ای غیرقابل‌کاهش ذکر شده در بالا، یعنی $X^2+X+1.$ می‌فرستد.

جستارهای وابسته

• گروه متناهی