میدان متناهی

در ریاضیات، یک میدان متناهی (به انگلیسی: finite field) یا میدان گالوا (به انگلیسی: Galois field) که به افتخار اواریست گالوا نامگذاری شده‌است، یک میدان است که شامل تعداد متناهی عنصر است. مثل هر میدانی، یک میدان متناهی یک مجموعه‌ای است که روی آن عملیات ضرب، جمع، تفریق و تقسیم تعریف شده و قواعد مبنایی معینی را برآورده می‌سازد. معمول‌ترین مثال‌های میدان متناهی همان میدان اعداد در پیمانه $p$ است که در آن $p$ یک عدد اول است.

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

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

ویژگی‌ها

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

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

اگر $q = p k$ باشد، همه میدان‌های از مرتبه $q$ یکریخت هستند (بخش وجود و یکتایی را در زیر ببینید).^[۱] بعلاوه، یک میدان نمی‌تواند شامل دو زیرمیدان متناهی متفاوت با یک مرتبه یکسان باشد. از این‌رو می‌توان همه میدان‌های متناهی با یک مرتبه یکسان را شناسایی کرد، و به صورت غیرمبهم توسط $\mathbb {F} _{q}$ ، $F q$ ، یا $GF(q)$ نشان داد، که در آن حروف GF مخفف «میدان گالوا» یا "Galois field" است.^[۲]

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

ساده‌ترین مثال‌های میدان‌های متناهی همان میدان‌های مرتبه اول هستند: برای هر عدد اول $p$ میدان اول از مرتبه $p$ یعنی $\mathbb {F} _{p}$ را می‌توان به صورت اعداد صحیح در پیمانه $p$ یا $Z / p Z$ ساخت.

عناصر میدان اول از مرتبه $p$ توسط اعداد صحیح در محدوده $0, \dots , p - ۱$ نمایش داده می‌شود. جمع، تفریق، و ضرب همان باقیمانده تقسیم بر $p$ از نتیجه عملیات عدد صحیح متناظر هستند. وارون ضربی یک عنصر توسط الگوریتم اقلیدسی تعمیم‌یافته محاسبه می‌شود (الگوریتم تعمیم‌یافته اقلیدس § حساب پیمانه‌ای اعداد صحیح را ببینید).

فرض کنید که $F$ یک میدان متناهی باشد. برای هر عنصر $x$ در $F$ و هر عدد صحیح $n$ ، جمع $n$ نسخه از $x$ توسط $n \cdot x$ نمایش داده می‌شود. کمترین $n$ مثبتی که در آن $n \cdot ۱ = ۰$ است برابر مشخصه $p$ میدان است. این موضوع امکان تعریف ضرب $(k,x)\mapsto k\cdot x$ از یک عنصر $k$ از $GF(p)$ را در یک عنصر $x$ از $F$ می‌دهد، این کار با انتخاب یک عدد صحیح نماینده برای $k$ انجام می‌شود. این ضرب $F$ را داخل یک $GF(p)$ -فضای برداری وارد می‌کند. این منجر به آن می‌شود که تعداد عناصر $F$ برابر $p n$ باشد که در آن $n$ یک عدد صحیح است.

اتحاد

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

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

از روی قضیه کوچک فرما، اگر $p$ یک عدد اول و $x$ در میدان $GF(p)$ باشد آنوقت $x p = x$ است. این منجر به تساوی زیر

X^{p}-X=\prod _{a\in {\rm {GF}}(p)}(X-a)

برای چندجمله‌ای‌های روی $GF(p)$ می‌شود. به صورت کلی‌تر، هر عنصر در $GF(p n)$ تساوی چندجمله‌ای $x p n - x = ۰$ را برآورده می‌کند.

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

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

وجود و یکتایی

فرض کنید $q = p n$ یک نمای اول باشد، و $F$ میدان شکافنده چندجمله‌ای

P=X^{q}-X

