الگوریتم کانتور-زاسنهاوس

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم کانتور-زاسنهاوس در جبر محاسباتی الگوریتم کانتور-زاسنهاوس روش شناخته شده‌ای برای تجزیه ی چند جمله‌ای‌ها به عوامل محدود است. این الگوریتم عمدتاً شامل محاسبات توانی و چند جمله‌ای ب.م.م می‌شود که توسط D.cantor و Hans Zassenhaus در سال 1981 نوآوری شد. این الگوریتم مسلماً الگوریتم برتری نسبت به راه حل قبلی (Berlekamp's algorithm) در سال 1967 است. و در حال حاضر در بسیاری از سیستم‌های جبر محاسباتی اجرا می‌شود.

بررسی اجمالی[ویرایش]

پیش زمینه[ویرایش]

الگوریتم کانتور-زاسنهاوس یک چند جمله‌ای با درجه ی n با ضرایب محدود که چند جمله‌ای‌های تجزیه ناپذیر آن از درجه ی یکسانی هستند را به عنوان ورودی می‌گیرد(f(x. و در خروجی چند جمله‌ای (g(x را می‌دهد به طوری که تابع خروجی تابع ورودی را تقسیم می‌کند. اگر فرض کنیم(f(x عوامل تجزیه ناپذیر از درجه ی d دارد این حلقه ی عوامل هم ریخت محصول مستقیم حلقه ی عامل است. مثلاً اگر:

باشد، .

نتیجه اصلی[ویرایش]

اگر یک چند جمله‌ای با شرایط زیر باشد:

که کاهش یافته ی باقی‌مانده تقسیم بر باشد و هیچ کدام از مجموعه‌های زیر تهی نباشند:

عوامل غیر تهی زیر برای (f(x وجود دارند:

الگوریتم[ویرایش]

الگوریتم کانتور-زاسنهاوس چند جمله‌ای‌های شبیه (a(x در قسمت بالا را با استفاده از همریختی‌های بحث شده در قسمت پیش زمینه محاسبه می‌کند: چند جمله‌ای را به صورت تصادفی در نظر می‌گیرد به طوری که . همچنین مقدار را در نظر بگیر و را محاسبه کن.

که هر عنصری از زمینه رتبه ی است.

کاربرد ها[ویرایش]

یکی از کاربردهای الگوریتم کانتور-زاسنهاوس در محاسبه ی لگاریتم گسسته روی عوامل با درجه ی اول است. محاسبه ی لگاریتم گسسته یکی از مسایل مهم رمزنگاری کلید عمومی است.

منابع[ویرایش]

  • David G. Cantor and Hans Zassenhaus. "A New Algorithm for Factoring Polynomials Over Finite Fields". Mathematics of Computation, 36:587-592, 1981.