موضوع مقاله: الگوریتم تعمیم‌یافته اقلیدس | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم تعمیم‌یافته اقلیدس | مقدمه: الگوریتم تعمیم یافته اقلیدس به الگوریتمی بسیار مشابه به الگوریتمی برای محاسبه بزرگترین مقسوم علیه مشترک چندجمله ای و ضرایب قضیه بزو از دو چندجمله‌ای با یک متغیر، ارجاع دارد. | ## بخش 1: الگوریتم تعمیم‌یافته اقلیدس | چون x برابر وارون ضربی پیمانه‌ای a به پیمانه b و y برابر وارون ضربی پیمانه‌ای b به پیمانه a است. در الگوریتم اقلیدس برای چندجمله‌ای می‌توان وارون ضربی را در بسط‌های میدان جبری محاسبه کرد. که از آن نتیجه می‌شود هردو نوع الگوریتم اقلیدسی تعمیم یافته (معمولی و چندجمله‌ای) کاربردی گسترده در رمزنگاری دارند. توضیح الگوریتم در الگوریتم اقلیدسی معمولی فقط باقی‌مانده‌ها نگاه داشته می‌شوند و خارج قسمت استفاده نمی‌شود. به‌طور دقیقتر در الگوریتم تعمیم یافته که a، b را به عنوان ورودی می‌گیرد، دنبالهٔ از خارج قسمت‌ها و دنبالهٔ از باقی‌مانده‌ها را شامل می‌شود. مهمترین ویژگی تقسیم اقلیدسی نامساوی سمت راست است که را متفاوت از و تعریف می‌کند. وقتی باقی‌مانده به صفر رسید محاسبه متوقف می‌شود، بزرگترین مقسوم علیه مشترک آخرین باقی‌مانده غیر صفر است. الگوریتم تعمیم یافته اقلیدسی روشی مشابه دارد با این تفاوت که دو دنبالهٔ زیر نیز به آن اضافه می‌شود: در این الگوریتم هم وقتی میشود کار الگوریتم به اتمام می‌رسد. ضرایب بزو هم که برابر و در رابطهٔ زیر صدق می‌کنند: خارج قسمت تقسیم a و b بر بزرگترین مقسوم علیه مشترکشان به این صورت است: و به علاوه اگر a و b هردو مثبت باشند داریم: که این یعنی جفت ضرایب بزو که از این الگوریتم به دست می‌آیند یکی از کمترین جفت ضرایب بزو هستند. که از ان نتیجه می‌شود بزرگترین مقسوم علیه مشترک برابر است با بزرگترین مقسوم علیه مشترک وهمچنین نشان می‌دهد که بزرگترین مقسوم علیه مشترک a و b است که آن را d می‌نامیم. و که برای i=0,1داریم: برای هر i رابطهٔ بازگشتی خطی برقرار است بخصوص برای i=k که نشان میدهیم که ضرایب بزواند. ماتریس زیر را در نظر بگیرید رابطهٔ بازگشی را به شکل ماتریسی می‌نویسیم ماتریس ماتریس واحد است و دترمینان آن برابر ۱ است. دترمینان ماتریس سمت راست برابر -1 است که نتیجه می‌شود دترمینان برابر است و برای حالت خاص i=k+1 داریم که نشان می‌دهد و نسبت بهم اولند. رابطهٔ که در بالا اثبات شد و لم اقلیدس نشان می‌دهد که مقسوم علیه b و مقسوم علیه a‌اند. | ## بخش 2: الگوریتم تعمیم‌یافته اقلیدس | چون آن‌ها نسبت بهم اولاً بدون در نظر گرفتن علامتشان برابر خارج قسمت تقسیم a و b بر d می‌شوند. الگوریتم اقلیدسی برای چندجمله‌ای برای یک چندجمله‌ای با ضریب در یک میدان همه چیز مشابه حالت قبل است (تقسیم اقلیدسی، قضیه بزو، و تعمیم الگوریتم اقلیدس). تفاوت دوم در محدودیتی است که بر اندازهٔ ضرایب بزو که از تعمیم الگوریتم اقلیدس به دست میاید وجود دارد، که در مورد چندجمله‌ای دقیق تر است. اگر a و b دو چند جملۀ غیر صفر باشند الگوریتم تعمیم یافته (s,t) را به گونه‌ای به دست میاورد که در شرایط زیر صدق کند: و تفاوت سوم در این است که بزرگترین مقسوم علیه مشترک فقط به صورت ضرب یک ثابت غیر صفر تعریف می‌شود. اگر a و b نسبت به هم اول باشند در سمت راست نامساوی بزو یکی ۱ می‌شود، در غیر این صورت یکی ممکن است هر مقدار ثابت غیر صفر شود. در جبر کامپیوتر، چندجمله‌ای معمولاً ضرایب صحیح را می‌پذیرد، و این راه ساده‌سازی بزرگترین مقسوم علیه مشترک برای سهولت تعداد بسیار زیادی بخش ایجاد می‌کند. راه دوم ساده‌سازی بزرگترین مقسوم علیه مشترک در حالت چندجمله‌ای با ضرایب صحیح تقسیم بر بزرگترین عمل مشترک بین ضرایب برای رسیدن به چندجمله‌ای اصلی (یعنی چندجمله‌ای که بزرگترین عامل مشترک ضرایبش ۱ است). اگر چند جمله‌ی‌های ورودی نسبت به هم اول باشند این نرمال‌سازی بزرگترین مقسوم علیه مشترک را یک می‌دهد. این روش این امکان را فراهم می‌کند که وقتی با چندجمله‌ای با ضرایب صحیح شروع می‌کنیم هر چندجمله‌ای که بدست میاید ضرایبش، صحیح باشد. اگر همه چیز را بر resultant تقسیم کنیم قضیه کلاسیک بزو بدست می‌آید ، با یک مقسوم علیه مشترک ساده برای اعداد گویایی که در آن ظاهر می‌شوند. شبه‌کد برای پیاده‌سازی الگوریتمی که در بالا ذکر شد،اولاً باید توجه داشت که در هر مرحله تنها نیاز به نگهداری دو مقدار نهایی متغیرهای شاخص‌گذاری شده، هست. بنابراین برای صرفه جویی در حافظه هر متغیر شاخص‌گذاری شده باید با تنها دو متغیر جایگزین شود. برای راحتی کار در الگوریتم زیر(و بقیهٔ الگوریتم‌ها در این مقاله) از مقداردهی موازی استفاده می‌شود.در زبانهای برنامه نویسی که از مقداردهی موازی پشتیبانی نمی‌کنند، باید اینکار را با کمک یک متغیر کمکی شبیه سازی کرد. رفع این مشکل در انتهای محاسبات بسیار ساده هست، اما در اینجا به دلیل سادگی کد بیان نشده‌است. | ## بخش 3: الگوریتم تعمیم‌یافته اقلیدس | مشاب‌ها اگر یکی از دو مقدار a یا b منفی و دیگری صفر باشد، ب.م.م، که خروجی این الگوریتم هست، منفی می‌شود و باید علامت خروجی تغییر کند. محاسبه ی وارون ضربی در ساختارهای پیمانه ای الگوریتم تعمیم یافتهٔ اقلیدس وسیلهٔ اصلی برای محاسبهٔ وارون ضربی در ساختارهای پیمانه‌ای هست و اغلب در حساب پیمانه‌ای اعداد صحیح و تعمیم‌های میادین جبری به کار می‌آید.یک نمونهٔ مهم از مورد آخر میدان‌های متناهی با order غیر اول هست. حساب پیمانه‌ای اعداد صحیح اگر n یک عدد صحیح مثبت باشد، حلقهٔ Z/nZ ممکن هست توسط مجموعه {0, 1, ..., n} از باقی‌مانده‌های تقسیم اقلیدسی بر n قابل شناسایی باشد،عمل جمع و ضرب همان محاسبه ی، باقی‌ماندهٔ نتیجهٔ جمع و ضرب اعداد صحیح، بر n هست.یک عضو از Z/nZ یک وارون ضربی دارد(اگر چنین باشد، به آن unit میگویند) اگر نسبت به n اول باشد.در حالت خاص اگر n اول باشد a وارون ضربی دارد،اگر مخالف صفر باشد(باقی‌مانده اش بر n).بنابراین Z/nZ یک میدان هست اگر و تنها اگر n اول باشد. قضیه بزو بیان می‌کند که a و n نسبت به هم اولند اگر و تنها اگر اعداد صحیحی مانند s و t وجود داشته باشند که که اگر از دوطرف بر n باقی‌مانده بگیریم: بنابراین t یا، به‌طور دقیقتر، باقی‌ماندهٔ تقسیم t بر n، همان وارون ضربی a در پیمانهٔ n هست. برای تطبیق دادن الگوریتم تعمیم یافتهٔ اقلیدس به نحوی که این مسئله را حل کند، باید در نظر داشته باشیم که نیازی به محاسبهٔ ضرایب بزو ی n نیست.همچنین برای اینکه نتیجه مثبت و کمتر از n باشد، باید از این موضوع که t همواره در رابطهٔ |t| < n صدق می‌کند،استفاده کرد. اگر t <0 در انتهای کار می‌توان با جمع کردن آن با n آن را مثبت کرد.این تغییرات را در شبه کد زیر آورده ایم که در آن n یک عدد صحیح بزرگتر از یک هست. در واقع اگر p یک عدد اول باشد و q = pd، میدان با اندازه(order) q یک تعمیم سادهٔ جبری از میدان اول p عضو ، هست، که توسط یک ریشهٔ معادله چندجمله‌ای کاهش ناپذیر از درجه d ساخته شده‌است. یک بسط سادهٔ جبری L از یک میدان K که توسط ریشه یک چندجمله‌ای کاهش ناپذیر از درجه d ساخته شده‌است، ممکن است توسط حلقهٔ خارج قسمت‌های به‌طور یکتا شناسایی شود، و اعضایش در یک رابطهٔ یک به یک و و پوشا با چندجمله‌ای‌هایی با درجات کمتر از d هستند.عمل جمع در L همان جمع چندجمله‌ای ها است.عمل ضرب در L باقی‌ماندهٔ تقسیم اقلیدسی بر، p حاصلضرب چندجمله ای‌ها است.بنابراین برای تکمیل اعمال حسابی در L تنها کافیست نحوهٔ محاسبهٔ وارون ضربی را تعریف کنیم.که آن با استفاده از الگوریتم تعمیم یافتهٔ اقلیدسی انجام می‌شود. این الگوریتم بسیار شبیه الگوریتمی است که در بالا برای محاسبهٔ وارون ضربی پیمانه‌ای بیان شده‌است.در اینجا دو تفاوت مهم وجود دارد:اولاً اینکه به خط آخر نیازی نیست، چون ضریب بزو همیشه یک درجه کمتر از d دارد. دوم اینکه ب.م.م ای که بدست آمده‌است، وقتی که چندجمله‌ای‌های ورودی نسبت به هم اولند، ممکن هست هر عضو غیرصفری از K باشند، بنابراین ضریب بزو (یک چندجمله‌ای با درجهٔ مثبت) باید در وارون این عضو از K ضرب شود. در شبه کد زیر p یک چندجمله‌ای از درجه بزرگتر از یک هست و a یک چندجمله‌ای هست.علاوه بر این div یک تابع کمکی است که خارج قسمت تقسیم اقلیدسی را حساب می‌کند. الگوریتم تعمیم یافته اقلیدس برای بیش از دو عدد ما می‌توانیم در موردی که تعداد اعداد بیش از دو تا هست، به‌طور پشت سر هم(دو تا باهم و سپس حاصل آن‌ها با عدد بعدی) از این الگوریتم استفاده کنیم.اول باید اثبات کنیم که .برای این اثبات اگر باشد،طبق تعریف می‌توان گفت که d مقسوم علیه مشترک a و b هست.بنابراین برای یک مقدار خاص k داریم .مشاب‌ها d مقسوم علیه c هم هست، پس برای یک مقدار خاصی ازj .اگر با این تعریف ما از u، اما چون d بزرگترین مقسوم علیه هستu وارون ضربی دارد.(unit هست.) بنابراین اگر پس مقادیر x و y وجود دارند به‌طوری‌که . | ## جمع‌بندی | پس اگر ما آن را با استقرا روی n عدد انجام دهیم به معادلهٔ زیر میرسیم که همان چیز مورد انتظار ما هست.