روی میدان اول $GF(p)$ باشد. این یعنی $F$ یک میدان متناهی از پایین‌ترین مرتبه است، که در آن $P$ دارای $q$ تا ریشه متمایز است (مشتق صوری $P$ برابر $P' = -۱$ است که یعنی $gcd(P, P') = ۱$ ، که در کل یعنی میدان شکافنده یک بسط قابل‌تفکیک از میدان اصلی است). اتحاد بالا نشان می‌دهد که جمع و ضرب دو ریشه $P$ هم ریشه $P$ است، همچنین وارون ضربی یکی از $P$ باز هم یک ریشه آن است. به زبان دیگر، ریشه‌های $P$ یک میدان از مرتبه $q$ می‌سازند که بر اساس کمینه‌بودن میدان شکافنده برابر $F$ است.

یکتایی به دلیل یکریختی میدان‌های شکافنده رخ‌می‌دهد که این یعنی همه میدان‌های مرتبه $q$ یکریخت هستند. همچنین، اگر یک میدان $F$ یک زیرمیدان از مرتبه $q = p k$ داشته باشد، عناصر آن $q$ ریشه از $X q - X$ هستند، و $F$ نمی‌تواند شامل زیرمیدان دیگری از مرتبه $q$ باشد.

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

مرتبه یک میدان متناهی یک نمای اول است. برای هر نمای اول

q

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

x^{q}=x,

و هر چندجمله‌ای X^q − X به این‌صورت عامل‌بندی می‌شود

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

این منجر به آن می‌شود که $GF(p n)$ شامل یک زیرمیدان یکریخت با $GF(p m)$ باشد اگر و فقط اگر $m$ یک مقسوم‌علیه $n$ باشد؛ در این حالت، این زیرمیدان یکتا است. در حقیقت، چندجمله‌ای $X p m - X$ چندجمله‌ای $X p n - X$ را اگر و فقط اگر در صورتی تقسیم می‌کند که $m$ یک مقسوم‌علیه $n$ باشد.

ساخت صریح

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

اگر یک نمای اول $q = p n$ داشته باشیم که در آن $p$ اول است و $n > 1$ است، میدان $GF(q)$ را به این روش می‌توان به صورت صریح ساخت. اول چندجمله‌ای غیرقابل‌کاهش $P$ را در $GF(p)[X]$ از درجه $n$ انتخاب کنید (چنین چندجمله‌ای غیرقابل‌کاهشی همیشه موجود است)، آنوقت حلقه خارج‌قسمتی

{\rm {GF}}(q)={\rm {GF}}(p)[X]/(P)

از حلقه چندجمله‌ای $GF(p)[X]$ توسط ایده‌آل تولید شده توسط $P$ ، یک میدان از مرتبه $q$ است.

به صورت صریح‌تر، عناصر $GF(q)$ چندجمله‌ای‌هایی روی $GF(p)$ هستند که درجه‌شان به صورت اکید کمتر از $n$ است. جمع و تفریق آن‌ها همان جمع و تفریق چندجمله‌ای‌ها روی $GF(p)$ است. ضرب دو عنصر برابر باقیمانده تقسیم اقلیدسی در $P$ از ضرب در $GF(p)[X]$ است. وارون ضربی از یک عنصر غیرصفر را می‌توان توسط الگوریتم اقلیدسی تعمیم‌یافته محاسبه کرد؛ الگوریتم تعمیم‌یافته اقلیدس#بسط‌های میدان جبری ساده را ببینید.

به جز در ساخت $GF(4)$ ، چندین گزینه ممکن برای $P$ وجود دارد، که همه، نتایج یکریخت تولید می‌کنند. برای ساده‌سازی تقسیم اقلیدسی، معمولاً می‌توان برای $P$ یک چندجمله‌ای از حالت زیر انتخاب کرد

X^{n}+aX+b,

این موضوع تقسیم‌های اقلیدسی لازم را خیلی کارا می‌سازد. با این حال، برای بعضی از میدان‌ها، معمولاً میدان‌های با مشخصه $2$ ، ممکن است چندجمله‌ای‌های غیرقابل‌کاهش از حالت $X n + aX + b$ موجود نباشد. در مشخصه $2$ ، اگر چندجمله‌ای $X n + X + 1$ کاهش‌پذیر باشد، پیشنهاد می‌شود که $X n + X k + 1$ را با کمترین $k$ ممکن انتخاب کرد، که این باعث می‌شود چندجمله‌ای غیرقابل‌کاهش شود. اگر همه این سه‌جمله‌ای‌ها کاهش‌پذیر باشد، می‌توان «پنج‌جمله‌ای» $X n + X a + X b + X c + 1$ را انتخاب کرد، زیرا چندجمله‌ای‌های با درجه بزرگتر از $1$ ، با تعداد جمله زوج، در مشخصه $2$ هیچ‌وقت غیرقابل‌کاهش نیستند، زیرا ریشه $1$ را دارند.^[۳]

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

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

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

