الگوریتم کانتور-زاسنهاوس
الگوریتم کانتور-زاسنهاوس در جبر محاسباتی الگوریتم کانتور-زاسنهاوس روش شناخته شدهای برای تجزیهٔ چند جملهایها به عوامل محدود است. این الگوریتم عمدتاً شامل محاسبات توانی و چند جملهای ب.م.م میشود که توسط 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.