کوچکترین میدان غیراول، همان میدان چهار عنصره است، که معمولاً توسط $GF(4)$ یا $\mathbb {F} _{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 \operatorname {GF} (4)$ است. دیگر نتایج عملیاتی به سادگی توسط قانون توزیع‌پذیری قابل استنتاج است. زیر را برای جداول عملیاتی کامل ببینید.

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

روی $GF(2)$ ، فقط یک چندجمله‌ای غیرقابل‌کاهش از درجه ۲ موجود است:

X^{2}+X+1

بنابراین، برای $GF(4)$ ، روش ساخت بخش قبل باید این چندجمله‌ای را درگیر کند و

{\rm {GF}}(4)={\rm {GF}}(2)[X]/(X^{2}+X+1).

فرض کنید $α$ به یک ریشه از این چندجمله‌ای در $GF(4)$ اشاره کند. این یعنی

α 2 = ۱ + α,

و اینکه $α$ و $1 + α$ همان عناصر $GF(4)$ هستند، که در $GF(2)$ موجود نیستند. جداول عملیات $GF(4)$ از این نتیجه می‌شود، و به صورت زیر است:

جمع

x + y

ضرب

x \cdot y

تقسیم

x / y

$x ╲ y$	$0$	$1$	$α$	$1 + α$
$0$	$0$	$1$	$α$	$1 + α$
$1$	$1$	$0$	$1 + α$	$α$
$α$	$α$	$1 + α$	$0$	$1$
$1 + α$	$1 + α$	$α$	$1$	$0$

$x ╲ y$	$0$	$1$	$α$	$1 + α$
$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$α$	$1 + α$
$α$	$0$	$α$	$1 + α$	$1$
$1 + α$	$0$	$1 + α$	$1$	$α$

$x ╲ y$	$1$	$α$	$1 + α$
$0$	$0$	$0$	$0$
$1$	$1$	$1 + α$	$α$
$α$	$α$	$1$	$1 + α$
$1 + α$	$1 + α$	$α$	$1$

جدولی برای تفریق داده نشده‌است، زیرا تفریق معادل جمع است، این موضوع برای هر میدان از مشخصه ۲ درست است. در جدول سوم، یعنی تقسیم $x$ در $y$ ، مقادیر $x$ باید از ستون چپ خوانده شود، و مقادیر $y$ باید ردیف بالا خوانده شود. (به این دلیل که $۰ \cdot z = ۰$ برای هر $z$ در هر حلقه درست است، تقسیم بر ۰ باید تعریف‌نشده باقی بماند)

نگاشت

\varphi :x\mapsto x^{2}

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

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

گروه متناهی

پانویس

↑ ^۱٫۰ ^۱٫۱ Moore, E. H. (1896), "A doubly-infinite system of simple groups", in E. H. Moore; et al. (eds.), Mathematical Papers Read at the International Mathematics Congress Held in Connection with the World's Columbian Exposition, Macmillan & Co., pp. 208–242
↑ This latter notation was introduced by E. H. Moore in an address given in 1893 at the International Mathematical Congress held in Chicago (Mullen و Panario 2013، p. 10).
↑ Recommended Elliptic Curves for Government Use (PDF), National Institute of Standards and Technology, July 1999, p. 3

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Finite field». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۷ دسامبر ۲۰۲۱.

[moore-1] ۱٫۰ ^۱٫۱ Moore, E. H. (1896), "A doubly-infinite system of simple groups", in E. H. Moore; et al. (eds.), Mathematical Papers Read at the International Mathematics Congress Held in Connection with the World's Columbian Exposition, Macmillan & Co., pp. 208–242

[2] This latter notation was introduced by E. H. Moore in an address given in 1893 at the International Mathematical Congress held in Chicago (Mullen و Panario 2013، p. 10).

[3] Recommended Elliptic Curves for Government Use (PDF), National Institute of Standards and Technology, July 1999, p. 3

[۱]

[۲]

[۳]